SRM 623: Saved by the challenge phase

Div1 300: The evil one

This problem was evil. Let me explain, you have a board of maximum size 20x20, some cells contain apples, some pears, some are empty. A valid move is to move a fruit to an empty cell. You can do at most `K` moves. The objective is to maximize the size of a rectangle containing only apples. What is the maximum?

Say you already picked an arbitrary rectangle, there are `O(n^4)` of those. There are two things that are important about this rectangle: `a` : Number of apples in side, `p` Number of pears inside, `e` number of empty cells inside. You can also know the number of apples/pears/empty cells outside the square. Finding this values is a complicated implementation part. Also, I think too slow for python, so I tried to do something in c++, using lambdas of course. It took eons. But when I finally did it , I had a new problem...

Knowing that information about the rectangle we need to find the minimum number of moves needed to have only apples in the rectangle.

At first I was trying something very wrong: Move each pear to a (different) empty cell outside, then move all the apples inside. This took me ages to debug, and when I finally passed system tests with it, I was about to click submit when I started to wonder "Is this really it?" , and I noticed that noooo, the minimum number of moves is much trickier to find. Hence the examples were weak.

So what is the real optimal strategy? Well, the first issue is that we only need one empty cell in the board. We can keep reusing it to do all the moves. Then we have this: If there are any empty cells in the square, it is easy to see that it is optimal to just move any outside apples and cover them. The remaining case is when there are some pears inside the rectangle, at least one empty cell outside and enough apples outside. A single pear is treated like this: Move pear to empty cell, move apple to the position the pear was in, this leaves an empty cell in the apple's position, and we can repeat.

So in fact, the minimum number of moves is equal to:

• 0 if all the cells already contain apples.
• # of empty cells inside the rectangle, if the rectangle contains no pears.
# of empty cells + 2 * number of pears inside the rectangle, if and only if there is at least one empty cell in the board

int getBoard(vector<string> board, int K)
{
    // stuff to count the number of apples / pears / empty inside a rectangle:
    int W = board.size(), H = board[0].size(); 
    map<char, vector<vector<int>>> total;
    string chars = ".AP";
    for ( char ch: chars ) {
        vector<vector<int>> t(W+1, vector<int>(H+1,0));
        for (int i = 1; i <= W; i++) {
            for (int j = 1; j <= H; j++) {
                int x = ( board[i-1][j-1] == ch );
                t[i][j] = x + t[i-1][j] + t[i][j-1] - t[i-1][j-1];
            }
        }
        total[ch] = t;
    }
    auto rectangle = [&](char ch, int x0, int x1, int y0, int y1) {
        auto &t = total[ch]; 
        return t[x1][y1] - t[x0][y1] - t[x1][y0] + t[x0][y0];
    };
    
    int A = rectangle('A', 0, W, 0, H);
    int E = rectangle('.', 0, W, 0, H);
    
    int res = 0;
    for (int x0 = 0; x0 < W; x0++) {
        for (int y0 = 0; y0 < H; y0++) {
            for (int x1 = x0 + 1; x1 <= W; x1++) {
                for (int y1 = y0 + 1; y1 <= H; y1++) {
                    // the actual logic:
                    // inside:
                    int e = rectangle('.',x0,x1,y0,y1);
                    int a = rectangle('A',x0,x1,y0,y1);
                    int p = rectangle('P',x0,x1,y0,y1);
                    
                    // out side:
                    int na = A - a;
                    int ne = E - e;
                    
                    if (e <= na) {
                        int x = e;
                        int mov = x;
                        na -= x;
                        a += x;
                        e = 0;
                        ne += x;
                        if (mov <= K) {
                            if (p == 0) {
                                res = std::max(res, a);
                            } else if ( (p <= na) && (ne >= 1) && (mov + 2*p <= K) ) {
                                res = std::max(res, a + p);
                            }
                        }
                    }
                }
            }
        }
    }
    return res;
}

Div1 450: The difficult one

All I can think of is that we can imagine a different problem, the points stay static and the player moves either in a vertical line upwards (increasing `y` coordinate) or in a diagonal (incrementing `y` and incrementing or decrementing `x`).

Challenge phase

I took too long to solve div1 300, but I did learn that the example cases were weak. So I thought of a challenge case to make my initial solution fail (using only one empty square). Luckily my room wasn't very aggressive and I could find 2 solutions with that wrong idea and earned 100 points.