## 11098 - Battle II

Moderator: Board moderators

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

### 11098 - Battle II

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:
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.

lbfacci
New poster
Posts: 4
Joined: Wed Nov 02, 2005 7:28 pm
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
any idea to solve this problem?

thanks a lot.
Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
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
Contact:
I keep getting WA.
SPOILER:

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
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
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
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
Contact:
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.
FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
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

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.