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

№	Пользователь	Рейтинг
1	tourist	3803
2	jiangly	3707
3	Benq	3627
4	ecnerwala	3584
5	orzdevinwang	3573
6	Geothermal	3569
6	cnnfls_csy	3569
8	Radewoosh	3542
9	jqdai0815	3532
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	165
2	awoo	164
3	adamant	162
4	maroonrk	152
5	-is-this-fft-	151
5	nor	151
7	atcoder_official	147
8	TheScrasse	146
9	Petr	145
10	SecondThread	142

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

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

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

→ Ответить

VIKRAM91

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

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