10482 - The Candyman Can

All about problems in Volume 104. 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
mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

10482 - The Candyman Can

Post by mido »

Feel ashamed to say this, but any clue would be appreciated :(

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. »

I solved this problem by traversing state space (a, b, c) with BFS. (I'm not sure I'm using the right terminology..)

At the first glance it could seem the space is too large (since 640^3 = 262,144,000 .. approximately 2^28 ), but you can derive that the maximum of these three values will not exceed .. about 240. Also you can reduce the size of it dramatically by asserting a <= b <= c. (You can see it's equivalent)

So with these features I believe there won't be more than 2 million nodes even in the worst case, and I think it's sufficient. My solution runs 0.416 sec. (although it uses a bit large memory :wink: , but it could be avoided by using a more efficient memory structure)

I don't know how to solve it in 0.004sec like Mr. Hossain, but this is what I've got. =)

Good luck, and any suggestions will be appreciated!
JongMan @ Yonsei

cmad
New poster
Posts: 5
Joined: Thu Sep 01, 2005 10:10 am

10482 - The candyman can

Post by cmad »

I was wondering if someone could point out the error in my DP algorithm (I get WA):

let sum(n) be the sum of the candies #1..n of the input

let c(n, a, b) be the min difference (as defined in the problem) of the total candy weight of the 3 children, right before candy #n is given, at that point, kid A has candy weight = a, kid B has candy weight = b

suppose we are to give N candies, the base case is:

c(N+1, a, b) = max( a, b, c ) - min( a, b, c ), where c = sum(N) - a - b

thus, for each n, 1 <= n <= N:

( v is the weight of the i-th candy )

c(n, a, b) = min( c(n+1, a + v[n], b), c(n+1, a, b + v[n]), c(n+1, a, b) )

and I output c(1, 0, 0)

short description: for each step (in reverse order), i consider the possible 3 next steps (give candy to A, B or C) I could make from that point, and choose the one which has the least difference

The above algorithm gives me WA at ~4sec. I saw that people submitted solutions that run almost instantly, and I wonder what the optimal solution would be like.

Thanks,
cmad ~

Edit: Sorry I didn't post here, but I thought that post was too old to bump.

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

Post by little joey »

Your reasoning looks OK to me, but I can't "think it trough" completely now.

One way to find flaws in this kind of problems, is to write a brute force solution, make a huge random testset with a limited number of candies, and compare the output of your program with the output from the brute force program.
For 10 candies, there are only 3^10 = 59049 different ways to distribute them among 3 kids, so the brute force answer isn't too hard to find. You could make a testset of say 1000 (or 10000, or a million) random 10-candy cases.

One obvious way to speed up your program is to require that a<=b<=c, although I don't know if that works in your implementation.

cmad
New poster
Posts: 5
Joined: Thu Sep 01, 2005 10:10 am

Post by cmad »

I must be very unlucky, as I compared my program with a bruteforce implementation of the solution (3^n). I ran 100 random tests, perfect matches for each test (n = 13 for each test, otherwise the bf binary would take ages to finish). This is weird :\ And I don't think it's an off-by-one error in some array, as I've allocated some extra space just to make sure.

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

Post by little joey »

Yes, this is a tricky problem and I had to write several programs during several months before I got it right. Are you sure you handle the 1-, 2- and 3-candy cases right?
If you want, you can send me your email address by PM and I'll give you a testset with 10000 random cases along with the output from my AC program.

cmad
New poster
Posts: 5
Joined: Thu Sep 01, 2005 10:10 am

Post by cmad »

Yes it seems to be able to handle (1, 2, 3) cases correctly. I'll pm you my e-mail as you said.

tmt514
New poster
Posts: 1
Joined: Thu Jun 07, 2007 9:52 am

Post by tmt514 »

You can use DFSID and some way like problem 307,
it'll AC in 0.004 sec!

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10482 - The Candyman Can

Post by stcheung »

Yeah like one of the previous post says, simple BFS is more than enough to solve this. So do BFS to get all DISTINCT (a, b) pairs such that neither a or b is >= 250. To make sure they are distinct you want to maintain a double array [250][250] to keep track of all the ones you have seen already. At the end, just iterate through these pairs, set c = sum-a-b and determine which max(a,b,c) - min(a,b,c) is the smallest.

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Re: 10482 - The Candyman Can

Post by shakil »

Why WA!!! I used BFS. Please give me some input & output which my code can not cover. Thanks

Code: Select all

CUT after AC. Thanks crip121 for his input & output. I have changed my BFS solution to DP & it really nice  :D 
Last edited by shakil on Thu Feb 11, 2010 8:07 pm, edited 2 times in total.
SHAKIL

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 10482 - The Candyman Can

Post by crip121 »

input

Code: Select all

10
32
2 8 15 1 10 5 19 19 3 5 6 6 2 8 2 12 16 3 8 17 12 5 3 14 13 3 2 17 19 16 8 7 
32
12 19 10 13 8 20 16 15 4 12 3 14 14 5 2 12 14 9 8 5 3 18 18 20 4 2 10 19 17 16 11 3 
32
9 7 1 3 5 9 7 6 11 10 11 11 7 2 14 9 10 4 5 15 17 1 7 17 12 9 5 20 7 4 18 19 
32
19 3 10 2 14 16 20 19 5 11 18 7 14 7 2 6 5 13 11 10 18 14 18 13 7 11 2 17 16 8 16 15 
32
12 13 11 11 2 5 7 11 8 12 8 18 18 8 14 4 6 10 10 19 2 9 3 7 7 11 14 9 1 12 3 16 
32
11 20 5 18 9 4 16 2 3 11 12 17 15 1 17 2 9 20 9 5 2 15 14 20 19 19 1 9 8 8 9 14 
32
9 4 8 2 11 18 14 15 10 17 16 12 1 10 20 17 19 4 5 9 5 10 10 3 16 6 14 4 4 8 15 4 
32
9 1 19 19 1 17 19 2 10 19 10 18 13 3 19 13 19 20 11 18 19 12 16 9 17 12 3 15 13 16 9 7 
32
3 7 16 14 10 3 5 17 2 19 3 12 2 20 18 17 13 10 16 13 1 11 4 10 2 9 2 10 16 4 3 6 
32
3 6 9 7 18 18 13 13 10 15 2 10 17 10 9 13 6 16 15 10 2 13 6 1 19 14 20 4 20 17 8 10 
output from my AC programm

Code: Select all

Case 1: 1
Case 2: 1
Case 3: 1
Case 4: 1
Case 5: 1
Case 6: 1
Case 7: 1
Case 8: 0
Case 9: 1
Case 10: 0

Post Reply

Return to “Volume 104 (10400-10499)”