EFFPAINT - Editorial

[pragrame]

Problem Link:

Practice

Contest

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

[jaskaran_1]

Could somebody tell me where I was going wrong in my approach.I used the naive algo of just painting black squares but it showed wrong answer.
http://www.codechef.com/viewsolution/1816615

[vineetpaliwal]

@jaskaran_1 : Just see your answer for sample input or any other small example , your answer is obviously coming wrong . The input starts with size of square . There is a new line character after that . Therefore after you read N with scanf add a getchar() to your code . Then it gives correct answer as I have verified .

[tijoforyou]

@jaskaran_1 YOu can use http://ideone.com to compile and run your codes online. ideone also uses SPOJ, just like codechef does. So, you can check and verify the correctness your codes for some sample inputs there.

PS: However, for a question, getting correct answer for some particular test case does not always mean, the program is correct. First, you must ensure the correctness of your algorithm as well. (In this case, your algo was right, only some programming language issues).

[mugurelionut]

About using (mostly) F operations: At some point during the contest there were 3 solutions tied at a score of 1.357354 (apia’s, mukel’s and aurinegro’s solutions) and I was very curious what was so special about that score. When there were about 10 hours left from the contest I was also able to reach this score and I believe that this was the score which either consisted of only F operations chosen properly or only F operations and a few B operations (that was my case: when there were just a small number of black cells, I was covering them using a minimum rectangle cover). Anyway, the point is that at that score my solution was able to almost always use a number of rectangles equal to the minimum possible number of flip rectangles (which is (the number of corners with odd parity)/4 plus, eventually, one more rectangle if the number of corners with odd parity is not divisible by 4).

After (finally) reaching the 1.357354 score I continued optimizing my solution by noticing that I could “cancel” more corners with odd parity by using a combination of black rectangles followed by flip rectangles + a minimum rectangle cover. For instance, think about a “grid” of P “horizontal” black rectangles and Q “vertical” black rectangles. These P+Q black rectangles have 4x(P+Q) corners and may have up to 4xPxQ intersection points (if every “horizontal” rectangle intersects every “vertical” rectangle in 4 points). All of these 4x(P+Q+PxQ) points will have their parity changed (if you now assume that the starting board is not the all-white board but the board after placing the P+Q black rectangles). Thus, by using such a grid, each of the P+Q black rectangles could cancel on average (and in the best case) 4x(P+Q+PxQ)/(P+Q)=4+4xPxQ/(P+Q) corners with odd parity (this value can be significantly greater than the value 4 associated to a flip rectangle).

However, in my solution I was only able to implement this idea for P=Q=1 (forming a cross of 2 black rectangles) to which I would add extra black rectangles if they cancel more than 4 corners with odd parity - i.e. they are better than using a flip rectangle). Such a cross consists of 2 black rectangles and may cancel 12 corners with odd parity (thus, 6 corners per rectangle on average). Subsequent black rectangles were able to cancel 6 or 8 corners with odd parity in my solution (although, at least in theory, a higher number of corners with odd parity per black rectangle could have been achieved if the black rectangles were properly chosen). On my test cases I was usually able to use an initial cross plus 0, 1 or (in some rare cases) 2 extra black rectangles, after which I would run a modified version of the mostly flips solution (it had to be modified because cells which were covered by the initial black rectangles had to be handled in a somewhat special manner). My final score was 1.319525.

I would be very interested in knowing the solutions of the other contestants who managed to get past the 1.357354 score: ACRush, apia, mukel and stzgd.

[jorgeilc]

thanks for your answers, I decided I had several questions

[ACRush]

1. Let’s start by the approach using only F operations, that’s trying to remove as many as “odd corners” (= the corner to which an odd number of black cells next) using one operation.

Notice that one F operation is to flip all four corners. So, the greedy algorithm (the same as setter’s solution) gives a 1.38 score. Actually, by adding some randomness, we can have about 1.33.

2. Continue with the idea for removing “odd corners”, we can run “matching”(not biparti) algorithm on each row, to minimize the number of F operations required for the current row. Build graph : for each pair of “odd corners”, we add one edge if and only if there exists an F operation flips these two corners and another two “odd corners”.

By this, we can improve the score to about 1.28.

3. We can add a few B and W operations if the operation can reduce the number of “odd corners” by 6, 8, 10…(more than 4 is good, since one F operation can only get at most 4).

Notice that, we can not do this (can not exceed 4) at the very beginning, but it becomes feasible after a few F operations. With this technique, we can improve the score to about 1.21.

One more thing, the above can be done in O(n^3) each iteration, actually, we can do it faster.

4. Some heuristics, get about 1.15.

*) Beam search. Minimize the ((number of “odd corners”) + 4 * (operations already used)).

*) Choose the row with fewer “odd corners” first.

*) Run dynamic programming when only 5 rows left.

Last thing : In IOI2002, there is a similar problem called XOR, though it’s a output-only problem.

[akshitpoddar]

" One can greedily pick rectangles that have all four corners with odd parity, then pick ones that have three corners with odd parity. " … Can you explain , how all the odd parities would be turned off by just 2 passes . In the first pass , all four corner odd parities would be turned off . In the next pass , all three corners with odd parity would be turned off , however the fourth would be flipped as well . How is it that all odd parities would be flipped ?

[risen_again]

I do not understand how is this editorial solution working. Can somebody please explain what is the intuition behind considering parity or link to some article regarding importance of parity in such question? Also the editorial author has not defined corners. “This is because, if you consider a corner outside the rectangle, then it is left unaffected. If … move thus flips that corner’s parity.” This paragraph is so confusing. How can a corner be on edge and another inside rectangle? Please somebody explain all these things.
@acrush @mugurelionut @vineetpaliwal

[bugkiller]

You made 25 * 24 submissions for this problem? You kidding me? or scaring me!?! This is huge! :-o

[mugurelionut]

@bugkiller: I made most of my submissions after reaching a score below 1.40. My solution had several parameters that I could tune and at that score it became difficult to evaluate the best values for these parameters using my tests only. So what I usually did was to send multiple submissions (2-3) at about the same time, but with different values for one of the parameters - then I would pick the value for which I would get the best score and continue from there (changing the value of another parameter and so on). Every now and then I also changed the algorithm in order to improve my score.