Editorial for Baltic OI '08 P5 - Grid - Olympiads Online Judge

Editorial for Baltic OI '08 P5 - Grid

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Subtask 1

The simplest solution is to consider all $\binom{n}{r} \binom{m}{s}$ $(\binom{n}{r}) (\binom{m}{s})$ placings of lines.

Time Complexity: $\mathcal O(\binom{n}{r} \binom{m}{s} nm)$ $O ((\binom{n}{r}) (\binom{m}{s}) n m)$

Subtask 2

If we fix the placing of lines going in one direction, then the optimal placing of lines going in the other direction can be computed much faster. There are two possible approaches:

We can use binary search to find an optimal computing time. Given a candidate for an optimal computing time and placing of all horizontal lines, we can place the vertical lines from the leftmost to the rightmost one using greedy approach: each vertical line should be put as far to the right as possible. This solution runs in $\mathcal O(\binom{n}{r} nm \log S)$ $O ((\binom{n}{r}) n m \log S)$ time, where $S$ $S$ is the sum of all computation times for individual squares.
Another approach considers all $\binom{n}{r}$ $(\binom{n}{r})$ placings of horizontal lines. For each placing, it calculates the minimal processing time using dynamic programming. Let $min[i][j]$ $m i n [i] [j]$ be the minimal processing time of $i$ $i$ first columns divided with $j$ $j$ meridians. The array $min$ $m i n$ can be easily filled in $\mathcal O(m^2n)$ $O (m^{2} n)$ time. The overall running time is $\mathcal O(\binom{n}{r}m^2n)$ $O ((\binom{n}{r}) m^{2} n)$ .

Time Complexity: $\mathcal O(\binom{n}{r} nm \log S)$ $O ((\binom{n}{r}) n m \log S)$ or $\mathcal O(\binom{n}{r}m^2n)$ $O ((\binom{n}{r}) m^{2} n)$

Comments

There are no comments at the moment.