## 624 - CD

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Maintain another array to store the last element from which the current value is made. Suppose you used 'val' to get from k to p. So, p = k + val. So, sq[p] = val (sq is the sequence array). Or you can use sq[p] = k. Its upto your implementation.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Jan, thank you for the advice, but I couldnt understand it completely. I made an additional array (sq for us to better understand each other) and store there the length of the track. My Dynamic Programming part of code looks like this:

Code: Select all

``````//a is Dynamic array, l (L) is array with lengths of tracks, sq - sequence
for i:=1 to n do //n - number of tracks
for j:=1 to m do //m - tape length
if l[i]>j then //knapsack algorithm
a[i,j] := a[i-1,j]; //...
else//...
begin//...
a[i,j] := max (a[i-1,j],l[i]+a[i-1,j-l[i]]); //end of knapsack algrorithm
if sq[j]=0 then //storing the sequence
sq[j] := l[i] //storing the sequence
end;

//Then sorting and outputting, I'll have no prob with that
``````
But this works only from time to time.. 50% of tests give ok sequence, 50% - only the same number several times.
Hope you'll help me, TIA.
Now I lay me down to sleep...
my profile

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I have edited your code. Check it.

Code: Select all

``````//a is Dynamic array, l (L) is array with lengths of tracks, sq - sequence
for i:=1 to n do //n - number of tracks
for j:=1 to m do //m - tape length
if l[i]>j then //knapsack algorithm
begin
a[i,j] := a[i-1,j]; //...
sq[j] := 0;
end;
else//...
begin//...
a[i,j] := a[i-1,j];
sq[j] := 0;
if a[i,j] < l[i]+a[i-1,j-l[i]] then
begin
a[i,j] :=l[i]+a[i-1,j-l[i]];
sq[j] := l[i]; //storing the sequence
end;
end;
``````
Now You can find the sequence easily. Check the pseudocode below.

Code: Select all

``````findsequence (i,j)
{
if(i<0)
return;
if(sq[j] == 0)
findsequence(i-1,j);
else
{
print(sq[j]);
findsequence(i-1,j-sq[j]);
}
}``````
P.S. I m not a pascal programmer. So, there can be errors .

Hope these help.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Thank you for help. I have modified the code you send me a bit, and wrote function of finding the sequence, still I got WA...
Maybe you may look what is wrong?..

The DP:

Code: Select all

``````    for i:=1 to n do
for j:=1 to m do
if l[i]>j then
a[i,j] := a[i-1,j];
else
begin
a[i,j] := a[i-1,j];
if a[i,j] < l[i]+a[i-1,j-l[i]] then
begin
a[i,j] :=l[i]+a[i-1,j-l[i]];
sq[j] := l[i]; //storing the sequence
end;

end;
``````
After the DP I execute the path-finding function, which stores the path in array ans. Here is this function: (I execute it with 0,a[n,m] params by the way)

Code: Select all

``````procedure metalblack (i,j: integer); //i - total length of this sequence, j - like you offered
begin
if (sq[j]=0) then
metalblack (i,j-1)
else
begin
k := k + 1; //add new item to ANS array
ans[k] := find (sq[j]); //add new item to ANS array. Find - it finds the index of the track with given length in array L (which is inputted) by just looking all elements.
if i+sq[j]>=a[n,m] then exit; //if we took all needed elements to the output sequence, we gotta exit this function.
metalblack (i+sq[j],j-sq[j])//otherwise, continue, with adding current length to i, and subtracting it from j
end
end;
``````
After it usual sorting (bubble one) and output like in sample output.
Now I lay me down to sleep...
my profile

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
You should initialize sq[], if you use your code. Or you can use the code I posted already.

Your metalblack looks correct to me. But you can think of findsequence (i,j) again. What if you call findsequence (n,m)?

Hope these help.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Well, I did like you said now, but it didn't even pass default i/o tests.
Maybe let's talk about the prog in general, not about the functions separately? Maybe error is hidden outside functions.
Sorry, for Pascal'ing again, but I tried to make it as clear as I can.

Code: Select all

``````program Project2;
{\$R-}{\$S-}{\$Q-}
type
integer = longint;
function max(a,b: integer): integer; //just 'maximum' function
begin
result := a;
if b>a then result:=b
end;

var
a: array [-1..20,-1..20000] of integer; //DP
sq: array [1..20000] of integer;
ans: array [1..40] of integer;//Answer for sorting and outputting
l: array [1..20] of integer; //Given lengths
i,j,m,n,k,t: integer;

function find(v: integer): integer; //finding element by its length
var
i: integer;
begin
for i:=1 to n do
if l[i] = v then
begin
result := i;
exit
end
end;

procedure findsequence (i,j: integer); //your findSequence just in PAS
begin
if(i<0) then
exit;
if(sq[j] = 0) then
findsequence(i-1,j)
else
begin
k := k + 1;
ans[k] := find(sq[j]);
findsequence(i-1,j-sq[j])
end;
end;

procedure doOut; //just outputting
var
i: integer;
begin
for i:=1 to k do
write (l[ans[i]],' '); //length of the track, index of which is stored in ans[i]
writeln ('sum:',a[n,m])
end;

procedure sort; //Bubblesort, because, you know, the task description says we got to output in the same sequence as inputted
var
i,j,temp: integer;
begin
for i:=1 to k-1 do
for j:=1 to k-i do
if ans[j]>ans[j+1] then
begin
temp := ans[j];
ans[j] := ans[j+1];
ans[j+1] := temp
end
end;

begin

while not eof do //while (cin>>m>>n)
begin
for i:=1 to 20 do
for j:=1 to 20000 do a[i,j] := 0; //initializing of DP array

for i:=1 to n do
begin
ans[i] := 0 //init the ANS array
end;

for i:=1 to n do //init of DP array as in KnapSack algorithm
a[i,0] := 0;
for j:=1 to m do
a[0,j] := 0;

for i:=1 to 20000 do
sq[i] := 0; //init of SQ (won't spoil at least)

//DP as you offered
for i:=1 to n do
for j:=1 to m do
if l[i]>j then
begin
a[i,j] := a[i-1,j];
sq[j] := 0;
end
else
begin
a[i,j] := a[i-1,j];
sq[j] := 0;
if a[i,j] < l[i]+a[i-1,j-l[i]] then
begin
a[i,j] :=l[i]+a[i-1,j-l[i]];
sq[j] := l[i];
end;
end;

k := 0;//k is number of elements in ANS

findsequence (n,m); //find sequence with needed params
sort; //bubble sort
doOut; //output

end;

end.
``````
Now I lay me down to sleep...
my profile

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I have updated some parts. You have to use a 2d sq.

Code: Select all

``````program Project2;
{\$R-}{\$S-}{\$Q-}
type
integer = longint;

var
a: array [-1..20,-1..20000] of integer; //DP
sq: array [-1..20,-1..20000] of integer;
ans: array [1..40] of integer;//Answer for sorting and outputting
l: array [1..20] of integer; //Given lengths
i,j,m,n,k,t: integer;

function find(v: integer): integer; //finding element by its length
var
i: integer;
begin
for i:=1 to n do
if l[i] = v then
begin
result := i;
exit
end
end;

procedure findsequence (i,j: integer); //your findSequence just in PAS
begin
if(i=0) then
exit;
if(sq[i,j] = 0) then
findsequence(i-1,j)
else
begin
k := k + 1;
ans[k] := sq[i,j];
//ans[k] := find(sq[i,j]);
findsequence(i-1,j-sq[i][j])
end;
end;

procedure doOut; //just outputting
var
i: integer;
begin
for i:=1 to k do
write (l[ans[i]],' '); //length of the track, index of which is stored in ans[i]
writeln ('sum:',a[n,m])
end;

procedure sort; //Bubblesort, because, you know, the task description says we got to output in the same sequence as inputted
var
i,j,temp: integer;
begin
for i:=1 to k-1 do
for j:=1 to k-i do
if ans[j]>ans[j+1] then
begin
temp := ans[j];
ans[j] := ans[j+1];
ans[j+1] := temp
end
end;

procedure doOut1; //just outputting
var
i: integer;
begin
for i:=1 to k do
write (ans[k-i+1],' '); //length of the track, index of which is stored in ans[i]
writeln ('sum:',a[n,m])
end;

begin

while not eof(input) do //while (cin>>m>>n)
begin
for i:=1 to 20 do
for j:=1 to 20000 do
begin
a[i,j] := 0; //initializing of DP array
sq[i,j] := 0;
end;

for i:=1 to n do
begin
ans[i] := 0 //init the ANS array
end;

for i:=1 to n do //init of DP array as in KnapSack algorithm
a[i,0] := 0;
for j:=1 to m do
a[0,j] := 0;

//DP as you offered
for i:=1 to n do
for j:=1 to m do
if l[i]>j then
begin
a[i,j] := a[i-1,j];
sq[i,j] := 0;
end
else
begin
a[i,j] := a[i-1,j];
sq[i,j] := 0;
if a[i,j] < l[i]+a[i-1,j-l[i]] then
begin
a[i,j] :=l[i]+a[i-1,j-l[i]];
sq[i,j] := l[i];
end;
end;

k := 0;//k is number of elements in ANS

findsequence (n,m); //find sequence with needed params
//sort; //bubble sort
doOut1; //output

end;

end.
``````
It gives WA, too. May be there is a problem with eof handling. It prints one extra line when eof is detected.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Jan, man, thank you for your colossal help!!!!!
I will try to find the mistake in this code, because even with not printing the last "\n" it gives WA.
Now I lay me down to sleep...
my profile

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
You are welcome. When eof is detected the code prints 'sum:0'. I was talking about this. However, good luck!
Ami ekhono shopno dekhi...
HomePage

AikoSenoo
New poster
Posts: 3
Joined: Tue Jul 18, 2006 5:28 pm

### Help!

Hello, this is my code.
I've read all the posts about 624, but I still can't find where my problem is.
I sent this code and got RE(signal 11) .

Thank you very much!

Code: Select all

``````#include<stdio.h>
#define limit 20000

int main(void){
int N;
int MW;

int total;
int c[25][limit+1];
int item[25][limit+1];
int cd[25];
int i,j;
int temp;
int a[25];

while(scanf("%d",&MW)!=EOF){
scanf("%d",&N);
total=0;
a[0]=0;

for(i=1;i<=N;i++)
scanf("%d",&a[i]);

for(j=0;j<=MW;j++)c[0][j]=0;

for(i=1;i<=N;i++){
c[i][0]=0;
item[0][i]=0;
for(j=1;j<=MW;j++){
if(a[i]>j){
c[i][j]=c[i-1][j];
item[i][j]=item[i-1][j];
}
else{
if(c[i-1][j]>=c[i-1][j-a[i]]+a[i]){
c[i][j]=c[i-1][j];
item[i][j]=item[i-1][j];
}
else{
c[i][j]=c[i-1][j-a[i]]+a[i];
item[i][j]=i;
}
}
}

}total+=c[N][MW];
temp=0;
for(i=MW,j=0;i>=1;i-=a[item[N][i]],j++)
cd[j]=a[item[N][i]];
for(i=j-1;i>=0;i--){
printf("%d ",cd[i]);
temp+=cd[i];
if(temp==total)break;
}
printf("sum:%d\n",total);
}

return 0;
}
``````

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
If there are more then one answer, can I print anyone of then?
Im getting WA, and I can't find the error.

Code: Select all

``````AC
``````
Thank you.
Last edited by renato_ferreira on Tue Aug 14, 2007 9:08 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the cases.

Input:

Code: Select all

``````32 5 14 1 11 5 9
15 8 13 10 20 19 4 19 7 20
29 6 20 15 5 7 20 19
60 8 10 8 3 11 3 19 7 8
81 7 19 20 12 18 14 14 1``````
Output:

Code: Select all

``````1 5 11 14 sum:31
4 10 sum:14
5 7 15 sum:27
3 3 7 8 8 11 19 sum:59
1 12 14 14 19 20 sum:80``````
And yes. Multiple outputs are supported. Hope these help.
Ami ekhono shopno dekhi...
HomePage

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm
Thank you very much, Jan! AC!

toni
New poster
Posts: 7
Joined: Wed Jul 25, 2007 6:03 pm
hello , I got WA in this problem, could anybody please help me to find out what cause WA, thanks very much

Code: Select all

`` got AC ``
Last edited by toni on Tue Sep 18, 2007 5:10 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
May be some sort of initialization problem. Check the cases...

Input:

Code: Select all

``````52 5 15 1 10 5 19
29 10 5 6 6 2 8 2 12 16 3 8
47 9 5 3 14 13 3 2 17 19 16
58 9 12 19 10 13 8 20 16 15 4
62 5 14 14 5 2 12
94 16 8 5 3 18 18 20 4 2 10 19 17 16 11 3 9 7
51 5 5 9 7 6 11
80 13 11 7 2 14 9 10 4 5 15 17 1 7 17
82 16 5 20 7 4 18 19 19 3 10 2 14 16 20 19 5 11``````
Output:

Code: Select all

``````1 5 10 15 19 sum:50
2 2 3 6 8 8 sum:29
3 3 5 17 19 sum:47
4 8 10 16 20 sum:58
2 5 12 14 14 sum:47
2 3 3 4 5 7 8 9 16 17 20 sum:94
5 6 7 9 11 sum:38
1 2 4 5 7 7 9 11 17 17 sum:80
2 3 4 5 5 7 10 11 16 19 sum:82``````
Hope these help.
Ami ekhono shopno dekhi...
HomePage