Easy — BearCharges

Did you help Limak, a little bear? Each base is a vertex and all vertices (except 0) should have a parent — base from which this one was captured. So we are looking for a tree but not exactly MST because for a vertex order of his children matters.

Let dp[mask][x] denote time needed to capture all bases in set defined by mask if we start with base x. We will calculate dp[S][a] by iterating over possible first son of a and over bitmask denoting set of vertices in subtree of a — so consider to which base b we shoot first and what bases will be captured directly or indirectly by b. dp[S][a] = min(dp[S][a], dist(a, b) + max(dp[A][a], dp[S - A][b]))

It is O(3ⁿ·n²) but you can get easier implementation with O(4ⁿ + 3ⁿ·n²) — check out my code.

Med — LuckyGrid

Let's assume n > 1. Note: by line I mean row or column.

The only possible lucky sums of lines are 44, 47, 74, 77, 444, 447. For n ≠ 11 there are exactly 0 or 2 lucky sums possible to get (e.g. only 74 and 77). Then for fixed n we have condition e.g. "sums should be 74 or 77" and it is equivalent to "in a line there should be x or x + 1 fours" — and we want to maximize number of fours.

We should solve this new problem with a flow. It's possible to solve it with "bounded flow" (I haven't heard of it before) but I will describe solution with MinCost. For all lines there could be some fours already in the grid so we count them and we know how many more fours should this line have. From S to each vertex denoting row we add two edges:
1. minimum capacity we want, cost 0
2. capacity 1, cost C where C is some big constant (I had 10⁵).
Similarly for edges from vertices denoting columns to T. And ofc. we add unit edges from each vertex to each column if there is empty cell. Now we run MinCostFlow and thanks to C we know number of used edges of each kind, ie. cost / C is number of used edges with cost C.

What about n = 11? I did some cases analysis and solved it with bipartite matching only but one can run algo described mincost multiple times — for each line we set desired number of fours as either 44 - 47 or 74 - 77.

my implementation

Hard — SubRectangles

Let's say H2 = W2 = 4. You can see that t[1][1] - t[5][1] = t[1][5] - t[5][5]. Then we can deduce that for each pair (a, b) where 0 ≤ a, b < 4 one of two holds:
1. t[x][y] = t[x + 4][y] if x%4 = a and y%4 = a
2. t[x][y] = t[x][y + 4] if x%4 = a and y%4 = a
For all possible ways to assign types to 16 cells we will calculate result and sum them up. So we consider 2¹⁶ bitmasks.

For first type of cells (with condition t[x][y] = t[x + 4][y]) we should set all cells of this type in first four columns — columns on the right will be the same. We should do it in such a manner that numbers of tokens in 1-st, 5-th, 9-th, ... rows are equal. The same for 2-nd, 6-th, ... and so on. Let's look at first set of rows (1-st, 5-th, ...). We should iterate over number of tokens we want to put in this "type" of rows. For each value we sum/multiply up some binomial coefficient powered up to number of rows of this type. E.g. for H = 14 there are 4 rows in this group, so if we have 2 possible cells here (number of lighten bits in bitmask) and we want to put 1 token in each row, then we have bin(2, 1)⁴. The same for the second direction but with some inclusion-exclusion formula. You can read my implementation.