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...

Problem A link

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); 
} 
 

Problem B link

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[1000][1000]; 
 
int Distance[4][1000][1000]; 
 
const int dx[4] = {0,0,1,-1}; 
const int dy[4] = {1,-1,0,0}; 
 
 
const char BINF = 0x7F; 
const int INF = 0x7F7F7F7F; 
 
int solve() 
{ 
    deque<int> Q; 
    memset(Distance, BINF, sizeof(Distance)); 
    Distance[3][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[3][0][0]; 
    return ( (dis==INF)? -1: dis); 
} 

Problem C link

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[500][500]; 
int sum[501][501]; //sum[x][y] is the sum of the rectangle (i<x), (y<j); 
 
int espiral[2][501][501]; 
 
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[3] = { 
    "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; 
     
     
}