624 - CD

Raiyan Kamal · Post by **Raiyan Kamal** » Tue Aug 10, 2004 7:23 pm

long in C is enough for this problem.

neno_uci · Post by **neno_uci** » Wed Jan 26, 2005 7:10 pm

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.

neno_uci · Post by **neno_uci** » Thu Jan 27, 2005 11:29 pm

I have found my bug, now i got AC.

dovier_antonio · Post by **dovier_antonio** » Sun Mar 13, 2005 11:35 am

I know you from some places.... uhmm... oh yeah, your are my teammate in the UCI team!!

Sedefcho · Post by **Sedefcho** » Wed Jul 20, 2005 11:57 am

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 0-1 knapsack problem.

Hope this helps.

Chok · Post by **Chok** » Sat Jul 23, 2005 8:43 am

Hi All,
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....

sohel · Post by **sohel** » Sat Jul 23, 2005 9:14 am

There is a slight mistake in your code...

consider this line..

Code: Select all

if(s<=sum && max<=s && res[21]<=k)

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.

Chok · Post by **Chok** » Sat Jul 23, 2005 6:20 pm

Hi Sohel,
Thanks for ur help. Got ACC. I misunderstood that part. You rite, the problem can be solved easily by 0/1 knapsack. I use backracking bcoz i'm not so good with 0/1 knapsack and here the limit is not so large. Thanks again.

helloneo · Post by **helloneo** » Sat Aug 13, 2005 10:55 am

anybody would tell me why it doen't work..?
need some input..

jagadish · Post by **jagadish** » Sat Aug 13, 2005 6:54 pm

my AC code assumes N<=20000..

http://online-judge.uva.es/board/viewto ... hlight=624

helloneo · Post by **helloneo** » Sat Aug 13, 2005 6:58 pm

i got AC..
thanks..~

andysoft · Post by **andysoft** » Tue Jul 17, 2007 5:47 pm

what's the knapsack??

Jan · Post by **Jan** » Tue Jul 17, 2007 7:45 pm

Remember that google is your friend

.

andysoft · Post by **andysoft** » Tue Jul 17, 2007 7:59 pm

I got it. I simply didn't know it in English.

andysoft · Post by **andysoft** » Tue Jul 17, 2007 9:10 pm

Well, knapsack method finds the sum ok, but how to restore all the taken elements (tracks) from array A ...

Recursion surely causes TLE

OJ Board

624 - CD

624 WA :(

Hola nenito !!!

N <= 20000

WA

slight mistake...

624 - CD

thanks..