11098 - Battle II

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

Post Reply
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

11098 - Battle II

Post by little joey »

A real nice problem, but what a crappy description:
A bomb b1 is in destruction range of another bomb b2 if distance of b2 from the perimeter of b1 is less than the range of b1. (i.e. b2.range + b1.radius + b2.radius >= Distance(b1.center, b2.center))
The first part of this sentence contradicts the second part in two ways: 'less than' vs. '>=', and 'range of b1' vs. 'b2.range'.
The ith bomb in the sequence should not result explosion of the jth bomb where j > i.
I had a hard time understanding this sentence, but eventually I think it means: 'A bomb in the sequence should not set off another bomb that appears later in the sequence'. Correct, but unnecessary: how could you manually set off a bomb that has already exploded?

A specification of the input ranges would have been nice. Even when all co-ordinates, radiusses and ranges are limited to 32-bit signed integers, some intermediate calculations could exeed the range of 64-bit integers (when calculating the square distance).

I guessed that the bombs where numbered from zero in the order given in the input, which turned out to be correct. But why not spend one more sentence in the description to take away all doubts?

Again: A very nice and original problem, but I would strongly advise the problemsetter to improve the description and have it replaced.
smile2ka10
New poster
Posts: 13
Joined: Wed Oct 26, 2005 10:14 pm
Location: Iran
Contact:

Post by smile2ka10 »

We will revise the problem statement, regarding your suggestions soon.

But some points:
The first part of this sentence contradicts the second part in two ways: 'less than' vs. '>=', and 'range of b1' vs. 'b2.range'.
'range of b1' should be replaced with 'range of b2', but the comparisons are correct.
I had a hard time understanding this sentence, but eventually I think it means: 'A bomb in the sequence should not set off another bomb that appears later in the sequence'. Correct, but unnecessary: how could you manually set off a bomb that has already exploded?
I agree with the fact that this consideration can be obtained from the problem statement, but I think it would not cause any misunderstandings.
A specification of the input ranges would have been nice. Even when all co-ordinates, radiusses and ranges are limited to 32-bit signed integers, some intermediate calculations could exeed the range of 64-bit integers (when calculating the square distance).
All necessary calculations will fit in 32 bit integer. We will add this sentence to the problem statement.
I guessed that the bombs where numbered from zero in the order given in the input, which turned out to be correct. But why not spend one more sentence in the description to take away all doubts?
You are right.

Thanks for your suggestions.
lbfacci
New poster
Posts: 4
Joined: Wed Nov 02, 2005 7:28 pm

Post by lbfacci »

Quote:
I had a hard time understanding this sentence, but eventually I think it means: 'A bomb in the sequence should not set off another bomb that appears later in the sequence'. Correct, but unnecessary: how could you manually set off a bomb that has already exploded?
I agree with the fact that this consideration can be obtained from the problem statement, but I think it would not cause any misunderstandings.
Actually, at first, I misunsderstood this sentence. I thought that the i_th bomb could not be exploded by the sequence started with the explosion of the j_th bomb, where j < i.

Either way I wouldnt be able to code it in time (I still havent tried), but I agree with 'little joey'.
lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone »

any idea to solve this problem?

thanks a lot.
Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon »

Hint:

think about how to solve this problem if our input graph is DAG,
then we can make an observation that allowed us to transform input graph to DAG. (in first part think about binary search)
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

I keep getting WA.
SPOILER:
Cut..... I already got AC. :D

But anyway,
Summary of my algorithm:
1. compute strongly connected components to get DAG.
2. determine which bomb that should be manually exploded in each SCC.
3. pick bombs that must be maunally exploded
4. try to pick additional bombs to decrease average
5. output correct order to manually set off bombs
Last edited by sclo on Tue Sep 26, 2006 12:43 am, edited 4 times in total.
kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia

Post by kalinov »

sclo wrote: Is the following algorithm correct?
The algorithm is correct.
What algorithm for finding SCCs are you using? Tarjan's DFS-based algorithm is great for this problem because it generates components in topologicaly sorted order, but (I think) many people make bugs when calculating 'lowlink number' for some node.
So, if you use that method, check your algorithm with some paper discribing the algorithm.
If that's ok, then probably you have some silly bug that you'll have to find on your own.
Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon »

I think it is very good algorithm :-) But I used binary search to guess average cost instead of your steps 3. and 5. But it seems that your method is better.
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

I also think your algorithm is correct, although my steps were in a slightly different order.

It is not so difficult to write a brute-force program for cases with a small number of bombs: just try all different explosion orders (max N!) and find the minimum average cost. Now also calculate the average cost from the solution your (real) program finds and compare these two. If they differ, you know your implementation is wrong.

I had to make a test file with 1000 random cases with 10 bombs, before I found a difference between my real program and my bruteforcer. But it made me find the bug in my code.

The case where my initial program failed was:

Code: Select all

1
10
6 1 3 2
21 5 9 9
21 4 9 1
40 17 5 8
27 0 4 8
20 24 2 9
46 31 0 4
42 22 2 0
25 35 2 9
40 42 8 3
The minimum average cost of exploding all bombs is 1.6666667.
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

Thanks for the replies. It was in fact a stupid bug, I forgot to clear some of my array. :-?
Should I remove my spoiler?
For computing SCC, I used the algorithm found in CLRS (Kosaraju's alg). It also has the property that the SCC are returned in reverse topologically sorted order.
See also http://en.wikipedia.org/wiki/Strongly_c ... _component
FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ »

some more I/Os please, I got RE at 0.080s :(
ahyangyi
New poster
Posts: 1
Joined: Tue Jun 30, 2009 2:11 pm

Re: 11098 - Battle II

Post by ahyangyi »

Here's a generated test case that got my code wrong:

Code: Select all

1
7
24 1 4 7
38 33 4 3
13 13 2 0
34 1 0 0
6 25 5 4
1 14 3 7
30 35 1 6
output contains 0 1 2 3 5 6.
Post Reply

Return to “Volume 110 (11000-11099)”