September 5, 2021 Single Round Match 812 Editorials

SpireAttack

There are two main observations we have to make.

First, the number of cards in our hand is small: only up to 50.

Second, the number of cards we’ll actually play is also small. As we have three actions and each card costs at least one action, we will clearly play at most three cards.

Together, these two observations tell us that we can use brute force: examine all possible sets of one, two, and three cards, for each of them check whether you have enough actions to play it, and if you do, look at the total damage you would deal. Among all those options, the one that deals the most damage is our answer.

There is no need to be too clever with the implementation, either: one, two, and three nested cycles are a perfectly valid approach.

public int dealMostDamage(int N, int[] actions, int[] damage) {
    int answer = 0;
    for (int a=0; a<N; ++a) 
        if (actions[a] <= 3)
            answer = Math.max( answer, damage[a] );
    for (int a=0; a<N; ++a) for (int b=a+1; b<N; ++b)
        if (actions[a] + actions[b] <= 3)
            answer = Math.max( answer, damage[a]+damage[b] );
    for (int a=0; a<N; ++a) for (int b=a+1; b<N; ++b) for (int c=b+1; c<N; ++c) 
        if (actions[a] + actions[b] + actions[c] <= 3)
            answer = Math.max( answer, damage[a]+damage[b]+damage[c] );
    return answer;
}

Incorrect greedy solution: Some solvers may be tempted to solve the task greedily: sort the cards according to the amount of damage they deal per action spent, and play them in that order. This approach would work if we could play cards partially – e.g., if it was possible to play half a card that costs 2 actions and deals 8 damage for 1 action to deal 4 damage. But as we cannot do that, the greedy strategy will sometimes fail. For example, suppose we only have two cards: one costs 2 actions and deals 20 damage, the other costs 3 actions and deals 21 damage. The first one deals more damage per action (10 versus just 7 for the other card), but we should play the card that deals 21 damage instead.

Correct greedy solution: The correct solution we have shown above has time complexity O(N^3): we look at all triples of cards. It is also possible to solve the task in linear time, i.e., in O(N), by adding a valid greedy step. The observation we need:

• We clearly cannot play more than one card with cost 3.
• We clearly cannot play more than one card with cost 2.
• We clearly cannot play more than three cards with cost 1 each.

Thus, we can iterate over the entire hand once and only keep the best card that costs 3, the best card that costs 2, and the three best cards that cost 1 each. This step can be done in linear time. And once we are done, we are left with at most five cards in our hand and we can examine all options what subset of them we should play in constant time.

An even better solution: The task would also be efficiently solvable if we had a much higher number of actions to spend. We can solve this more general version of the problem using dynamic programming: we’ll process the cards one at a time, and we will maintain a table in which we have, for each number of actions spent on the cards we already processed, the maximum amount of damage we could have dealt using those cards.

MarsHabitats

In the language of graph theory, the task we are given is as follows: our goal is to construct a cubic graph (i.e., a graph in which each vertex has degree 3) such that each vertex has the correct distance from vertex 0. The graph may contain self-loops and multiple edges connecting the same two vertices.

If we had the restriction that each vertex must have a degree at most 3, the task would be easy: we could just sort all vertices according to their desired distance from vertex 0, connect them into a line, and set edge lengths accordingly. For example, if we want distances {0, 10, 7, 7, 25, 26}, we would have the line of vertices 0-2-3-1-4-5, with edge lengths 7, 0, 3, 15 and 1 from left to right. In this construction the first and the last vertex have degree 1, and each other vertex has degree 2.

Before we complete the construction, we now need to make an observation about the existence of a solution. What is the sum of degrees in a graph? The sum of degrees of all vertices must clearly be equal to twice the number of edges – because each endpoint of each edge is counted once, and each edge has two endpoints. Note that this implies that in each graph the sum of degrees of all vertices must always be even.

This tells us that a cubic graph with N vertices exists if and only if N is even. Why? The sum of all vertex degrees in a cubic graph is 3*N. If N is odd, 3*N is odd, and thus such a graph cannot exist – we would need half an edge somewhere in the graph.

Now let’s go back to our line that connects all vertices. All we need to do is to add additional edges that do not change any distances. For example, if we add a copy of an edge that’s already in the graph, the distances clearly won’t change. We can double every second edge along our path. E.g., in the example we had above, instead of 0-2-3-1-4-5 we could use 0-2=3-1=4-5, where “=” denotes two parallel edges. This new line still has the same distances as the previous one. And now all vertices have degree 3, except for the two endpoints. Those (for N even) have degree 1, so we can attach a self-loop to each of them and we are done.

There are also many other solutions. For example, we can start with the line as shown above, and now we can repeat: take any two vertices that don’t have three edges yet, and connect them using an edge of the maximal possible length 1,000,000. Clearly, these edges won’t influence distances regardless of which vertices we connect.

struct edge { int destination, length; };

vector<int> design(vector<int> distances) {
    int N = distances.size();
    vector<int> answer;
    if (N % 2 == 1) return answer;

    // sort all vertices according to distance
    vector< pair<int,int> > order;
    for (int n=0; n<N; ++n) order.push_back( { distances[n], n } );
    sort( order.begin(), order.end() );

    // connect them into a line
    vector< vector<edge> > G(N);
    for (int n=0; n+1<N; ++n) {
        int u = order[n].second, v = order[n+1].second;
        int len = order[n+1].first - order[n].first;
        G[u].push_back( {v,len} );
        G[v].push_back( {u,len} );
    }

    // add useless self-loops so that each degree is at least 2
    for (int a=0; a<N; ++a) if (G[a].size() <= 1u) {
        G[a].push_back( {a,1000000} );
        G[a].push_back( {a,1000000} );
    }

    // add useless edges so that each degree is exactly 3
    for (int a=0; a<N; ++a) for (int b=a+1; b<N; ++b) {
        if (G[a].size() == 2u && G[b].size() == 2u) {
            G[a].push_back( {b,1000000} );
            G[b].push_back( {a,1000000} );
        }
    }

    // construct and return the report
    for (int n=0; n<N; ++n) for (int i=0; i<3; ++i) {
        answer.push_back(G[n][i].destination);
        answer.push_back(G[n][i].length);
    }
    return answer;
}

GuessForMoney

The payoff P for the game should clearly be equal to the expected number of questions Adam will ask if he uses a strategy that minimizes it. This strategy is clearly some version of binary search.

Any non-stupid strategy can be represented using a binary search tree. Given such a tree, the expected number of questions can be calculated as follows: For each x, we look at the depth of x in the tree. The depth tells us the number of guesses we’ll make if x is the number Genevieve selected. The answer we seek is the average of these numbers.

As there are exactly N numbers, the average number of guesses is simply the total number of guesses, divided by N. The optimal strategy therefore corresponds to the tree in which the sum of depths of vertices is minimized.

From this point the easiest way to continue is to realize that we can very easily construct the shape of such a tree and calculate its sum of depths. We will simply build the tree from top to bottom, one layer at a time. Each layer will be completely full, until we run out of vertices. The last layer may then be filled only partially. This construction gives us a very simple implementation:

long solveByConstructingTreeShape(long N) {
    long sumOfDepths = 0;
    long remain = N;
    for (int d=0; ; ++d) {
        long atDepth = 1L << d;
        long use = Math.min( atDepth, remain );
        sumOfDepths += use * (d+1);
        remain -= use;
        if (remain == 0) break;
    }
    return sumOfDepths;
}

Another solution gets to the point that we want the minimum sum of depths in a BST and continues by realizing that the ideal binary search in which we always ask the question in the middle of the current interval must always produce an optimal tree in which all layers except for the last one are fully filled. Thus, we just need to calculate the sum of vertex depths for this particular tree. A naive way would be to do this recursively. For each of the N numbers we ask at least the first question. If we guessed correctly, we are done, if not, we have the same problem with approximately half the numbers, and we sum the remaining questions recursively.

long solveNaively(long N) {
    if (N == 0) return 0;
    if (N == 1) return 1;
    long answer = N;
    answer += solve(memo, (N-1)/2 );
    answer += solve(memo, N/2 );
    return answer;
}

This solution is correct but too slow: it runs in O(N) time. But we can easily speed it up by adding memoization. (Exercise: show that only O(log^2 N) distinct inputs will be evaluated.)

ZeroBoard

Suppose we color the board like a chessboard. We claim that if the sum of white squares does not equal the sum of black squares, there is no solution. Proof: each step will add the same amount to one white and one black square, so the sums will never be equal, but on a board with all zeros they are equal.

This condition is also sufficient for a solution to exist.

Suppose we have any three cells X, Y, Z such that XY and YZ are adjacent. Let x, y, z be the values in these cells. We can now set cell Z to zero as follows:

• If y >= z, we can just subtract and change (x,y,z) to (x,y-z,0).
• If y < z, let d = z-y. We can first add d to x and y, producing (x+d,z,z), and then subtract z from the last two to get (x+d,0,0).

Note that in at most two steps we set one cell to zero.

Also note that the sum of the entire board did not increase. This extra observation tells us that all the numbers on the board have to remain small and there is no risk of an overflow. (Making observations like this one is a good idea if the task statement imposes some constraint. In other similar problems other similar constructions can easily create situations in which the numbers on the board grow exponentially in the number of steps.)

We can repeatedly use the above rule to set almost the entire board to zeroes. E.g., we can go over all the cells in row major order and set them to zero until we are only left with the last two cells on the board. As the sum of white and black cells on the board is the same after each step, now that everything except for the last two cells are zeros we know that the last two cells must be equal and we can finish the solution.

ClassifyQuads

This problem looks ugly, but with a good observation we can actually implement a fast solution reasonably easily. 

The first important observation is that if we have N points, there are O(N^2) pairs of points but they only determine O(N) distinct vectors. (For each vector determined by two points we can shift the two points simultaneously to move the origin of the vector into a corner of the grid.) We will start by generating all distinct vectors.

We can now do most of the counting as follows:

• For each vector (r,c):
  • If the line segment from (0,0) to (r,c) passes through at least two grid points, this is a viable “line segment” shape.

• For each pair of vectors that are not parallel and therefore determines a triangle:
  • Let X be the number of grid points on the sides of the triangle (excluding vertices).
  • If X > 0, we have a valid “triangle” shape.
  • We have 2*X valid “letter-P” shapes for which the triangle is the convex hull.
  • Let Y be the number of grid points strictly inside the triangle.
  • We have 3*Y valid “concave quad” shapes.

In order to count the grid points along a segment from (0,0) to (r,c) we just need to compute gcd(r,c).

We can use Pick’s theorem to count the grid points inside a triangle.

For each shape generated during the above process we can look at the size of its bounding box and in constant time determine the number of ways it can actually be positioned in the grid.

As all coordinates are O(N) in value, gcd runs in O(log N) and therefore the whole solution up to this point runs in O(N^2 log N).

What remains are the “convex quad” shapes and the “figure eight” shapes. Each convex quad corresponds to two figure eights, so we just need the convex quads. The easiest way to count these is to count all unordered 4-tuples of points and subtract those that generate other shapes. (We already know almost everything we need, the only extra information we’ll need is the number of collinear 4-tuples, which can easily be computed while counting the line segment shapes.)