624 - CD

Moderator: Board moderators

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Contact:
long in C is enough for this problem.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

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

Yandry.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
I have found my bug, now i got AC.

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.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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

Hope this helps.

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

WA

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....
``````
Last edited by Chok on Sat Jul 23, 2005 6:22 pm, edited 1 time in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

slight mistake...

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
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong
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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

624 - CD

anybody would tell me why it doen't work..?
need some input..
Last edited by helloneo on Tue May 22, 2007 7:58 am, edited 2 times in total.

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
if u can think of it .. u can do it in software.

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

thanks..

i got AC..
thanks..~

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
what's the knapsack??
Now I lay me down to sleep...
my profile

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

I got it. I simply didn't know it in English.
Now I lay me down to sleep...
my profile

andysoft
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
Now I lay me down to sleep...
my profile