624 - CD

[Jan]

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.

[andysoft]

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.

[Jan]

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.

[andysoft]

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.

[Jan]

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.

[andysoft]

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
    read (m);
    read (n);
    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
      read (l[i]); //for(i=1;i<=n;i++) cin>>l[i];
      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.

[Jan]

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
    read (m);
    read (n);
    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
      read (l[i]); //for(i=1;i<=n;i++) cin>>l[i];
      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.

[andysoft]

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.

[Jan]

You are welcome. When eof is detected the code prints 'sum:0'. I was talking about this. However, good luck!

[AikoSenoo]

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) .
Would you please help me find where My code is wrong?

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]

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.

[Jan]

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.

[renato_ferreira]

Thank you very much, Jan! AC!

[toni]

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 

[Jan]

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.