SquareCovering in SRM 474

At first, I found that there's an optimal solution where each square's left and upper edge must touch a red point. Otherwise we can simply shift those squares.

This lead to a straightforward bit-mask DP. Suppose we sort the points along the x axis then the y axis. Then for each mask(bit 1 represents a point already been covered), we find the lowest 0 bit(corresponding to the left most uncovered point thus is the left edge of the square), iterate through all points while using those to the upper right of it as possible upper edges, iterate through all possible squares and calculate the new mask to do the DP. This results in O((2^n)*(n^2)*m), which barely passed under the time limit by some careful pruning(ignore points already covered when iterating through points).

As I looked at others' solutions in the practice room, I found a clever technique to optimize. Instead of explicitly determine the position of the squares, we can first simply calculate all the masks using exactly one square. Then using the techniques to iterate through subsets, we can set dp[mask] to min(dp[i]+dp[maks^i], mask|i==mask). Inductively, if two subsets can both be covered by an arbitrary number of squares, so is the whole set. This results in O(3^n).

Optimal Proof - Nisoku in SRM 463

I'll prove a subtle part of the problem:

Given a sorted array of even length $\{a_1, a_2, \ldots, a_{2n}\}$, we need to pair these elements and multiply the sum of each pair. The largest value should be $(a_1 + a_{2n}) \times (a_2 + a_{2n-1}) \cdots$.

Let's consider an easier case. Suppose we have 4 numbers $a<b<c<d$. It's obvious that $(a+d)(b+c)>(a+b)(c+d)$ and $(a+d)(b+c)>(a+c)(b+d)$. How can we generalize this property?

Suppose $a_1$ is paired with some $a_i$, and $a_{2n}$ is paired with some $a_j$. By a single exchange, we could get a better solution. After that, the pair of the smallest & largest element remains the same, and we can use induction here for inner elements.

Sometimes it's just essential to prove pairwise inequalities for sequence optimality.

SRM536 Div1 Level2 500 Problem

The solution is ready for download at https://sites.google.com/site/boyouepii/document/SRM-536-Div1-Medium.pdf?attredirects=0&d=1.
I'm practicing $latex \textrm{\LaTeX}$ these days and this solution happens to be quite mathematical.

SRM522 Div1 Level1 250 Problem

Given a board consisting of n(n>=2) cells, each marked with either an 'A' or 'B', Alice and Bob alternatively place coins on some continuous empty cells, with the restriction that at least one cell must be left empty. When there is only one cell left, Alice wins if that cell is marked with 'A' and Bob wins otherwise.

First of all, if at least one end is marked with an 'A', then Alice wins. Without loss of generality, suppose the board is of the form "A??...?"('?' means empty cells marked with 'A' or 'B' arbitrarily). Alice can obtain "ACC...C"('C' means covered by a coin) in one step and win.

Then what if the board is of the form "B??...?B"?
If Alice covered either end with a coin, again without loss of generality, the board becomes "CC...CB" or "CC...C??..?B". Bob wins immediately for the former, by covering all other empty cells except the rightmost 'B' for the latter. So Alice would have to choose "B??...?CC...C??...?B" if she wanted to win.
Now let's consider a simpler situation, "B??...?CC...CB". (I)If it is now Bob's turn, he only needs to cover all the empty cells on the left and wins. (II)If it is now Alice's turn, she has up to four choices. If she choose to cover the rightmost 'B' or either end of the empty cells on the left, Bob can obviously win. Then again she has to choose to make the board of the form "B??...?CC...C??...?CC...CB". If Bob covers all empty cells of the second interval, then we reach the same configuration except that the number of empty cells decreases. So we can prove by induction that no matter whose turn is it, the winner would be Bob if the board is of the form "B??...?CC...CB".
So let's return to "B??...?CC...C??...?B". If the second interval is empty, the it corresponds to (I). Otherwise, Bob could cover all empty cells on the right except the rightmost 'B', and now it corresponds to (II). Either way, Bob wins.

So all we have to do is to check the two cells on both ends.

I code a bit mask DP during the contest. Finding patterns and proving them is still a hard task for me. Need more exercise.

SRM502 Div1 Level2 500 Problem

We define the relation problem[i]<problem[j] if pointsPerMinute[i]*requiredTime[j]>pointsPerMinute[j]*requiredTime[i]. This is a total order, as is explained in this thread.

If two adjacent problems, say i and i+1, satisfies that problem[i+1]<problem[i]. Then by swapping them, we get a better solution, for doing so doesn't affect the points of all other problems, increases problem[i+1]'s point by pointsPerMinute[i+1]*requiredTime[i] and decreases problem[i]'s point by pointsPerMinute[i]*requiredTime[i+1]. By definition, the former is larger.

Many people figure out at this point that the best solution must be exactly the one satisfying problem[i]<=problem[i+1] for all i in the range [0,n-2], e.g. this post by wywcgs. I used to just believe so after a USACO contest, but now I'm not that convinced. So I do some careful analysis.(I hope for an intuitive explanation.)

Lemma 1. If S is not a sorted sequence, then there must be at least one pair of adjacent elements such that S[i]>S[i+1].
Lemma 2. For every possible sequence S, we can get the sorted sequence by repeatedly swapping adjacent pairs such that S[i]>S[i+1]. We know in linear algebra such adjacent swapping reduces the inversion number by exactly 1.(I'm eagerly looking forward to a more elegant explanation.)
Theorem 3. The sorted sequence is the best solution. This comes directly from the fact that all the swapping operations in Lemma 2 increase the points.

Note that we may not want to include some problems, since their points may become negative. But every time we do decide to include a problem, it must be placed at the end if we consider the problems in order. So the optimal substructure and independent substructure properties are reserved. The recurrence relation becomes obvious as in the classic 0-1 knapsack problem: best[i][j]=max(best[i-1][j], best[i-1][j-requiredTime[i]]+maxPoint[i]-j*pointsPerMinute[i]). Here i means we have so far considered problem [0, i] and j means the last problem gets solved at time j.

P.S. See Petr's perfect code here.