624 - CD

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

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

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 :(

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
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

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

I have found my bug, now i got AC. :D

User avatar
dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

Hola nenito !!!

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!!
Last edited by dovier_antonio on Fri Feb 03, 2012 10:09 am, edited 1 time in total.

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

N <= 20000

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
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

WA

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

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

slight mistake...

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
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

624 - CD

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

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.

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

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

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

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

i got AC..
thanks..~

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

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

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
Location: Dhaka, Bangladesh
Contact:

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

Remember that google is your friend :D .
Ami ekhono shopno dekhi...
HomePage

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

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

:)
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:

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

Post Reply

Return to “Volume 6 (600-699)”