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

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;


}

4 comments :

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 :-)