11514 - Batman

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

11514 - Batman

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
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

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

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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

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: Select all

``````Accepted!  Thanks.  Note villains must be killed with one shot, using up all power.
}``````
}[/code]
Last edited by baodog on Fri Oct 03, 2008 8:32 am, edited 1 time in total.
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

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[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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com
wallace
New poster
Posts: 10
Joined: Thu Feb 26, 2009 4:03 pm

Re: 11514 - Batman

hi!
i tested with the case test of exercise, but i got wa!
somebody could write some cases test?
thank you!
wallace
New poster
Posts: 10
Joined: Thu Feb 26, 2009 4:03 pm

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?
Khongor_SMCS
New poster
Posts: 15
Joined: Thu Jun 18, 2009 12:01 pm
Contact:

Re: 11514 - Batman

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?
Because you must destroy villains and use powers input order.