Codeforces round #96 (division 2)

Day for another contest. This time I had to do it from my reliable, but small netbook since the big one was busy. I didn't think it would matter, and it turns out it didn't.

I had issues entering the site for the first three minutes of the contest. Apparently they got fixed themselves.

Problem A - HQ9+
An easy one, the only characters that do any printing are H, Q and 9. So, just make a loop to detect them.

I actually spent a lot of time getting my setup to run and test stuff for some reason.

Problem B - Unary
Just at the bottom of the statement, it finally explains that the unary system just writes 1 n times. The length of a number n when represented in unary is thus exactly n.

Then we need to find the actual number n. It is the result of the concatenation of a (possibly large) amount of 4 bits numbers in binary. Three things:
- Consider the binary blocks as decimal numbers directly, for example consider < to be 8 right away.
- To concatenate 1000 with 1010 is the same as doing: 1000 * 10000 + 1010. In decimal it translates into 8 * 16 + 10.
- So, to concatenate the (n-1) first symbols with a new one, find the result X for the n-1 first symbols then do: (n-1)*16 + new.
- The actual number may be very large (400 bits). But the problem asks for the result modulo 1000003. We can just exploit some modular arithmetic . (X * Y + Z) mod 1000003 is equal to ( (X mod 1000003) * (Y mod 1000003) + Z ) mod 1000003. This way, we need only to remember the partial results modulo 1000003.

const int MOD = 1000003; 
 
int translate(char ch) 
{ 
    switch(ch) { 
    case '>': return 8; 
    case '<': return 9; // →  1001, 
    case '+': return 10;//   →  1010, 
    case '-': return 11; // →  1011, 
    case '.': return 12; // →  1100, 
    case ',': return 13; // →  1101, 
    case '[': return 14; // →  1110, 
    case ']': return 15; // →  1111.          
    } 
} 
 
int solve(string x) 
{ 
    int res = 0; 
    for (int i=0; i<x.size(); i++) { 
        res = (res << 4) % MOD; 
        res += translate(x[i]); 
        res %= MOD; 
    } 
    return res; 
} 

Problem C - Turing tape
* Keep in mind the integer value of the previous printed character. For i=0, this is 0, else it is the (i-1)-th character of the input string.
* The conversion is: rev[ (x - rev(last) ) mod 256 ], it is simple to revert, first, reverse the i-th printed character, then solve the modular equaton, yes, once again modular arithmetic.

I was going to explain more problems but I will go take lunch, will update this soon.

Problem D - Piet
Oh, this is such an evil problem. Anyway, since n can be 10^7, you'd probably like to do each step in O(1). In order to do each step in O(1) you need to precalculate various things that you can use in each step. First, find the blocks and which block each cell belongs to.

What I did was to also precalculate the corner cells of each block (A look at the statement reveals that every move involves moving from a corner of a block to another).

To represent the directions (DP), I use a integer from 0 to 3. The offsets (change of coordinates) are left, down, right, up - ordered in clockwise order. CP will then be the offset in the direction index from DP and is -1 or 1.

The implementation of the logic takes some work of thought. In my case, I need to convert DP and CP into a corner of the current block. Then from that corner, move according to DP and find the next block. If it is black or outside the board, you would need to rotate DP and CP according to the statement.

int m; 
int n; 
string board[50]; 
 
int blockn; 
int cellBlock[50][50]; 
int blockCornerX[2500][2][2]; 
int blockCornerY[2500][2][2]; 
 
char solve() 
{ 
    //a) let us save a block id for each square in the grid 
    memset(cellBlock,-1,sizeof(cellBlock)); 
    blockn = 0; 
    int w = m; 
    int h = board[0].size(); 
    //get info about our beloved blocks. 
    for (int i=0; i<w; i++) { 
        for (int j=0; j<h; j++) { 
            if ( (board[i][j] != '0') && (cellBlock[i][j]==-1) ) { 
                int a = i; 
                while ( (a<w) && (board[a][j] == board[i][j] ) ) { 
                    a++; 
                } 
                int b = j; 
                while ( (b<h) && (board[i][b] == board[i][j] ) ) { 
                    b++; 
                } 
                for (int x=i; x<a; x++) { 
                    for (int y=j; y<b; y++) { 
                        cellBlock[x][y] = blockn; 
                    } 
                } 
                for (int x=0; x<2; x++) { 
                    for (int y=0; y<2; y++) { 
                        blockCornerX[blockn][x][y] = i + (a-1-i)*x; 
                        blockCornerY[blockn][x][y] = j + (b-1-j)*y; 
                    } 
                } 
                blockn++; 
            } 
        } 
    } 
    int BP = 0; 
    int dx[4] = {0, 1,  0, -1}; 
    int dy[4] = {1, 0, -1, 0 }; 
    int DP = 0; 
    int CP = -1; 
    for (int t=0; t<n; t++) { 
        //cout << "t"<<t<<" : "<<BP<<" ; "<<dx[DP]<<","<<dy[DP]<<" ; "<<CP<<endl; 
        int nx = dx[DP] + dx[ (DP+CP+4) % 4 ]; 
        int ny = dy[DP] + dy[ (DP+CP+4) % 4 ]; 
        if (nx == -1) { 
            nx = 0; 
        } else { 
            nx = 1; 
        } 
        if (ny == -1) { 
            ny = 0; 
        } else { 
            ny = 1; 
        } 
        int cx = blockCornerX[BP][nx][ny]; 
        int cy = blockCornerY[BP][nx][ny]; 
        nx = cx + dx[DP]; 
        ny = cy + dy[DP]; 
        if ( (nx<0) || (nx>=w) || (ny<0) || (ny>=h) || (board[nx][ny]=='0') ) { 
            //black 
            if (CP == -1) {//left turns into right 
                CP = 1; 
            } else { 
                //right turns into left, but DP rotates 90 degrees. 
                DP = (DP+1)%4; 
                CP = -1; 
            } 
        } else { 
            BP = cellBlock[nx][ny]; 
        } 
 
    } 
    //    cout << "t"<<n<<" : "<<BP<<" ; "<<DP<<" ; "<<CP<<endl; 
 
    return board[blockCornerX[BP][0][0]][blockCornerY[BP][0][0]]; 
} 
 

Problem E - Logo turtle
At first I was excited but then figured the problem has little to do with LOGO. It took me a while to understand that T - turn around means a 180 degrees turn. Anyway, the problem is solvable with dynamic programming.

Take for instance a recurrence F(p, n, d, minimize). If minimize is true, the function will find the minimum possible position offset if we only use commands higher than or equal to p, must change n commands, and d is 0 if we are facing right or 1 if we are facing left. At each recursive step, we can decide to alter the p-th character or not. If we do, we increase (d is 0) or decrease (d is 1) the position, or turn the direction and then will move F(p+1, nn, nd, minimize) positions.

The base case is when p is equal to the number of commands, there are no commands to make. However, remember that we must do n changes. If n is even, we can waste the changes by repeating all of the changes on a single command (and thus changing nothing). Else we return -INFINITE (if minimize is false) or INFINITE (if it is true).

Why do we need to minimize and maximize the result? Because the largest distance can be at some point that is negative. So, if the minimum value we can find is negative, we can negate it and find a possible max distance.

Edit: seems I passed system tests in all the problems. Good. Hopefully I will only do division 1 problem sets from now (unless the contest is div2 only, I guess).

Edit: Here is the code for E.

string commands; 
 
bool knownAnswer[101][51][2][2]; 
int  answer[101][51][2][2]; 
 
const int INF = 1000000; 
 
// Returns the minimum/maximum change in distance starting at command p. If we must 
// do n changes. The current direction is d (0 : positive, 1: negative). 
// 
int rec(int p, int n, int d, int wantMinimum) 
{ 
    int & res = answer[p][n][d][wantMinimum]; 
    if (! knownAnswer[p][n][d][wantMinimum]) { 
         
        res = (wantMinimum ? INF : -INF); 
         
        if (p==commands.size()) {  //if there are no more commands left, we 
                                   //cannot decide to change any more commands 
            if (n % 2 == 0) { 
                res = 0;      //won't move anything, the only possible offset is 0. 
            } 
        } else { 
            for (int doChange = 0; doChange < 2; doChange++) { 
                if ( (doChange==0) || (n > 0) ) { //can we actually change this? 
                    int nn = n; 
                    int nd = d; 
                    char com = commands[p]; 
                    if (doChange) { 
                        com = ( (com=='T') ? 'F' : 'T' ); 
                        nn--; 
                    } 
                    int x = 0; 
                    if (com == 'T') { 
                        nd = ! d; 
                    } else { //move forward (depending on your direction). 
                        if (d == 0) { 
                            x++; 
                        } else { 
                            x--; 
                        } 
                    } 
                    if (wantMinimum) { 
                        res = std::min(res, x + rec(p+1,nn,nd, wantMinimum) ); 
                    } else { 
                        res = std::max(res, x + rec(p+1,nn,nd, wantMinimum) ); 
                    } 
                } 
            } 
        } 
         
         
        knownAnswer[p][n][d][wantMinimum] = true; 
    } 
         
    return res; 
} 
 
int solve(int n) 
{ 
    memset(knownAnswer,0,sizeof(knownAnswer)); 
     
    int minim = abs( -rec(0,n,0, true) ); //minimum offset from this starting point 
    int maxim = abs( -rec(0,n,0, false) ); //maximum... 
    return std::max( minim, maxim); 
}