SRM 559: Just wow

This one was tough. I know ad hoc 250s are great. And I love them. I also liked this problem a lot. But it felt way too much for 250.

The good thing is that I managed to mostly avoid an ad hoc solution. Instead, mine relies on inclusion-exclusion magic.

Div1 "Easy": The one with knights

You have a (possibly large) chess board. Your knight can move from cell (x,y) to cells (x+a,y+b), (x+a,y-b), (x-a,y+b), (x-a,y-b), (x+b,y+a), (x+b,y-a), (x-b,y+a) and (x-b,y-a). If the cell does not exist, the move is invalid. Return the total number of cells from which there are exactly k moves. The values are from 1 to 10⁹. a and b are never the same. Also, 2*max(a,b) is always less than min(number of columns, number of rows).

That last constraint was something very suspicious. I guessed that this constraint reduces the number of corner cases. When the people behind these contests reduce the number of corner cases, it can only mean that the problem is very complicated...

And it was. At first I thought to just solve the problem. There are 9 special cases. Some are easy It is impossible to have cells with (k=0, k=1, K=5, k=7) valid moves (In realty, k=0 and k=1 should be possible if not for the suspicious constraint). It is not completely obvious, but K=3 is possible. I thought that this was going to be a corner case, but nope.

Eventually, I returned to my senses and figured that finding a formula for each of the 4 remaining cases would have been crazy and bug-prone. There got to be a better way. Good thing I could think of it. But the time I wasted trying to think of the formulas and then debugging the solution (which turned out to be very long) gave me a very low score and no time to solve the medium-difficulty problem.

Here is the solution anyway: Let us define a move as (dx,dy) so that you move from cell (x,y) to (x+dx, y+dy). It is simple to know the number of cells in which this move is valid. There are 2*dx invalid rows and 2*dy invalid columns. So just multiply the number of remaining rows and columns and find the result.

Let us count the number of cells from which two specific moves (dx1, dy1) and (dx2, dy2) are valid. (And possibly other moves). This is a bit harder. But indeed, you can find the rectangle of cells from which these moves (but not necessarily only these moves) are valid.

For any subset of the 8 available moves, the number of cells from which all of the moves in the subset are valid are also a rectangle, and thus we can calculate this value for each subset of moves. Let us use bit masks to represent these sets. Now let us store the results in an array valid[mask] that for each mask (subset of moves) returns the total number of cells in which all of the moves in the bit mask are valid).

Now, if we wanted to find the total number of cells from which exactly k moves are valid. We would just need to find all subsets that have exactly k and sum their valid[mask]. Right?... NO!. You have not been paying attention. Because valid[mask] may include cells from which other moves are valid.

Thus what we want to somehow create is another array called exactly[mask] that gives us the number of cells from which the only moves allowed are those in the bit mask.

The key

The key is to observe that valid[255] = exactly[255]. In other words, since there are only 8 moves. Then all the cells valid[255] are also the cells from which the only valid moves are the 8 ones (note that 255 is the subset that contains all 8 moves).

And that is cool. Because we can now calculate the results of exactly[mask] for all masks that have exactly 7 bits. Yeah! Imagine a subset of moves that lacks exactly one moves in that case, valid[mask] will return all the cells that allow those 7 moves. This includes all the cells that allow the 8 moves AND the cells that allow only the 7 moves. We can find exactly[mask] with a simple subtraction.

In fact, for every bit mask mask. exactly[mask] is equal to valid[mask] minus sum(exactly[mask2]) for each mask2 of which mask1 is a proper subset of. You can build exactly[] using this method. Then sum all the values of exactly[mask] for all masks that have exactly k elements (1 bits).

Solution

typedef long long int64; 
#define long int64 
 
struct HyperKnight 
{ 
    long countCells(int a, int b, int numRows, int numColumns, int k) 
    { 
        // The 8 moves: 
        long dx[8] = {a,a,-a,-a,b,b,-b,-b}; 
        long dy[8] = {b,-b,b,-b,a,-a,a,-a}; 
         
        long exactly[256]; 
        long result = 0; 
         
        // We visit the masks from highest to smallest, this way we 
        // can guarantee that all subsets with more elements than the 
        // current one have already been solved. 
        for (int mask = 255; mask >= 0; mask--) { 
            long valid = 0; 
            // valid : How many cells allow the moves in mask? 
            // (and possibly other moves) 
             
            // In the explanation valid is an array, but we do not really 
            // need to remember all its values, just valid[mask]. 
             
            int n = 0; 
            // Find the rectangle of such cells: 
            long left = 0, right = 0, up = 0, down = 0; 
            for (int i=0; i<8; i++) { 
                // For each move that belongs to the mask subset: 
                if (mask & (1<<i)) { 
                    n++; 
                    // update the rectangle's dimensions 
                    if (dx[i] < 0) { 
                        left = std::max(left, -dx[i]); 
                    } else { 
                        right = std::max(right, dx[i]); 
                    } 
                    if (dy[i] < 0) { 
                        up = std::max(up, -dy[i]); 
                    } else { 
                        down = std::max(down, dy[i]); 
                    } 
                } 
 
            } 
            // Area of the rectangle 
            valid = (numRows - left - right) * (numColumns - up - down); 
            // if we make sure to set valid = 0 when the moves are too large 
            // this makes the solution work even without the special constraint 
             
            exactly[mask] = valid; 
             
            // For each subset with more elements than this one. 
            // (mask must be a proper subset of mask2): 
            for (int mask2 = mask + 1; mask2 < 256; mask2++) { 
                if ( (mask & mask2) == mask ) { 
                    // remove the cells that allow more moves than mask. 
                    exactly[mask] -= exactly[mask2]; 
                } 
            } 
            // n is the number of moves in the mask. 
            // now exactly[mask] contains the number of cells from which the ONLY 
            // valid moves are those in the mask: 
            if (n == k) { 
                result += exactly[mask]; 
            } 
        } 
        return result; 
    } 
}; 
#undef long 

Div1 medium

By the time I finished my 250, I did not really have much time to try to code a solution. But I think it is easy to just fix the root and the depth of the tree. Then count the number of ways to have those given root and depth following the conditions. This root shall have one or two children. One child should have exactly (depth-1) depth and be full. The other can have (depth) depth and not be full (but to the right). These are all similar subproblems. Implementation is probably messy.

Opinions / etc?

I liked the match, I just wish I solved 250 faster. What about you?