PROBLEM LINK:
Author: Dmytro Berezin
Tester: Jingbo Shang
Editorialist: Ajay K. Verma
DIFFICULTY:
Challenge
PREREQUISITES:
Ad-hoc, Randomized Algorithm
PROBLEM:
We are given an N x M rectangle, where some of the cells are already colored. The goal is to color the remaining cells in minimum number of steps, where in a single step a maximal set of contiguous uncolored cells, aligned horizontally or vertically, can be colored.
EXPLANATION:
This is a challenge problem and there is no exact solution. A greedy algorithm could be to scan the cells in a row major order, and whenever an uncolored cell is encountered, either color a maximal row starting at this cell, or color a maximal column starting at this cell, whichever colors most number of cells.
void greedy() {
for (int i = 1 to N) {
for (int j = 1 to M) {
if (a[i][j] is colored) continue;
int x = 0;
for (int k = j to M) {
if (a[i][k] is colored) break;
++x;
}
int y = 0;
for (int k = i to N) {
if (a[k][j] is colored) break;
++y;
}
if (x > y) {
for (int k = j to (j + x))
color(a[i][k]);
} else {
for (int k = i to (i + y))
color(a[k][j]);
}
}
}
}
Of course there is no reason to traverse the cells in row major order, one could also traverse them in a column major order, or in decreasing row/column major order. Apply the greedy approach for each of them and pick the one which uses minimum number of steps.
We could go even further: After each coloring, we can pick one of the four traversal orders randomly, and then traverse the rectangle cells in that order to find the first uncolored cell. We can run this randomized version of greedy approach as long as time permits, and then pick the one which gives the best result.
In order to increase the number of random trials, we may want to increase the speed of our greedy approach. There are three main steps in the greedy approach:
- find the first uncolored cell: could take O (NM) time, however, if we store the pointer from the previous iteration, it will take O (1) amortized time.
- find the length of the maximal uncolored row/column starting at this cell: could take O (N + M) time,
- color the row/column: could take O (N + M) time.
If we use (N + M) segment trees, one for each row and one for each column. The complexity of some of the steps can be reduced. The first step can be reduced to O ((N + M) lg (N + M)), the second step can be reduced to O (lg (N + M)), while the complexity of the third step will increase to O ((N + M) lg (N + M)).
One could also try representing the rows and columns of rectangle using bit masks, and use bit twiddling tricks to perform the three steps, which will also reduce the runtime of a single trial.
I did not manage to look at the top solutions very carefully, and it would be great if people could come forward and explain their approaches.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution will be put up soon.