SRM 514

Oh boy, two huge mistakes related to the poorly thought % operator in C++.

Div1 500 MagicalGirlLevelTwoDivOne

I did not let it trick me and I actually found the key to solve the problem quite quickly.

Imagine we have n+1 numbers in a column:

[][][][][][]...[]

The two consecutive groups of n numbers will overlap in exactly (n-1) numbers. Let us say that the sum of all the numbers in this overlap area is already known. There are two cases:

* The overlap sum is even: Then both of the remaining numbers must be odd so that the two n-sized areas are odd.
* The overlap sum is odd: Then both of the remaining numbers must be even so that the two n-sized areas are odd.

Now, this is the nice part, this means that for every column the parity of F[x][y] must be equal to the parity of F[x+n][y]. The same is true for rows, the parity of F[x][y] must be equal to the parity of F[x][y+n]. And this applies everywhere.

In fact, this means that we only need to decide the parity for the cells in the first n x m rectangle. This is an easier problem because n and m are at most 10. For each cell F[x][y] where (x < n) and (y < m) there are different numbers of ways to have that cell even or odd, it depends of all the cells F[x2][y2] such that (x2 % n = x) and (y2 % m = y). All of those cells must be even or odd numbers depending of the chosen parity for F[x][y] and if they are . there are 5 or 4 different digits for each of those cells. The number of ways to have a parity in cell F[x][y] can be calculated easily with a single n^4 loop.

Finally, we need to pick the parities. Imagine a certain row of m=6 elements was 010101 , now the first group of m elements will have an odd total parity and that's good. The second group of m elements will be: 10101 . 0 , because we have already determined that the parities are cyclic. The parity will be the same as the first group. So we should just need to worry that in our m x n rectangle , the rows and columns all make odd parities. The final result can be found with a dp. Just remember the current parities of each column and the parity of the current row and select 0 or 1 for the parity of each cell.

I took more time than necessary because at first I thought I could use a slower but simpler to implement dp, that just takes the 2^m parities of the columns and a current row number. (Needs to try 2^m row combinations for each row, in total 2^(2*m)*n). It turned out to be too slow. So I moved to the other approach.

const int MOD = 1000000007;

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct MagicalGirlLevelTwoDivOne
{
    long long fact[10][10][2];
    long long dp[11][11][2][1024];
    vector<int> vmasks;
    int theCount(vector <string> palette, int n, int m)
    {
        int h = palette.size();
        int w = palette[0].size();
        
        // fact[y][x][k] is the number of ways to have
        // parity k (0 : even , 1 : odd) in cell [y][x]
        // Where y < n and x < m.
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                for (int k=0; k<2; k++) {
                    long long & p = fact[i][j][k];
                    p = 1;
                    for (int ii=i; ii<h; ii+=n) {
                        for (int jj=j; jj<w; jj+=m) {
                            if ( palette[ii][jj] == '.' ) {
                                p = (p * (4+k) ) % MOD;
                            } else if (palette[ii][jj]%2 != k) {
                                p = 0;
                            }
                        }
                    }
                }
            }
        }

        // dp[y][x][r][mask] is the total number of ways to assign the parities
        // if :
        // * We have already assigned the parities of the cells previous to (y,x)
        // * The current parity of the row is r (0 or 1).
        // * The current parity of the j-th column is the j-th bit of mask.
        //
        memset(dp,0,sizeof(dp));
        dp[n][0][0][ (1<<m)-1 ] = 1;
        for (int y=n-1; y>=0; y--) {
            for (int x=m; x>=0; x--) {
              for (int r=0; r<2; r++) {
                for (int mask=0; mask<(1<<m); mask++) {
                    if (x==m) {
                        if ( r == 1) {
                            dp[y][m][r][mask] = dp[y+1][0][0][mask];
                        } else {
                            dp[y][m][r][mask] = 0;
                        }
                    } else {
                        dp[y][x][r][mask] = 0;
                        for (int k=0; k<2; k++) {
                            int nmask = (mask ^ (k<<x));
                            int nr = (r^k);
                            dp[y][x][r][mask] += (fact[y][x][k] * dp[y][x+1][nr][nmask]) % MOD;
                        }
                        dp[y][x][r][mask] %= MOD;
                    }
                }
              }
            }
        }
        return dp[0][0][0][0];
    }
};

Div 250 MagicalGirlLevelOneDivOne
Things are doing great, it seems that when I finished 500 and made sure it was correct I was first at my room and I had a very good position. I opened 250 and then...

It seemed a little abstract. At the end after tons of thinking I decided to do what I should have done from the beginning, I coded a program that simulated a BFS on a 100x100 board to find any pattern related to n-knight moves. The results were nice.

For a 2-knight, it turns out that all of the cells were reachable. I tried many other even numbers and it was always possible.

More cooler When I tried 3-knight, it was different, the reachable cells formed a checkered board pattern:

x.x.x.x.x.x
.x.x.x.x.x.
x.x.x.x.x.x
.x.x.x.x.x.
x.x.*.x.x.x
.x.x.x.x.x.
x.x.x.x.x.x
.x.x.x.x.x.

The asterix is (0,0) and every x is a reachable cell. This turned out to seem true for all odd number.

So, if there is an even number in the allowed n-knight moves, the solution is always possible. Then we have to worry only about odd-moves, but note that since the checkered board pattern is always there, it does not matter what combination of odd knight moves you use, the reachable cells are always the same in the checkered board.

Leads me to a very simple solution:

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct MagicalGirlLevelOneDivOne
{
    string isReachable(vector <int> jumpTypes, int x, int y)
    {
        for_each(n, jumpTypes) {
            if (*n % 2 == 0) {
                return "YES";
            }
        }
        return ( (x&1) == (y&1) ) ? "YES": "NO";
    }
};

Blunder
Did you notice the blunder? At first, I was a little paranoid that the solution cannot be so easy. I initially thought that when n is 1, the 1-knight moves are also always possible. But after trying the program, it seemed that it was still an odd number and followed the same rules.

The challenge phase came. I eventually saw that a solution using the same logic was challenged.

... It was some time after that I noticed the bug. Someone designing C didn't agree with making % compatible with the concept of true modulus. Negative numbers behave different than you would expect -1 % 2 is not 1 , it is -1. I knew that, but I just didn't think of that during the match. I figured out that my solution was wrong and it was eventually challenged.

Then I made another blunder, I tried to exploit this knowledge to score some challenges. But I misread code / didn't notice that in the case when the number is a multiple of the second operand of the % operation, it still returns 0 regardless of whether the first one is negative. I scored two wrong challenges that way.

The final outcome, I increased my rating to 2073. Which is barely one rating point above my previous maximum. It makes me wonder what would have happened if I didn't break rule #2: DO NOT CHALLENGE.

Here's a fixed version of the code for 250, note that it is still incredibly simple.

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct MagicalGirlLevelOneDivOne
{
    string isReachable(vector <int> jumpTypes, int x, int y)
    {
        for_each(n, jumpTypes) {
            if (*n % 2 == 0) {
                return "YES";
            }
        }
        return ( (x+y) % 2  == 0) ) ? "YES": "NO";
    }
};