CDUTSV03 Heist Editorial

editorial
1

PROBLEM LINK: Digit Game

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;
}
2

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

3

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.

4

Thanks , :smiley: