Wednesday, February 13, 2013

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.

2 comments :

tehqin said...

On the plus side the editorial for the 900 should be easy. I'm surprised it went unsolved in the contest. It didn't take me long to solve in the practice room. (Very unusual for div1 hards) Maybe because I found the idea similar to ToyTrain?

xiaodao said...

Don't take it so hard, anyway, the rating is not everything, we all see you are on the right road .. !! ... The most glorious day is not the day finally become success ... but the day he extricated himself from the predicament .. :) cheer up !! ..