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 :

Behold, for I have acquired the power of Orange!

I am ultra citric now!

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

Seems like I got something taking cases mod 3.

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

Post a Comment