11230 - Annoying painting tool

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11230 - Annoying painting tool

Post by cmd »

How solve it?
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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

Post by cmd »

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

Post by sohel »

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

It's quite strange that very few people tle on this one.
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

Anyway, I originally thought naive algorithm TLE, so I came up with something that's O(n m logn logm)
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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
Location: Calgary, Canada

Post by Darko »

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

Post by Wei-Ming Chen »

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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.
Post Reply

Return to “Volume 112 (11200-11299)”