SRM 570: Blue

This is it, I am going blue today.

As I write this (Before challenge phase) I know that if it was not for a last second mistake, I would have actually had a good score in division 1 250. But this last mistake made me unable to submit.

Div1 250: The one with robot

A robot in an infinite grid has a program. For each integer a[i], it moves forward a[i] times, then rotates left a[i] times. This program is repeated T times, return abs(x) + abs(y) where (x,y) is the final position.

Let us represent directions by 4 integers: 0, 1, 2, 3. Rotating left x times really just does direction = (direction + x) % 4. The direction is an index for off set array, so moving by direction i means moving dx[i] units in x axis and dy[i] units in y axis. dx[] and dy[] should be in clockwise order.

The trick is to know that after running the program one time, the direction will change by either 0, 1, 2 or 3. x and y should also change.

If the direction changes by 0, repeating the program again will not change the direction, then final x = 4*x , final y = 4*y (where x,y are the position after running once).

If the direction changes by 1 or 3, then repeating the program FOUR times will take us to a total program that modifies the direction by 0. So we can just repeat four times to find out how many does this combined program change, multiply x and y by T/4, then repeat original program T%4 times.

If the direction changes by 2, then you just need to repeat 2 times.

// simulates program a one time, updating initial x,y and d. 
void doit(vector<int> a, long &x , long &y, int&d)
{
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    for (int i=0; i < a.size(); i++) {
        x += dx[d] * a[i];
        y += dy[d] * a[i];
        d = ( d + a[i]) % 4;
    }
}
long getdist(int T, vector <int> a)
{
    long x = 0, y = 0;
    int d = 0;
    // run once to know how will d change:
    doit(a, x,y,d);
    // Select the number of times to repeat the program so that d=0
    int r = 1;
    if (d == 0) {
        r = 1;
    } else if ( (d == 1) || (d==3 ) ) { 
        r = 4;
    } else {
        r = 2;
    }
    // Simulate how it is to repeat the program r times (Already done once)
    for (int i=0; i<r - 1; i++) {
        doit(a, x,y,d);
    }
    x = x * (T/r);
    y = y * (T/r);
    // Repeat T%r more times:
    for (int i=0; i<T%r; i++) {
        doit(a, x,y,d);
    }
    return abs(x) + abs(y);        
}

As usual, I only had 10 minutes to solve this problem. So I rushed a bit, and actually managed to do it all -- with the exception that in my rush I thought that when the direction changes by 3 you should repeat thrice instead of four. This was dumb because when I initially thought of the solution I knew it was 4 repetitions (The results modulo 4 are known after you do these problems for a while). But for some reason, when there was about one minute left, I did sums modulo 4 manually. I did 0+3 = 3 mod 4, 3+3 = 1 mod 4, then 1+3 = 0 mod 4. The mistake was that I accidentally had 3+3=1 mod 4, when it should be 2.

So I failed example cases. I had 40 seconds to debug. I didn't have time to find out what the issue was. Around 10 seconds after the end of the coding phase I figured what the mistake was.

But I think the real blunder was not to engineer the code better. I kept pasting stuff and redoing the bit of code for each d, I think this copy paste delayed me too much. This problem was workable for 10 minutes.

Later in the challenge phase, I found a solution that returned 0 in a case, so I challenged it (I knew that there was no difference between 0 and -25, so basically no risk). It turns out that was correct. That was clever actually, if d=2 after one run and T is even, the result is 0. There are other similar tricks. After that moment I just kept challenging it to gain more minuses.

Last words

Anyway, I am going to be blue today, but I will maintain my strategy. I think that with more practice I will be able to start solving div1 250s in less than 10 minutes without all these mess ups. And now that I am blue I have nothing to lose anymore. This was a consequence I foresaw after taking the decision to use this strategy. Short term rating is not the objective.

Of course, I spent the first 65 minutes of the match looking at div1 medium and hard. I think div1 medium should be meet in the middle (That n<=36 constraint?). Div1 hard might be my favorite kind of problem, super optimized dp. Or it might be some sort of brute force.