# CDUTSV03 Heist Editorial

AUTHOR: sohit_1212

DIFFICULTY: Medium

PREREQUISITES: Dynamic Programming , Recursion

This is a standard DP question. We maintain a DP state A[N][M] ; where N=10000 (the upper limit for the 4 digit number) and M=101(The number of chances)
We make 4 recursive call at each turn by modifying the digit at all the four places, when i is even we take the minimum value and store it in A[n][i] and when i is odd, we take the maximum.

``````#include <iostream>
#include <cstring>

#define N 10000
#define M 110
using namespace std;

int A[N][M];

int foo(int n, int i, int m) {

if(i>m) return n;

if(A[n][i] != -1) return A[n][i];

int a=n/10,b=n/100,c=n/1000,d=0;

a = a*10+((n%10+1)%10);
b = b*100+((n%100+10)%100);
c = c*1000+((n%1000+100)%1000);
d = (n+1000)%10000;

if(i%2 == 1) {
A[n][i] = max(max(foo(a,i+1,m),foo(b,i+1,m)),
max(foo(c,i+1,m),foo(d,i+1,m)));
//return A[n][i];
}
else {
A[n][i] = min(min(foo(a,i+1,m),foo(b,i+1,m)),
min(foo(c,i+1,m),foo(d,i+1,m)));
}

return A[n][i];

}
int main() {
int t;
scanf("%d",&t);
while(t--) {
int n,m;
scanf("%d%d",&n,&m);
memset(A,-1,sizeof(A));
int val = foo(n,1,m);
if(val > n) printf("Berlin\n");
else printf("Professor\n");
}
return 0;
}``````

could someone explain when would the condition if(A[n][i] != -1) return A[n][i];
would be true ??

Since there are multiple recursive calls, it is always possible that at some instance, there will be a recursive call for the same value of (n,i) .
If A[n][i] was previously calculated, we can return the stored value and hence avoid overlapping subproblems.

Thanks ,