11514 - Batman

[Leonid]

I've got some questions about the task.
First, I assume that it is possible to use the same weapon twice against different villains. Is it right?
Second, I assume that the list of weapons which can be used to defeat a villain is not empty. I don't think this assumption is right according to the problem description, but I think input does not contain cases like that. Otherwise I believe it would have been mentioned in the problem description.
Third, is it possible to solve the task faster then O(n^2 * m) ?

[Leonid]

Ok, finally after 6 WA I solved the task.
Initially I assumed that the same power may be used twice to get rid of more than one villain.
But this assumption proved to be wrong. Does

Code: Select all

Batman must use the powers of his list in order (possibly skipping some powers) and have to beat all the villains in the same order of the list.

imply that we can't use the same power twice?

[baodog]

How did you solve it? what's your complexity? Thanks!
I use sophisticated branch and bound + memorization of best energy for # of villains x powers left, but get TLE.

My code is below

Code: Select all

Accepted!  Thanks.  Note villains must be killed with one shot, using up all power.
}

}[/code]

[andmej]

I solved it in O(n^2) with this approach, although it is rather slow, ~4 seconds:

dp[j] = Minimum energy needed to kill first j villains having selected some powers from the first i powers.

dp[0] = 0 (I don't need any energy to kill zero villains). (0 <= i <= no. of powers)
dp[0][j] = infinity (It's impossible to kill some villain without using any power). (1 <= j <= no. of villains)

And dp[j] = Minimum of two choices:

1. dp[i-1][j] (Do not use this power. We must kill the j villains using the first i-1 powers).
2. dp[i-1][j-1] + energy_of_power. (Use this power to kill this villain. This choice can only be taken when the i'th power can kill the j'th villain, that is when attack_factor >= defense_factor[j] and j'th villain has i'th power in his "sensitivity" list).

This problem is somewhat similar to 3986 - The Bridges of Kolsberg.

Hope that helps.

[wallace]

hi!
i tested with the case test of exercise, but i got wa!
somebody could write some cases test?
thank you!

[wallace]

this case:
4 4 3000
pA 9000 44
pB 9000 100
pC 9000 400
pD 9000 100
Joker 4000 pB
Penguin 8000 pD
TwoFace 6000 pC
feroz 4000 pA
0 0 0



answer: No

why?

[Khongor_SMCS]

this case:
4 4 3000
pA 9000 44
pB 9000 100
pC 9000 400
pD 9000 100
Joker 4000 pB
Penguin 8000 pD
TwoFace 6000 pC
feroz 4000 pA
0 0 0



answer: No

why?

Because you must destroy villains and use powers input order.