10482  The Candyman Can
Moderator: Board moderators
10482  The Candyman Can
Feel ashamed to say this, but any clue would be appreciated

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
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 , 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!
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 , 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
10482  The candyman can
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 ith 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.
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 ith 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.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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 10candy 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.
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 10candy 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.
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 offbyone error in some array, as I've allocated some extra space just to make sure.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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 3candy 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.
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.
Re: 10482  The Candyman Can
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 = sumab and determine which max(a,b,c)  min(a,b,c) is the smallest.

 Learning poster
 Posts: 74
 Joined: Sat Jul 15, 2006 6:28 am
 Location: CUET , bangladesh
 Contact:
Re: 10482  The Candyman Can
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
Re: 10482  The Candyman Can
input
output from my AC programm
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
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