Problem Link:
Difficulty:
Challenge
Pre-requisites:
Ad-hoc
Problem:
You are given a NxN board, some cells of which are black, and others are white. Starting from a blank board (all cells white), you wish to reach this target board by repeatedly picking rectangles and painting them either (a) white (b) black or (c) flipping the white and black cells in the rectangle. Your goal is to minimize the number of operations.
Explanation:
Naive approach:
For every black cell, paint just that cell. You will take at most N^2 cells to paint, so this will get you AC. (This gives a score of 10 points)
You can slightly improve this approach by counting whether white cells or black cells are more. In case white cells are more, just individually paint black ones. In case black cells are more, then first paint the whole board black in 1 step, and then paint each individual white cell. (This one gives a score of 4.5)
Approach using only âFâ moves:
Here, instead of concentrating on cells to pick, consider corners of the cells. Either they have an odd number of black cells next to them, or an even number. Consider these parities. When you pick a rectangle and use an âFâ move, exactly the 4 corners of the chosen rectangle have their parity changed.
This is because, if you consider a corner outside the rectangle, then it is left unaffected. If you consider a corner on an edge, it is adjacent to 2 cells inside, and flipping both of them is not going to change the parity of the corner. Similarly for the case where the corner is in the interior of the rectangle. However, if you consider a corner of the rectangle, it is adjacent to just the one cell, and the flip move thus flips that cornerâs parity.
One can greedily pick rectangles that have all four corners with odd parity, then pick ones that have three corners with odd parity. This is greedy, and there exist better ways to search for rectangles such that you end up flipping the parities as required.
Depending on what method you use to choose your rectangles, this method can give a score of 1.36 or less.
Setterâs Solution:
Can be found here
Testerâs Solution:
Can be found here