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) ?
11514  Batman
Moderator: Board moderators
Re: 11514  Batman
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
imply that we can't use the same power twice?
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.
Re: 11514  Batman
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]
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.
}
Last edited by baodog on Fri Oct 03, 2008 8:32 am, edited 1 time in total.
Re: 11514  Batman
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[i1][j] (Do not use this power. We must kill the j villains using the first i1 powers).
2. dp[i1][j1] + 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.
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[i1][j] (Do not use this power. We must kill the j villains using the first i1 powers).
2. dp[i1][j1] + 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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
Re: 11514  Batman
hi!
i tested with the case test of exercise, but i got wa!
somebody could write some cases test?
thank you!
i tested with the case test of exercise, but i got wa!
somebody could write some cases test?
thank you!
11514  Batman
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?
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?

 New poster
 Posts: 15
 Joined: Thu Jun 18, 2009 12:01 pm
 Contact:
Re: 11514  Batman
Because you must destroy villains and use powers input order.wallace wrote: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?