11337 - Greatest Hits!

All about problems in Volume 113. 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
shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:
Contact shakil

11337 - Greatest Hits!

Post by shakil »

Why WA.Please give some sample input and output.

Code: Select all

Cut after AC.
Top
shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:
Contact shakil

Post by shakil »

I think , this problem can not solve by DP.Are any one solved it using DP.
SHAKIL
Top
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
Contact sclo

Post by sclo »

I just looked at the bound and thought about backtracking. I never really consider any dp. Actually now I don't see how it can be done using dp.
Top
baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Classical DP problem

Post by baodog »

This is classical DP problem of knapsack variety !!!
I used my knapsack template for this problem (only a few lines change).
I get 20ms using DP.
The dataset is a bit weak ... so brute force
backtracking also works.
Top
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
Contact sclo

Post by sclo »

I was stupid for not thinking about the dp. Anyway, I think the backtrack is quicker to code than dp anyway.
Top
Post Reply

Return to “Volume 113 (11300-11399)”