Tuesday, November 29, 2011

SRM 595: And now , for something completely different

Believe it or not, I do have a life outside of programming contests. That life, however, involves barely studying Computer Science.

I have a sort of a final today, which overlaps with SRM 525. I always try to organize my subjects to minimize the amount of SRMs I lose. Unfortunately, it was not possible to avoid this overlap. In cases where the overlap is forced, I prioritize the SRM unless the class is very urgent/important. But today that's not the case.

However, I am tired of this, maybe I can't control the overlap, but I can still control my fate. I can still decide to participate in SRM 525. Here is how it goes: I can arrive to the sort of final at 08:30, the SRM starts at 08:02. I do not have the ability of teleportation. So, what I will do is participate until exactly 08:15 AM. That gives me 13 minutes which are statistically enough for me to solve the division 1 easy problem. Also statistically, that might be enough for me to gain rating points.

There are risks. If for some reason I don't manage to solve the problem on time. Or if the medium problem turns out to be more approachable, then the easy won't be enough. Let us see what happens.

Update after the SRM: Experiment went sort of ok.

Div1 300


You have a grid of at most 30x30 cells. There may be coins in each cell. You can move all the coins up, left, down or right in one step. If in any step a number of coins get out of the grid, they are lost forever. Return the minimum number of turns needed to end with exactly K coins. Or -1 if it is impossible.

First of all, note that at the end you will necessarily end with the coins inside one of the sub-rectangles of the grid. Thus if no sub-rectangle contains exactly K coins, it is impossible. If one does, however it is possible. There are w*w*h*h, total sub-rectangles. If one of these rectangles has K coins, then we can try to find the required number of steps to remove the coins in the cells outside it.

Now, for each rectangle we have to count the number of coins. We can actually do it in O(w*h) time. Many people did not notice that the constraints are small enough to allow a total time complexity of O(w*w*w*h*h*h), so they went with a way of counting the number of coins in O(1) time (by first making a matrix of accumulated sums).

Now that we know that a given sub-rectangle has K coins, we need to find the minimum number of steps to remove the coins in the other rectangles. This is similar to just removing rows or columns. First of all, I'd like to point out that we can treat rows and columns separately. Moving horizontally won't affect your requirements to move vertically.

So, we have to make a decision, we will go up a X number of times and down a Y number of times. Minimize (X+Y). What is cool here is that every move up, will add a requirement for a move down (There will be a whole new column that we have to remove). And viceversa. Thus if we first do the moves up required to clear the top rows, we will need to do a similar amount of extra moves down to return the grid to normal before removing the bottom rows.

Long story short, if c id the number of top rows to remove and d is the number of bottom rows. Then the number of moves will be at least (c+d) on top of that, we will need T extra moves, and T is either c or d. It is best to minimize T, and that is done by taking the minimum between c and d.

Now, the same will happen with columns, if you have to remove a left columns and b right columns, the number of steps will be (a + b + min(a,b)).

The rectangle with K coins that needs the minimum number of steps is the overall answer.
....

I then went to the "exam". To my disgrace it started later than I thought so I would have had more time to try the medium problem. During all the waiting time I had a lot of second thoughts about the approach, but I was able to think of many arguments to show that it is correct.

I was able to grab a computer during the challenge phase and tried to open some solutions. My room seemed very solid.

The final result: I passed system tests. The speed in 300 was indeed good enough to gain rating. But I am still in [less than 1900] land, which is not where I feel I should be.

6 comments :

Anonymous said...

How would you do if k = 0 ?

vexorian said...

It cannot be by constraints. But When k can be 0. The algorithm is almost the same but you need to enable "rectangles" with 0 width or 0 height.

When width or height of a rectangle is 0, that means that you are removing all the rows or all the columns, and the formula won't work. But the minimum number of steps is the minimum between c and d or between a and b, respectively.

Some rectangles with non-zero width or height could be the answer, too. The logic too end with the rectangle is the same too: Remove rows or columns.

Unknown said...

So, we have to make a decision, we will go up a X number of times and down a Y number of times. Minimize (X+Y). What is cool here is that every move up, will add a requirement for a move down (There will be a whole new column that we have to remove). And viceversa. Thus if we first do the moves up required to clear the top rows, we will need to do a similar amount of extra moves down to return the grid to normal before removing the bottom rows.


didnt undertand this part

vexorian said...

Ok.

We have the following grid:

xxxxxxx
xooooox
xooooox
xooooox
xxxxxxx

The x represent rows/columns that we would like to "remove". There are some coins in some of the x locations.

We will focus on rows first. Each move does not only remove a row. Let us say we move all the coins up once. This will remove any coin that was in the top row. However, something else will happen with our rectangle:

xooooox
xooooox
xooooox
xxxxxxx
xxxxxxx

There is now a whole new row at the bottom of the grid. So, we will need a new move down to get rid of it.

This means that if we first do moves up then every (move up) we use will add a new (move down) that we will need to use later. And if we begin with moves towards the down direction, the opposite will happen.

ty said...

Maybe this have wrong title 595(of yesterday at now) instead of 525 ?

vexorian said...

Maybe.