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

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

11514 - Batman

Post by Leonid » Thu Oct 02, 2008 11:07 pm

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

Post by Leonid » Fri Oct 03, 2008 12:58 am

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

Post by baodog » Fri Oct 03, 2008 4:09 am

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.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11514 - Batman

Post by andmej » Fri Oct 03, 2008 5:32 am

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

Post by wallace » Sun May 31, 2009 6:11 am

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

Post by wallace » Mon Jun 01, 2009 5:18 am

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

Post by Khongor_SMCS » Tue Jun 23, 2009 2:45 pm

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.

Post Reply

Return to “Volume 115 (11500-11599)”