All submissions for this problem are available.
Chef recently took up painting. He likes painting pictures, but is always thinking of ways to make painting more efficient. Chef begins with a square canvas, initially painted completely white. He paints one rectangle at a time, where every edge must have integer length, and 2 edges of the rectangle must be parallel to the horizontal axis. When Chef paints a rectangle, he paints it in one of the following ways:
- White - paint the entire rectangle white
- Black - paint the entire rectangle black
- Flip - All white paint inside the rectangle becomes black, and all black paint becomes white
Chef wants your help in order to paint as few rectangles as possible. You will be given the final picture that Chef intends to paint. You must come up with a plan to paint the picture. Chef knows this is a difficult problem, so he isn't requiring optimal solutions, but the fewer rectangles you use the more points you will score.
Input will begin with an integer N, the size of the painting. N lines follow with N characters each, describing the picture chef wishes to paint. The top-left corner is (0, 0), the top-right corner is (0, N−1), the bottom-left corner is (N−1, 0), and the bottom-right corner is (N−1, N-1). A 'W' character indicates the corresponding cell of the painting is white, and a 'B' character indicates the cell is black.
First output an integer L, the number of rectangles in your solution. This number must not exceed N2. Then output L lines. Each line should consist of 2 pairs of integers followed by a 'W', 'B', or 'F' character. The first pair of integers is the (row, column) coordinates of the upper-left corner of the rectangle, and the second pair is the (row, column) coordinates of the bottom-right corner. The final character indicates the operation to perform on the rectangle, 'W' for white, 'B' for black, and 'F' for flip.
10 ≤ N ≤ 50 (excepting Sample Input)
All official inputs are generated by the method described in Test Generation.
Your score for each test file is 10*L/N2. Your overall score is the average of your scores on the individual test files. The goal is to minimize your score.
5 BWBBB BBBWW BBWWB BBWWB WBBBW
5 0 0 3 4 B 2 2 4 3 F 4 1 4 1 B 0 1 0 1 W 1 3 1 4 W
The painting of the grid proceeds as follows:
WWWWW WWWWW WWWWW WWWWW WWWWW BBBBB BBBBB BBBBB BBBBB WWWWW BBBBB BBBBB BBWWB BBWWB WWBBW BBBBB BBBBB BBWWB BBWWB WBBBW BWBBB BBBBB BBWWB BBWWB WBBBW BWBBB BBBWW BBWWB BBWWB WBBBW
This sample output would score 10*5/52 = 2.
We have 50 official test cases, each of them is created as follows:
An integer N is chosen from [10, 50] uniformly at random. An real value p is chosen from [0.4, 0.6] uniformly at random. Then each cell is independently chosen as 'B' with probability p, 'W' with probability 1 − p.
|Tags||ad-hoc, challenge, feb13, pieguy|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.