11008  Antimatter Ray Clearcutting
Moderator: Board moderators
 Martin Macko
 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)

 Experienced poster
 Posts: 161
 Joined: Tue Oct 25, 2005 8:38 pm
 Location: buet, dhaka, bangladesh
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 np 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
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 np 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

the world is nothing but a good program, and we are all some instances of the program
No, it's wrong. Consider for example the trees, arranged as follows, you want to cut all of them:
Optimal solution has 4 lines: 07A, 258, 369, 14.
Your algorithm under some conditions could initially choose these lines: 035, 247; and then it'll need 3 more lines, for a total of 5 lines.
Code: Select all
.012..
.3.4..
.567..
8.....
....9A
Your algorithm under some conditions could initially choose these lines: 035, 247; and then it'll need 3 more lines, for a total of 5 lines.
Re: 11008  Antimatter Ray Clearcutting
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 12 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).
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 12 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).
Re: 11008  Antimatter Ray Clearcutting
Can you please elaborate your approach slightly ?