11088 - End up with More Teams

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

11088 - End up with More Teams

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 :D
studying @ ntu csie

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

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.

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

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... :lol:

I takes >1s ,precisely 1.094..
:wink:
If I will myself do hashing, then who will do coding !!!

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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

I solved it with backtracking.

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

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.. :lol:
If I will myself do hashing, then who will do coding !!!

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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

0.002

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

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

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
New poster
Posts: 6
Joined: Sat Oct 29, 2005 11:56 pm

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... :lol:

I takes >1s ,precisely 1.094..
:wink:
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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

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
New poster
Posts: 6
Joined: Sat Oct 29, 2005 11:56 pm

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...

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

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

why is backtracking so fast :o
If I will myself do hashing, then who will do coding !!!

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

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.

Post Reply

Return to “Volume 110 (11000-11099)”