11230 - Annoying painting tool

cmd · Post by **cmd** » Sun Jul 08, 2007 12:53 am

How solve it?

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Jul 08, 2007 3:29 am

Hint: for each possible position of a painting operation, you will select it at most once for painting, and the order in which you do the painting operations doesn't matter, so you can do the operations in order by row and column.

cmd · Post by **cmd** » Sun Jul 08, 2007 11:34 am

thanks.
I'm think, that it can be solved by linear equations set by mod 2.
But i don't know how solve this kind of equations set..

sohel · Post by **sohel** » Sun Jul 08, 2007 11:40 am

No need to solve any equation for this problem.

Go over Adrian's Hints again and think of the greedy approach!

sclo · Post by **sclo** » Sun Jul 08, 2007 1:07 pm

It's quite strange that very few people tle on this one.

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Jul 08, 2007 1:14 pm

Why? The naive algorithm takes (n-r)*r*(m-c)*c steps, which is at most 50^4.

sclo · Post by **sclo** » Mon Jul 09, 2007 12:08 am

Anyway, I originally thought naive algorithm TLE, so I came up with something that's O(n m logn logm)

Adrian Kuegel · Post by **Adrian Kuegel** » Mon Jul 09, 2007 12:19 am

O(n * m) is also possible, but since this should be an easy problem in the problemset of our local contest, I used such a low limit for n and m so that the naive algorithm runs in time.

Darko · Post by **Darko** » Wed Jul 11, 2007 2:17 am

I also thought that it would time out, so I went to sleep (was an hour late anyway and it was 4am...)

When I looked at the problem again I realized the naive solution would pass, so I coded it. I can see how to speed it up using bitmasks, but I can't figure out how to do it in O(n*m). Any hints?

Wei-Ming Chen · Post by **Wei-Ming Chen** » Wed Jul 11, 2007 5:21 am

When I looked at the problem again I realized the naive solution would pass, so I coded it. I can see how to speed it up using bitmasks, but I can't figure out how to do it in O(n*m). Any hints?

Well, in my method, I didn't do the "same change" more than one time

I tried to change every block to the right color in a special order
column first, and row next (row first and column next is also possible)

Each change make sure of one block on the right color and it wouldn't be changed again in the changes after.

I think it is the same method as Adrian Kuegel's in the top of this page

Adrian Kuegel · Post by **Adrian Kuegel** » Wed Jul 11, 2007 9:19 am

Well, you just describe the greedy everyone uses. But if you implement this naively, it will be O(r*(n-r)*m*(m-c)), because each time when you apply the operation it takes r * c steps.
The idea how to get O(n*m) is to store how many operations have been applied with the top left corner in one of the first i rows and j columns. With this information it is possible to answer in constant time how many operations
covering a pixel have been applied.