11098 - Battle II

[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]

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]

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]

any idea to solve this problem?

thanks a lot.

[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]

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

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

[kalinov]

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]

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]

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]

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]

some more I/Os please, I got RE at 0.080s

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