нет

You are not alone, it happened to me quite often...

For example you can reduce it to project selection problem, where white pieces are projects and empty cells adjacent to them are equipments.

It is equivalent to finding minimal vertex coverage in bipartite graph with on '.' and 'o' with edges between adjacent cells and answer is {number of '.' and 'o'} — {coverage size}.

I believe I had an almost correct solution, though I couldn't debug it in time.

We can notice that it's always better to leave fewer cells after the chosen one. So, DP: d_k, x~--- minimal number of cells left after k moves if the chosen cell ends up in position x. The transitions are clear: we must take all possible rectangles not containing the chosen cell and very carefully count how many cells before and after chosen cells they contain. We can reduce number of transitions to O(n) via moving rectangles to some border when possible.

It suffices to notice that four moves are always enough to win. So, this solution is O(n²).

Look at this thought:

If you have some i,j such that planet corresponds to A[i] is exact same planet that to B[j], then there are have to be some ratioA and ratioB such that ratioA*A[i] == ratioB*B[j]. Lets put all elemets of A multiplied by ratioA to setA <- ratioA*A[i]. And do the same for another array: setB <- ratioB*B[i].

What you want to do? You want to find such ratioA and ratioB that merged-set ResultSet = Merge(setA,setB) have the smallest possible size Size(ResultSet) -> min.

Since size of A and B is not more than 50 elements per each, you can check wise ratioA and ratioB for all i and j for O(n^2) and find size of ResultSet in O(n) [or even in O(log n), if you would use binary check of presence, which is not so important, but still is fun].

So what ratioA and ratioB would be wise to choose for some i and j? Of course, ratioA = LCM(A[i],B[j]) / B[j] and ratioB = LCM(A[i],B[j]) / A[i].

Final estimate is O(n^3) [or O(n^2 log n)].

Cheers.

Division 1 950's editorial is complete.