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.
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;
doit(a, x,y,d);
int r = 1;
if (d == 0) {
r = 1;
} else if ( (d == 1) || (d==3 ) ) {
r = 4;
} else {
r = 2;
}
for (int i=0; i<r - 1; i++) {
doit(a, x,y,d);
}
x = x * (T/r);
y = y * (T/r);
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.
