11008 - Antimatter Ray Clearcutting

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

Moderator: Board moderators

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

Post by C » Thu May 25, 2006 11:54 pm

..my code has passed all the inputs above, but i still got WA. Is there any tricky cases ??... I feel helpless..

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun May 28, 2006 8:13 pm

C wrote:..my code has passed all the inputs above, but i still got WA. Is there any tricky cases ??... I feel helpless..
I don't think there are any more tricky cases... If you're still getting WA, you can try to post your code here...

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sat Jun 03, 2006 9:20 pm

Is this algorithm correct?
first we have n trees. now using dfs we find the line with the maximum number of trees(say p). if we have any other line with p trees we may choose anyone. fire those p trees. now we have n-p trees. with the same process now we find the best line with the maximum number of trees and fire as before until only m remaining.
is this process correct? if not please tell my why
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Jun 03, 2006 9:45 pm

No, it's wrong. Consider for example the trees, arranged as follows, you want to cut all of them:

Code: Select all

.012..
.3.4..
.567..
8.....
....9A
Optimal solution has 4 lines: 0-7-A, 2-5-8, 3-6-9, 1-4.
Your algorithm under some conditions could initially choose these lines: 0-3-5, 2-4-7; and then it'll need 3 more lines, for a total of 5 lines.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sat Jun 03, 2006 9:56 pm

oh, thank you very much for the wonderful example, i knew from previous posts that something like greedy wont work, but i could not find a good counter-example.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 11008 - Antimatter Ray Clearcutting

Post by Sedefcho » Sat Jan 24, 2009 5:48 pm

With the risk of reviving this very old forum thread I want to proudly
mention :) that I got my first ACC on this problem almost 3 years
after I first posted some pretty confused thoughts of mine (above).

I got back to this problem by pure chance and this time
(after doing some thinking in the last 1-2 days in order to
again understand the problem) I finally managed to
solve it (0.180 seconds in java) :)

I have used backtracking (instead of DFS), the rest
is the same as many people mentioned above
(simple geometry, bitmasks, memoization).
I don't think I have used any DP though.

This has been a pretty good problem, not saying
this just because I finally solved it, but because
of the many different techniques and considerations
involved in it (and in its solution).

ankit1990
New poster
Posts: 1
Joined: Tue Jan 03, 2012 7:26 am

Re: 11008 - Antimatter Ray Clearcutting

Post by ankit1990 » Tue Jan 03, 2012 9:53 am

Can you please elaborate your approach slightly ?

Post Reply

Return to “Volume 110 (11000-11099)”