11088  End up with More Teams
Moderator: Board moderators
11088  End up with More Teams
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
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
studying @ ntu csie
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 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.
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.

 New poster
 Posts: 18
 Joined: Fri Apr 21, 2006 11:34 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.
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

 New poster
 Posts: 18
 Joined: Fri Apr 21, 2006 11:34 am
I tried it using backtracking, and DP like O(2^n), but I got TLEvinay 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 want to show your solution  that is, how to solve it using backtracking... or memoization

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
Seems like most of the memo's got around 1 second. Just memo on the state..
Check out http://www.algorithmist.com !