VIKRAM91's blog

Why is my recursive solution of this(link given) spoj problem giving me WA?
By VIKRAM91, history, 6 years ago, In English

I was doing this Spoj problem and written tabulation method which got accepted, then I have written recursive solution but this gave me the wrong solution(WA), Where is my recursive solution is wrong:-

Below is my tabulation solution which got AC:- 

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[n]={0};
  int b[n]={0};
  for(int i=0;i<n;i++){
      cin>>a[i]>>b[i];
  }
  int dp[n][2]={{0}};
  dp[0][0]=b[0];
  dp[0][1]=a[0];
  for(int i=1;i<n;i++){
      int x=dp[i-1][0]+abs(a[i]-a[i-1])+b[i];
      int y=dp[i-1][1]+abs(a[i]-b[i-1])+b[i];
      int s=dp[i-1][0]+abs(b[i]-a[i-1])+a[i];
      int t=dp[i-1][1]+abs(b[i]-b[i-1])+a[i];
      dp[i][0]=max(x,y);
      dp[i][1]=max(s,t);
  }
  cout<<max(dp[n-1][0],dp[n-1][1]);
  return 0;
 }

And below is my recursive solution which is giving me WA:-

#include<bits/stdc++.h>
 using namespace std;

 int ans(int a[],int b[],int n,int j){
    if(n==0&&j==0)
       return b[0];
    if(n==0&&j==1)
       return a[0];
    int x=ans(a,b,n-1,0)+b[n]+abs(a[n-1]-a[n]);
    int y=ans(a,b,n-1,1)+b[n]+abs(b[n-1]-a[n]);
    int s=ans(a,b,n-1,0)+a[n]+abs(a[n-1]-b[n]);
    int t=ans(a,b,n-1,1)+a[n]+abs(b[n-1]-b[n]);
    return max(max(x,y),max(s,t));
}

 int main(){
    int n;
    cin>>n;
    int a[n]={0};
    int b[n]={0};
    for(int i=0;i<n;i++){
       cin>>a[i]>>b[i];
    }
    if(a[0]>b[0])
        cout<<ans(a,b,n-1,1);
    else cout<<ans(a,b,n-1,0)
    return 0;
  }

I want to ask:-

1). What is wrong with my recursive solution.

2). Can we do all dp problem with tabulation and memoization i.e if we can do with memoization than can we do with tabulation and vice versa for every dp problem?

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if n is equal to 1, you have got RE.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Edited, still same problem.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Rewriting the recursive ans() function to make it more readable may help others to give you their feedback, and help you as well in comparing it to the iterative version of the program.

      It is recommended that the return value of each recursive call to ans() function is stored in a different variable whose value can be subsequently used to compute the return value of the function.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks a lot. I have edited the code.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 6   Vote: I like it +1 Vote: I do not like it

          With pleasure.

          The following is an update to your two versions. Both updated versions were accepted on Spoj.

          Iterative version

          #include <bits/stdc++.h>

using namespace std;

const size_t N = 1000; int a[ N ], b[ N ], dp[ N ][ 2 ];

int main()
{
    int n, p; cin >> n, p = n - 1;

    for( int i = 0; i < n; i++ )
      cin >> a[ i ] >> b[ i ];

    dp[ 0 ][ 0 ] = b[ 0 ],
    dp[ 0 ][ 1 ] = a[ 0 ];

    for( int j = 0, i = 1; i < n; j = i++ )
    {
        int ai = a[ i ],
            bi = b[ i ],
            aj = a[ j ],
            bj = b[ j ],
            d0 = dp[ j ][ 0 ],
            d1 = dp[ j ][ 1 ],
            g0 = d0 + abs( ai - aj ),
            g1 = d1 + abs( ai - bj ),
            g2 = d0 + abs( bi - aj ),
            g3 = d1 + abs( bi - bj );

        dp[ i ][ 0 ] = bi + max( g0, g1 ),
        dp[ i ][ 1 ] = ai + max( g2, g3 );
    }

    cout << max( dp[ p ][ 0 ], dp[ p ][ 1 ] );
 }

          Recursive version

          #include <bits/stdc++.h>

using namespace std;

const size_t N = 1000; int a[ N ], b[ N ], dp[ N ][ 2 ];

int DP( int i, int k )
{
    if ( i == 0 )
        return ( k ? a[ 0 ] : b[ 0 ] );

    int j  = i - 1;

    int ai = a[ i ],
        bi = b[ i ],
        aj = a[ j ],
        bj = b[ j ],
        d0 = dp[ j ][ 0 ],
        d1 = dp[ j ][ 1 ];

    if ( d0 == 0 )
        dp[ j ][ 0 ] = d0 = DP( j, 0 );

    if ( d1 == 0 )
        dp[ j ][ 1 ] = d1 = DP( j, 1 );

    if ( k == 0 )
    {
        int  g0 = d0 + abs( ai - aj ),
             g1 = d1 + abs( ai - bj );

        return bi + max( g0, g1 );
    }
    else
    {
        int g2 = d0 + abs( bi - aj ),
            g3 = d1 + abs( bi - bj );

        return ai + max( g2, g3 );
    }
}

int main()
{
    int n, p; cin >> n, p = n - 1;

    for( int i = 0; i < n; i++ )
      cin >> a[ i ] >> b[ i ];

    cout << max( DP( p, 0 ), DP( p, 1 ) );
 }
          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks a lot, buddy. Finally, I got accepted my memoization solution thanks to you.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 12   Vote: I like it 0 Vote: I do not like it

              With pleasure, fellow.

              The update has just been modified slightly to use the same variables in both versions for storing partial results.

              It is imperative that the return value of the function call DP(i,k) in the recursive version is equal to the array value dp[i][k] computed in the iterative version.

              → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 9   Vote: I like it 0 Vote: I do not like it

          The following is a more compact update that uses pair< int, int > data structure to store the dimensions of each rectangle as well as the partial solution and the final solution with the two possible orientations of the last rectangle and the previous rectangle.

          Furthermore, the DP() recursive function is rewritten as two different functions dp_first() and dp_second() so as to remove the second function argument k of DP() and remove the conditional if statements on the value of k inside DP().

          Iterative version

          #include <bits/stdc++.h>

using namespace std;

typedef pair< int, int > pair_t;

const size_t N = 1000; pair_t r[ N ], dp[ N ];

int DP( int n )
{
    pair_t *di = dp, *dj = di++, *ri = r, *rj = ri++;

    dj->first = rj->second, dj->second = rj->first;

    for( int i = 1; i < n; i++, dj = di++, rj = ri++ )
    {
        int g0 = dj->first  + abs( ri->first  - rj->first  ),
            g1 = dj->second + abs( ri->first  - rj->second ),
            g2 = dj->first  + abs( ri->second - rj->first  ),
            g3 = dj->second + abs( ri->second - rj->second );

        di->first  = ri->second + max( g0, g1 ),
        di->second = ri->first  + max( g2, g3 );
    }

    return max( dj->first, dj->second );
}

int main()
{
    int n; cin >> n;

    for( int i = 0; i < n; i++ )
        cin >> r[ i ].first >> r[ i ].second;

    cout << DP( n );
}

          Recursive version

          #include <bits/stdc++.h>

using namespace std;

typedef pair< int, int > pair_t;

const size_t N = 1000; pair_t r[ N ], dp[ N ];

int dp_second( int );

int dp_first( int i )
{
    if ( i == 0 )
        return r->second;

    int j  = i - 1;

    pair_t *d = dp + j, *ri = r + i, *rj = r + j;

    if ( d->first  == 0 )
         d->first = dp_second( j );

    if ( d->second == 0 )
         d->second = dp_first( j );

    int g0 = d->second + abs( ri->first - rj->first  ),
        g1 = d->first  + abs( ri->first - rj->second );

    return ri->second + max( g0, g1 );
}

int dp_second( int i )
{
    if ( i == 0 )
        return r->first;

    int j  = i - 1;

    pair_t *d = dp + j, *ri = r + i, *rj = r + j;

    if ( d->first  == 0 )
         d->first  = dp_second( j );

    if ( d->second == 0 )
         d->second = dp_first( j );

    int g2 = d->second + abs( ri->second - rj->first  ),
        g3 = d->first  + abs( ri->second - rj->second );

    return ri->first + max( g2, g3 );
}


int main()
{
    int n, p; cin >> n, p = n - 1;

    for( int i = 0; i < n; i++ )
        cin >> r[ i ].first >> r[ i ].second;

    cout << max( dp_first( p ), dp_second( p ) );
}
          → Reply