August 27, 2019 Single Round Match 765 Editorials

MilkConsumption

The key observation is that whenever a bunch of countries has an average consumption of X litres per person, at least one of those countries must have an average consumption of at least X litres per person. (If all countries drink less than X litres per person, the average over them cannot be X.)

Hence, there is always an optimal solution that consists of a single country. We can compute the average for each country separately, and output any one country that reaches the maximum (or any subset of those countries).

For a nicer implementation, it is not necessary to compute the averages as floating-point numbers. Instead, we can compare any two countries exactly using 64-bit integers. Instead of evaluating whether milk1/people1 > milk2/people2 we can check the equivalent condition milk1*people2 > milk2*people1. (The checker does a similar computation when verifying the output of your submission, so that the verdict cannot be affected by rounding errors.)

Tunnel

This is a very simple task on dynamic programming. We will process the tunnel one row at a time. For each cell of each row we will compute the following value: if it’s possible that the spaceship reached this cell by moving forward, what is the smallest number of keystrokes to bring it there?

In the first row, the only such cell is the cell where we start, and the number of keystrokes is zero.

When processing a row, for each position you could reach try all valid number of keypresses (from -rate to +rate) and remember the best way in which you could reach each of the cells in the next row.

public int minKeystrokes(String[] level, int rate) {
    // initialize the values for row 0
    int C = level[0].length();
    int[] where = new int[C];
    for (int c=0; c<C; ++c) where[c] = 123456789;
    for (int c=0; c<C; ++c) if (level[0].charAt(c) == 'v') where[c] = 0;
    for (int r=1; r<level.length; ++r) {
        // use the values for row r-1 to compute the values for row r
        // initially, we do not know any way to get to row r
        int[] newwhere = new int[C];
        for (int c=0; c<C; ++c) newwhere[c] = 123456789;
        // for each column in row r-1 that was reachable...
        for (int c=0; c<C; ++c) if (where[c] < 123456789) {
            // ... try all possible movements left and right...
            for (int c2=c-rate; c2<=c+rate; ++c2) {
                // make sure you don’t leave the level or hit a wall
                if (c2 < 0 || c2 >= C) continue;
                if (level[r-1].charAt(c2) == '#') continue;
                if (level[r].charAt(c2) == '#') continue;
                // if you found a valid way to move, update info
                int curr = where[c] + Math.abs(c-c2);
                newwhere[c2] = Math.min( newwhere[c2], curr );
            }
        }
        // and move on to the next row
        where = newwhere;
    }
    int answer = 123456789;
    for (int x : where) answer = Math.min( answer, x );
    if (answer == 123456789) answer = -1;
    return answer;
}

It should also be possible to solve this task greedily, but I expect such solutions to be more complicated and error-prone. With the dynamic programming it’s clear that we are not missing any cases, because we tried all possibilities.

FixedPointReversals

Without the fixed point, we can sort any array of length N in at most N-1 reversals. This is easy: always pick the largest element that is not in its place, and reverse the part between its current and desired location, inclusive.

A clear necessary condition for a solution to exist is that the sorted array and the input array must have the same value at the fixed index. This is easy to check, and as we show below, this necessary condition is also sufficient — if it holds, the solution does exist.

The condition about not changing the value at the fixed point is a bit of a red herring. Our solution has to work for inputs in which all values are distinct, and for those inputs not changing the value is the same as not moving the element at all. So we may simply look for a solution that does not move the fixed element at all. I.e., all reversals either happen on one side of the fixed element, or they have the fixed element in the middle.

Let L and R be the number of elements to the left and to the right of the fixed point. We’ll show that we can always sort the array in at most 2*min(L,R) + max(L,R) – 1 <= 72 reversals.

WLOG, let’s assume L >= R. We will first put the elements in the right part onto their correct places (using at most two reversals per element) and then we’ll sort the left part. We already know how to do the latter in at most L-1 reversals, so we just need to do the former.

We’ll process the right part from the largest element to the smallest. If the current element is already where it belongs, we do nothing. If it’s already in the right part, we can get it to its proper place in one reversal. And if it’s in the left part, we can do so in two reversals: The first reversal will be inside the left part, to get it to the place that is the mirror image of the place where it belongs (*), and the second is a reversal centered at the fixed point.

(*) Here we are using the fact that L >= R, so that position always exists.

Here’s an example of getting the number 47 where it belongs in two reversals. The last three values are already in place, and parentheses denote the fixed point. Note that the second reversal doesn’t mess up the part that is already sorted.

aa  bb  47  cc  dd  ee  ff  gg  hh (ii) jj  kk  ll  48  49  50
        ------------------
aa  bb  ff  ee  dd  cc  47  gg  hh (ii) jj  kk  ll  48  49  50
                        --------------------------
aa  bb  ff  ee  dd  cc  ll  kk  jj (ii) hh  gg  47  48  49  50

NiceMultiples

If U/M is small (up to, say, 5,000,000), we can check each of the U/M multiples of M that are small enough separately. As U <= 10^12, the above covers all cases with M > 200,000.

As now we are left only with inputs in which M is reasonably small, we can solve those using dynamic programming. Suppose that in base B the number U has D digits. We now want to count all strings of exactly D digits that:

• represent numbers at most equal to U
• only contain zeros at the beginning
• are divisible by M

One reasonably easy implementation is to imagine that we construct the number from the left to the right. For each prefix, we will ask the question: “How many valid solutions begin with this prefix?”

For a fixed prefix, there are three possibilities:

• We know that the number will be too big: Return 0.
• The current prefix is a prefix of U: Recursively try all possibilities for the next digit and sum the answers. (This only happens a few times during the entire solution, so it doesn’t impact the time complexity.)
• We know that the number will be too small: The answer to our question depends only on three things — the number of digits left, the remainder the prefix gives modulo M, and a boolean flag whether the current prefix is still zero or not (if not, we cannot use zeros any more). Do the same as in the previous case, but memoize the answer.

With memoization, this gives us a solution with 2*M*log_B(U) states and at most B transitions from each state, and that is fast enough to solve the remaining cases.

SteelMill

There is an obvious dynamic programming solution that is too slow: For each amount of steel we store the cheapest way to get it, we process the mines one at a time, and for each mine and each state we try all possible ways of mining.

The above solution can be sped up using some heavy-duty data structures, but there is also a clever observation we can make that will make the implementation really simple and painless.

The problem looks like greedy should work somehow — converting ore cheaply should be better than converting other ore more expensively, right? That’s not entirely true because of the shipping costs, but we can combine the greedy strategy with the above DP. The key observation is described below.

Suppose we ignore the shipment cost for now, and we order the mines according to cost per producing 1 kg of steel, in descending order. We will now process the mines in this order, one at a time.

Imagine that we already processed some mines, and that for each integer amount of steel we know the cheapest way of producing it using ore from those mines. Now we are adding one additional mine. We already know what happens if we don’t buy the shipment from this mine, so we just need to examine what happens if we do buy it. If we already paid for the shipment, we now have a bunch of ore from this mine, and among all mines we currently have, this ore is the cheapest to process. Hence, in the optimal solution we want to process as much of it as possible.

Thus, instead of trying all possible amounts, we just try one: min( the amount available, the total we are currently trying to produce ).

With this improvement we now have a solution that runs in O(number of mines * desired amount of steel), and that is fast enough.

    // below we assume that costPerKg is sorted in >= order
    long[] dp = new long[goal+1];
    for (int i=1; i<=goal; ++i) dp[i] = 1L << 62;
    for (int m=0; m<shipmentCost.length; ++m) {
        for (int i=goal; i>=1; --i) {
            int take = Math.min( i, shipmentSize[m] );
            long pay = shipmentCost[m] + 1L * take * costPerKg[m];
            dp[i] = Math.min( dp[i], dp[i-take] + pay );
        }
    }
    return dp[goal];