11088 - End up with More Teams

SRX · Post by **SRX** » Sun Sep 10, 2006 12:09 pm

I have solved this problem with backtracking .

But I have some questions .
Can we solve it with greedy algorithm ?
Can someone give me some cases that greedy algorithm dosen't work ??

thanks

little joey · Post by **little joey** » Sun Sep 10, 2006 12:56 pm

Why don't you just try?
You have a working solution and it is not too difficult to create random I/O for this problem and test your alternative, greedy solution if the judge says it fails.

Not all problems have to be spoiled by strong hints and/or critical I/O in the forum. There is room for people to be creative themselves.

rammestain · Post by **rammestain** » Sun Sep 10, 2006 8:34 pm

I solved this problem greedy, and I got WA , please give me some test cases. I myself could'nt find

sclo · Post by **sclo** » Mon Sep 11, 2006 3:01 am

There is also a dp solution but it is probably slower than backtracking. The observation is that if we have >=3 people to choose from, then we can try to choose the highest first (greedy), but the choice of the second and third person of the team are not greedy. It is not hard to come up with examples that illustrates this.

vinay · Post by **vinay** » Mon Sep 11, 2006 4:43 pm

is it that ppl who solved it in less than 1s or .002 sec have solved it using backtracking..
I myself solve it using dp... more apt would be memoization...

I takes >1s ,precisely 1.094..

Cho · Post by **Cho** » Mon Sep 11, 2006 5:14 pm

I solved it with backtracking.

vinay · Post by **vinay** » Mon Sep 11, 2006 5:36 pm

and what was ur run time...
I have now the run time as 1.012 s..

Cho · Post by **Cho** » Mon Sep 11, 2006 6:46 pm

0.002

helloneo · Post by **helloneo** » Mon Sep 11, 2006 7:24 pm

rammestain wrote:I solved this problem greedy, and I got WA , please give me some test cases. I myself could'nt find

Try this one..

Code: Select all

9 
7 7 6 13 13 14 1 1 1

The answer should be 3

rammestain · Post by **rammestain** » Mon Sep 11, 2006 10:55 pm

thank u very mauch, but my program gives right answer to it,
I really got confused with this

LIBe · Post by **LIBe** » Tue Sep 12, 2006 2:51 am

vinay wrote:is it that ppl who solved it in less than 1s or .002 sec have solved it using backtracking..
I myself solve it using dp... more apt would be memoization...

I takes >1s ,precisely 1.094..

I tried it using back-tracking, and DP like O(2^n), but I got TLE

I want to show your solution - that is, how to solve it using back-tracking... or memoization

Larry · Post by **Larry** » Tue Sep 12, 2006 6:34 am

Seems like most of the memo's got around 1 second. Just memo on the state..

LIBe · Post by **LIBe** » Tue Sep 12, 2006 7:43 am

Larry wrote:Seems like most of the memo's got around 1 second. Just memo on the state..

I got AC in 0.023 using memoization

thx...

vinay · Post by **vinay** » Tue Sep 12, 2006 11:39 am

why is backtracking so fast

kp · Post by kp » Tue Sep 12, 2006 1:36 pm

I solved it using both DP and greedy.

Greedy is as follows:
1. Take one guy with maximum value
2. Take two appropriate guys with minimum sum of values

However, I have not proved it.