You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFPNT-Editorial

PROBLEM LINK:

Practice
Contest

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:
1) 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.
2) find the length of the maximal uncolored row/column starting at this cell: could take O (N + M) time,
3) 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.

This question is marked "community wiki".

asked 16 Oct '14, 05:18

djdolls's gravatar image

6★djdolls
2.2k508484
accept rate: 0%

edited 10 Nov '14, 01:41

admin's gravatar image

0★admin ♦♦
19.0k348495531


I used a simple dynamic programming approach which landed me a rank of 26 in this question. I started at the corner (N,M) and then I computed this: dp(N,M)= max ( number of steps to fill the nth row horizontally +dp(N-1,M) , number of steps to fill the mth column vertically +dp(N,M-1) ).

Using these values at each step I either travelled left or up. I applied this same approach from all four corners for improvement. Here is my code: http://www.codechef.com/viewsolution/5107369 I would like to know about dinelia's approach. If anybody could explain

link

answered 16 Oct '14, 09:07

a7i7's gravatar image

5★a7i7
15125
accept rate: 0%

edited 16 Oct '14, 09:14

Can any help to find out the bug.............. http://www.codechef.com/viewsolution/5175799

link

answered 19 Oct '14, 17:29

Shiva_c's gravatar image

1★Shiva_c
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×14,366
×689
×319
×15

question asked: 16 Oct '14, 05:18

question was seen: 1,884 times

last updated: 10 Nov '14, 01:41