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.