## Friday, April 06, 2012

### Codeforces Croc Champ 2012 - Round 1

As usual, I am too slow and to make matters worse, my slowness does not translate into a better chance to have a correct solution. This time I spent a lot of time in problem A, there was something I didn't quite get until 50 minutes later...

Both sequences are cyclic. When you put two cyclic sequences together, their pairs also form a cycle. This cycle will have size LCM(m,k) (I actually was trying to do a cycle of size m*k, which is also true, but it is harder to deal with step #2).

Since the cycle has size LCM(m,k) and due to constraints it will be less than 1000000, we can simply do iterations from i = 0 to LCM(m,k)-1, It will represent one pair in the cyclic sequence of pairs. Then just take a[i%m] and b[j%m], this play will be repeated n/LCM(m,k) times. If this play gives the first player a win, this means he will win n/LCM(m,k).

There will be n%LCM(m,k) plays that the previous loop does not count. Not a big deal, just to another iteration from i=0 to n%LCM(m,k) and do the same thing. Of course, you can also join both loops together using a small if-then-else to find the total number of times the pair appears.

int whoWins(char ach, char bch) {     //there are much simpler ways to do this, I can bet     if (ach == 'R') {         if (bch == 'S') {             return 1;         } else if (bch == 'P') {             return -1;         }     }     if (ach == 'P') {         if (bch == 'R') {             return 1;         } else if (bch == 'S') {             return -1;         }     }     if (ach == 'S') {         if (bch == 'P') {             return 1;         } else if (bch == 'R') {             return -1;         }     }     return 0;  }      int gcd(int a, int b) {     while (a != 0) {         int c = a;         a = b % a;         b = c;     }     return b; }  int lcm(int a, int b) {     return (a/gcd(a,b))* b; }      pair<int,int> solve(int n, string a, string b) {     int bWins = 0, aWins = 0;     int m = a.size(), k = b.size();     int L = lcm(m,k);      for (int i=0; i<L; i++) {         int times = 0; //how many times does this pattern repeat?         times = n / L;         if (n%L > i) {             times ++;         }                  int win = whoWins(a[i%m],b[i%k]);         if (win == 1) {             aWins += times;         } else if (win == -1) {             bWins += times;         }                }     return make_pair(bWins, aWins); }

During the match, I just did a Dijkstra variation using deques (because this is more optimized when the edge cost can be 1 or 0) There is probably a clever way to avoid Dijkstra, perhaps with dp. But here is my solution anyway.

You can see the input as a maze and the "glare" starts at bottom-right cell facing left. You need to find the minimum cost for the glare to reach top-left cell facing left as well.

It is always possible to move one square towards the glare's direction at cost 0. This means there is always an edge between nodes: (d1,x1,y1) and nodes (d2,x2,y2) where d2=d1 and x2,y2 change depending on the direction.

More importantly, if the glare is currently at the position of a column, we can choose to make the column magical, so we can rotate the facing direction towards any of the four possible values. This has cost 1 (We make the column magical). So this special edge that connects nodes (d1, cx,cy) and any (d, cx,cy) such that cell (cx,cy) has a column has cost 1.

The minimum cost path can be found using Dijkstra's algorithm. And again, you can implement it very easily in a way that looks like BFS using a deque. Just move edges that increase the current cost to the back of the queue, and edges that don't to the front.

int n, m; char board;  int Distance;  const int dx = {0,0,1,-1}; const int dy = {1,-1,0,0};   const char BINF = 0x7F; const int INF = 0x7F7F7F7F;  int solve() {     deque<int> Q;     memset(Distance, BINF, sizeof(Distance));     Distance[n-1][m-1] = 0;     Q.push_back(3); Q.push_back(n-1); Q.push_back(m-1);     while (! Q.empty()) {         int d = Q.front(); Q.pop_front();         int y = Q.front(); Q.pop_front();         int x = Q.front(); Q.pop_front();                  if (board[y][x] == '#') {             //column (can switch)             for (int nd=0; nd<4; nd++) {                 if (Distance[nd][y][x] > Distance[d][y][x]+1) {                     Distance[nd][y][x] = Distance[d][y][x]+1;                     Q.push_back(nd); Q.push_back(y); Q.push_back(x);                 }             }         }         //just move!         int nx = x + dx[d];         int ny = y + dy[d];         if (nx >= 0 && nx < m && ny >= 0 && ny < n) {             if (Distance[d][ny][nx] > Distance[d][y][x]) {                 Distance[d][ny][nx] = Distance[d][y][x];                 Q.push_front(nx); Q.push_front(ny); Q.push_front(d);             }         }     }     int& dis = Distance;     return ( (dis==INF)? -1: dis); }

I wish I opened this problem first. There is something very cute about the spirals of size (K+2) and size K, it is that the spiral of size (K+2) is almost like the subtraction between the (K+2)x(K+2) rectangle and the KxK spiral in the middle of it. The only difference is that you also subtract another cell from it (The one bellow the top-left cell).

So, assuming you have accumulated the numbers so you can find the sums of each rectangle quickly. You just need a O(n^n) loop for each K, always subtracting from each rectangle of size K*K the appropriate spiral of size (K-2)*(K-2) and another cell. This should be enough to work in time.

int n,m; int a; int sum; //sum[x][y] is the sum of the rectangle (i<x), (y<j);  int espiral;  int solve() {     // This just makes the accumulated matrix so we can calculate sums of      // the contents of arbitrary rectangles pretty fast inside other loops.      memset(sum, 0, sizeof(sum));     for (int i=1; i<=n; i++){         for (int j=1; j<=m; j++) {             sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i-1][j-1];         }     }      // initially for k=3, let us encode the shape and calculate the 3 x 3     // spirals. In reality, we can consider a single painted cell as a spiral of     // size k=1, and simplify this a lot. But for now, we will leave it like this:     const char* shape = {     "xxx",     "..x",     "xxx"};          int pid = 0;     int maxFound = -500*500*1000;     for (int i=0; i+3<=n; i++) {         for (int j=0; j+3<=m; j++) {             espiral[pid][i][j] = 0;             for (int x=0; (x<3) && (i+x < n); x++) {                 for (int y=0; (y<3) && (j+y < m); y++) {                     if (shape[x][y]=='x') {                         espiral[pid][i][j] += a[i+x][j+y];                     }                 }             }             maxFound = std::max(maxFound, espiral[pid][i][j] );         }     }          //now try larger values of k     for (int k=5; (k<=n) && (k<=m); k+=2) {         int id = !pid;         for (int i=0; i+k<=n; i++) {             for (int j=0; j+k<=m; j++) {                 //this is fun, we can calculate a larger spiral by subtracting a smaller                 // one from the k x k square.                 int spir = sum[i+k][j+k] - sum[i+k][j] - sum[i][j+k] + sum[i][j]; // K x K square                 spir -= espiral[pid][i+1][j+1]; // The smaller spiral                 spir -= a[i+1][j]; // The one cell to remove                 espiral[id][i][j] = spir;                 maxFound = std::max(maxFound, spir);             }         }         pid = id;     }     return maxFound;           } vexorian said...

Behold, for I have acquired the power of Orange!

I am ultra citric now!

Mario Ynocente Castro said...

Do you have any idea about how to solve D, I found it harder to solve than E, maybe some theory is needed

Mario Ynocente Castro said...

Seems like I got something taking cases mod 3. TurtleShip said...

Minor typo,, I think.
//sum[x][y] is the sum of the rectangle (i sum[x][y] is the sum of the rectangle (i<x), (j<y);

Thx for the nice blog :-)