×

Challenge

# 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

This question is marked "community wiki".

973568379
accept rate: 14%

 13 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. answered 20 Feb '13, 06:17 7★ACRush ♦ 897●5●6●7 accept rate: 0%
 0 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 answered 16 Feb '13, 19:16 525●23●35●50 accept rate: 0%
 0 @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 . answered 16 Feb '13, 20:40 12.4k●47●107●171 accept rate: 12%
 0 @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). answered 16 Feb '13, 21:21 4.2k●5●23●64 accept rate: 15%
 0 " 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 ? answered 24 Feb '13, 18:25 1 accept rate: 0%
 0 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 answered 10 Feb, 16:19 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×947
×847
×13
×1

question asked: 16 Feb '13, 18:31

question was seen: 4,172 times

last updated: 10 Feb, 16:21