## 11230 - Annoying painting tool

Moderator: Board moderators

cmd
New poster
Posts: 4
Joined: Sun Jul 08, 2007 12:44 am

### 11230 - Annoying painting tool

How solve it?
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
New poster
Posts: 4
Joined: Sun Jul 08, 2007 12:44 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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
No need to solve any equation for this problem.

Go over Adrian's Hints again and think of the greedy approach!
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
It's quite strange that very few people tle on this one.
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Why? The naive algorithm takes (n-r)*r*(m-c)*c steps, which is at most 50^4.
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Anyway, I originally thought naive algorithm TLE, so I came up with something that's O(n m logn logm)
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 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
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
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.