Why is my recursive solution of this(link given) spoj problem giving me WA?

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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?

#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 ] ); }

#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 ) ); }

#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 ); }

#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 ) ); }

Комментарии (8)

Написать комментарий?

CrafterKolyan

7 лет назад, # |

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

→ Ответить

VIKRAM91

7 лет назад, # ^ |

Edited, still same problem.

CodingKnight

← Rev. 2 →

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.

Thanks a lot. I have edited the code.

← Rev. 6 →

With pleasure.

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

Iterative version

Recursive version

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

← Rev. 12 →

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.

← Rev. 9 →

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

Блог пользователя VIKRAM91