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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Jul 17, 2007 9:44 pm

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:

Post by andysoft » Wed Jul 18, 2007 1:58 pm

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

Post by Jan » Wed Jul 18, 2007 3:55 pm

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

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:

Post by andysoft » Wed Jul 18, 2007 9:15 pm

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

Post by Jan » Wed Jul 18, 2007 9:28 pm

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:

Post by andysoft » Wed Jul 18, 2007 9:49 pm

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.
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 » Wed Jul 18, 2007 11:39 pm

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.
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 » Thu Jul 19, 2007 9:54 am

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

Post by Jan » Thu Jul 19, 2007 6:03 pm

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!

Post by AikoSenoo » Sat Jul 21, 2007 5:30 pm

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
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

Post by renato_ferreira » Tue Aug 14, 2007 12:10 am

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

Post by Jan » Tue Aug 14, 2007 11:48 am

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

Post by renato_ferreira » Tue Aug 14, 2007 9:07 pm

Thank you very much, Jan! AC!

toni
New poster
Posts: 7
Joined: Wed Jul 25, 2007 6:03 pm

Post by toni » Mon Sep 17, 2007 6:39 pm

hello , I got WA in this problem, could anybody please help me to find out what cause WA, thanks very much :D

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

Post by Jan » Tue Sep 18, 2007 1:18 am

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

Post Reply

Return to “Volume 6 (600-699)”