Page 1 of 3
11088 - End up with More Teams
Posted: Sun Sep 10, 2006 12:09 pm
by SRX
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
Posted: Sun Sep 10, 2006 12:56 pm
by little joey
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.
Posted: Sun Sep 10, 2006 8:34 pm
by rammestain
I solved this problem greedy, and I got WA , please give me some test cases. I myself could'nt find
Posted: Mon Sep 11, 2006 3:01 am
by sclo
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.
Posted: Mon Sep 11, 2006 4:43 pm
by vinay
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..
Posted: Mon Sep 11, 2006 5:14 pm
by Cho
I solved it with backtracking.
Posted: Mon Sep 11, 2006 5:36 pm
by vinay
and what was ur run time...
I have now the run time as 1.012 s..
Posted: Mon Sep 11, 2006 6:46 pm
by Cho
0.002
Posted: Mon Sep 11, 2006 7:24 pm
by helloneo
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..
The answer should be 3
Posted: Mon Sep 11, 2006 10:55 pm
by rammestain
thank u very mauch, but my program gives right answer to it,
I really got confused with this
Posted: Tue Sep 12, 2006 2:51 am
by LIBe
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
Posted: Tue Sep 12, 2006 6:34 am
by Larry
Seems like most of the memo's got around 1 second. Just memo on the state..
Posted: Tue Sep 12, 2006 7:43 am
by LIBe
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...
Posted: Tue Sep 12, 2006 11:39 am
by vinay
why is backtracking so fast
Posted: Tue Sep 12, 2006 1:36 pm
by kp
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.