624  CD
Moderator: Board moderators

 Experienced poster
 Posts: 106
 Joined: Thu Jan 29, 2004 12:07 pm
 Location: Bangladesh
 Contact:
624 WA :(
Hi, i dont know why WA!!!, I have tried a lot of test cases and they are all fine...
Here is my algo:
Store all the numbers in an array.
1. If the sum of all is less or equal than N then output them all.
2. If one of them is equal to N then output it.
3. Else go from 1 to 2^t  1 selecting the best bit pattern which satisfies that sum <= N.(here t is the number of tracks)
Where is my mistake???
Thanx in advance,
Yandry.
Here is my algo:
Store all the numbers in an array.
1. If the sum of all is less or equal than N then output them all.
2. If one of them is equal to N then output it.
3. Else go from 1 to 2^t  1 selecting the best bit pattern which satisfies that sum <= N.(here t is the number of tracks)
Where is my mistake???
Thanx in advance,
Yandry.
 dovier_antonio
 New poster
 Posts: 47
 Joined: Fri Feb 18, 2005 5:00 am
 Location: Havana, Cuba
Hola nenito !!!
I know you from some places.... uhmm... oh yeah, your are my teammate in the UCI team!!
Last edited by dovier_antonio on Fri Feb 03, 2012 10:09 am, edited 1 time in total.
N <= 20000
I know it has been a long time since anyone made a post
in this thread but just there are few words I want to say for
those who will try to solve problem 624 in the future. I hope
it will make the problem boundaries clearer.
In the problem statement is said that the count of the
tracks is <= 20. So this is clear.
With respect to N ( the length of the tape ) you may safely assume
that N <= 20000. I haven't tried to assume a smaller max value
for N but 20000 is fine. I mean, I use DP and my algorithm assumes
that N<=20000 and it works fine.
And long in C/C++ is just too much At the end of the day,
this is just a 01 knapsack problem.
Hope this helps.
in this thread but just there are few words I want to say for
those who will try to solve problem 624 in the future. I hope
it will make the problem boundaries clearer.
In the problem statement is said that the count of the
tracks is <= 20. So this is clear.
With respect to N ( the length of the tape ) you may safely assume
that N <= 20000. I haven't tried to assume a smaller max value
for N but 20000 is fine. I mean, I use DP and my algorithm assumes
that N<=20000 and it works fine.
And long in C/C++ is just too much At the end of the day,
this is just a 01 knapsack problem.
Hope this helps.
WA
Hi All,
I'm getting WA several times. Please tell me what i mistake. Thanks in advance.
Here is my code :
I'm getting WA several times. Please tell me what i mistake. Thanks in advance.
Here is my code :
Code: Select all
Cut After Accepted....
Last edited by Chok on Sat Jul 23, 2005 6:22 pm, edited 1 time in total.
slight mistake...
There is a slight mistake in your code...
consider this line..
there is no need for  res[21] <= k ; infact that's the cause of WA.
Remove the last condition and you should get AC.
The main priority should be given on the amount of free spaces at the end and not on how many tracks you have used.
BTW: This problem could be solved easily by 0/1 knapsack..
if the input range was something close to 100, then backtracking won't suffice.
consider this line..
Code: Select all
if(s<=sum && max<=s && res[21]<=k)
Remove the last condition and you should get AC.
The main priority should be given on the amount of free spaces at the end and not on how many tracks you have used.
BTW: This problem could be solved easily by 0/1 knapsack..
if the input range was something close to 100, then backtracking won't suffice.

 Experienced poster
 Posts: 109
 Joined: Sat Jun 23, 2007 9:53 pm
 Location: Brest, BELARUS
 Contact:
Well, knapsack method finds the sum ok, but how to restore all the taken elements (tracks) from array A ...
Recursion surely causes TLE
Recursion surely causes TLE
Now I lay me down to sleep...
my profile
my profile