March 31, 2022 Single Round Match 826 Editorials

GetGas

The solution is mostly casework. For each possible gas station:

1. Check whether you have enough gas to reach it. If not, skip it completely.
2. Calculate the amount of gas you’ll need for the whole trip if you stop at this gas station.
3. If you don’t have enough gas for the whole trip, purchase what you need and remember the cost.

Then, just pick the smallest out of the costs you remembered.

public double optimize(int G, int[] Dto, int[] Dfrom, int[] gasPrice) {
    double best = 1e30;
    int N = Dto.length;
    for (int n=0; n<N; ++n) {
        if (25*G < Dto[n]) continue;
        double totalDistance = Dto[n] + Dfrom[n];
        double gallonsNeeded = totalDistance / 25;
        if (G >= gallonsNeeded) {
            best = 0;
            continue;
        }
        gallonsNeeded -= G;
        best = Math.min( best, gallonsNeeded * gasPrice[n] );
    }
    return best;
}

VisitPoints

As all coordinates of targets are small, we should be able to get from any target to any other reasonably quickly. (If there were no obstacles, we could simply go first up/down and then left/right as necessary and this would always take at most 50 steps. In the worst case, every second step this path will hit an obstacle. If we do the dumbest possible thing and just go around each obstacle and return back to the desired path, we will have two extra steps per obstacle. Thus, there is always some valid path with at most 100 steps.)

This means that the 5000 move limit is very generous. We don’t need to optimize anything, we can just visit the given targets in any order we like. We just need to make sure to avoid targets other than target x when we are on our way to target x.

One possible implementation of a solution is to use some graph traversal algorithm, for example, breadth-first search (BFS). We can always look for the shortest path from the current target to the next one, while treating the others as obstacles. This will guarantee us to find a path that’s valid and short enough.

There is also an approach that’s easier to implement: we can just greedily move towards the target. One particular strategy that works is to always make a valid move that brings you closest to your current target (in terms of Euclidean distance).

Why does this strategy work? Without loss of generality imagine that you are at (0, 0) and that your target is at (r, c).

• If both r and c are positive (you are neither in the right row nor in the right column) you have two moves that bring you closer: you can go to (0, 1) or to (1, 0). At most one of these can have an obstacle, so you can get closer to your goal.
• If r > 0 and c = 0 (or vice versa), you just want to go directly towards the goal: in this case, to (1, 0). If that move is available, you do it.
• If that move hits an obstacle, the next best move is to take a step to the side. (This step will always be available.) Then, the next move is always a move of the first type and you will move to the cell next to the obstacle (not back to the same cell you just came from) because that cell is available and closer to your goal. So, you just went around the obstacle.

int ID(int[] X, int[] Y, int x, int y) {
    for (int n=0; n<X.length; ++n) if (X[n] == x && Y[n] == y) return n;
    return -1;
}

int sqDist(int x1, int y1, int x2, int y2) {
    return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}

public String visit(int[] X, int[] Y) {
    char[] dl = { 'N', 'S', 'E', 'W' };
    int[] dx = { 0, 0, 1, -1 };
    int[] dy = { 1, -1, 0, 0 };

    int N = X.length;
    int x = 0, y = 0;
    String answer = "";
    for (int n=0; n<N; ++n) {
        while (x != X[n] || y != Y[n]) {
            int bx = -1, by = -1;
            char bl = '?';
            for (int d=0; d<4; ++d) {
                int nx = x + dx[d], ny = y + dy[d];
                int id = ID(X,Y,nx,ny);
                if (id != -1 && id != n) continue;
                if (bl == '?') { bx=nx; by=ny; bl=dl[d]; continue; }
                if (sqDist(X[n],Y[n],nx,ny) < sqDist(X[n],Y[n],bx,by)) {
                    bx=nx; by=ny; bl=dl[d];
                }
            }
            answer += bl;
            x = bx; y = by;
        }
    }
    return answer;
}

TwoFairDice

When comparing two dice we do not care about the actual values on the faces, only their relative sizes. For example, if Alice’s die is {10, 20, 30, 40, 50, 60}, putting the number 23 on Bob’s die has exactly the same effect as putting 29 on it: if rolled, it will beat 10 and 20, but it will lose to the other four options.

Thus, in general we have at most 13 distinct choices for each face of Bob’s die: we can use one of the (at most) six values Alice used, or we can use a value from the (at most) seven (possibly empty) ranges between them. This gives us at most 13^6 options for the whole die, and that number is still small enough. Thus, we can iterate over all these options one by one, for each of them evaluate whether the current pair of dice is fair, and if it is, calculate the number of different dice of this type.

In the implementation we explicitly pick one value from each of the available ranges. For the example Alice’s die above we could pick the values {0, 10, 11, 20, 21, 30, 31, 40, 41, 50, 51, 60, 61} as the 13 values we try. For each value we remember its weight. E.g., 0 has weight 10 (because the 0 represents the entire range [0,9] which contains 10 options) while 10 has weight 1 (because this must be exactly the number 10). Once we construct one good die for Bob, the total number of “similar” dice can then be computed simply by multiplying the weights of the numbers we used.

boolean areDiceEqual(int[] A, int[] B) {
    int aliceWins = 0, bobWins = 0;
    for (int a : A) for (int b : B) {
        if (a > b) ++aliceWins;
        if (b > a) ++bobWins;
    }
    return aliceWins == bobWins;
}

int[] options;
long[] weights;
int[] Bcompleted;
int[] Acopy;

long go(int idx, long waysSoFar) {
    if (idx == 6) {
        if (areDiceEqual(Acopy, Bcompleted)) return waysSoFar;
        return 0;
    }
    long answer = 0;
    for (int i=0; i<options.length; ++i) {
        Bcompleted[idx] = options[i];
        answer += go(idx+1, waysSoFar*weights[i]);
    }
    return answer;
}

public long finish(int[] A, int[] B) {
    Set<Integer> values = new TreeSet<Integer>();
    for (int a : A) values.add(a);
    int[] sorted = new int[values.size()];
    { int i = 0; for (int x : values) sorted[i++] = x; }

    int optionCount = sorted.length;
    if (sorted[0] > 0) ++optionCount;
    if (sorted[sorted.length-1] < 1000) ++optionCount;
    for (int i=0; i+1<sorted.length; ++i)
        if (sorted[i]+1 < sorted[i+1]) ++optionCount;

    options = new int[optionCount];
    weights = new long[optionCount];

    {
        int j = 0;
        for (int i=0; i<sorted.length; ++i) {
            options[j] = sorted[i];
            weights[j] = 1;
            ++j;
        }
        if (sorted[0] > 0) {
            options[j] = 0;
            weights[j] = sorted[0];
            ++j;
        }
        if (sorted[sorted.length-1] < 1000) {
            options[j] = 1000;
            weights[j] = 1000 - sorted[sorted.length-1];
            ++j;
        }
        for (int i=0; i+1<sorted.length; ++i) if (sorted[i]+1 < sorted[i+1]) {
            options[j] = sorted[i] + 1;
            weights[j] = sorted[i+1] - sorted[i] - 1;
            ++j;
        }
    }

    Acopy = new int[6];
    for (int i=0; i<6; ++i) Acopy[i] = A[i];
    Bcompleted = new int[6];
    for (int i=0; i<B.length; ++i) Bcompleted[i] = B[i];

    return go(B.length, 1);
}

Alternate solutions are possible by using dynamic programming instead of brute force. These solutions can actually be shorter to implement, as we don’t have to do the logic for empty intervals and we can just iterate over all options what to put on the next face. (The state after filling some faces of Bob’s die can be represented by a single additional value X: the number of ways in which Bob can already win against Alice, minus the number of ways in which Alice can win against Bob. Note that this value may be negative; its absolute value is always very small.)

TwoCatsAndAMouse

This task has two solution types. One solution uses that the input is small, requires less thinking if you know the general approach, but requires writing more code. The other solution solves the problem in general and requires writing less code.

The first solution is very similar to what’s internally implemented as checker that validates the output of your solution. We can start by noticing that we can already resolve some situations: if either cat is adjacent to the mouse, we can catch it and win in one turn. Now we can repeatedly iterate over all other states of the game. For each state S we can reason as follows: We can look at all 25 possible ways the cats can move in their first turn. For each such way: the mouse now has 5 possible moves. If all moves of the mouse lead to situations that are already known to be winning for us, state S must also be winning and the cat moves we are currently considering are a winning move. (If the mouse wants us to win as slowly as possible, it will pick the option that requires most turns to win, so the number of turns to win from S if this move is picked is 1 + maximum of these numbers for the five new states.)

Eventually, this process terminates in one of two possible ways: either we find winning moves for all possible states (and if we are a bit more careful, we can actually compute the optimal strategy for each of them), or we eventually reach the situation where we traversed through all unsolved states without learning anything new. If the latter happens, it means that for those states the mouse has a strategy that always keeps us in those states – hence, we have no way to win.

The second solution will show that the latter case cannot occur: the two cats can always catch the mouse. Here’s a simple strategy: cat 1 wants to be in the same row as the mouse while cat 2 wants to be in the same column. Whenever they aren’t, they move one row/column closer, whenever they are, they move within the current row/column towards the mouse.

Remembering that R >= C, we can argue as follows. First, after at most R-1 turns we will have cat 1 in the same row as the mouse and cat 2 in the same column. Second, once that configuration occurs, after at most R+C-3 turns a cat will catch the mouse. (Imagine that each cat is looking at the mouse, and imagine that the cats will remain facing these directions for the rest of the solution. Regardless of how the mouse moves, one cat always takes a step towards the wall it’s facing while the other takes a side-step to again be in the same row/column as the mouse. After R+C-3 steps at least one of the cats must have already reached the wall it is facing, and at the very least at that moment it must have caught the mouse.

int[] DR, DC;

char doMove(int R, int C, int r1, int c1, int r2, int c2, int r3, int c3) {
    // catch the mouse (with one cat) if you can
    for (int m=0; m<5; ++m) {
        int nr1 = r1 + DR[m], nc1 = c1 + DC[m];
        if (nr1 < 0 || nr1 >= R || nc1 < 0 || nc1 >= C) continue;
        if (nr1 == r3 && nc1 == c3) return (char)('A' + 5*m + 0);
    }
    for (int m=0; m<5; ++m) {
        int nr2 = r2 + DR[m], nc2 = c2 + DC[m];
        if (nr2 < 0 || nr2 >= R || nc2 < 0 || nc2 >= C) continue;
        if (nr2 == r3 && nc2 == c3) return (char)('A' + 5*0 + m);
    }

    int m1 = -1, m2 = -1;
    // cat 1 moves to the correct row and then to the mouse
    if (r1 != r3) {
        if (r1 < r3) m1 = 2; else m1 = 1;
    } else {
        if (c1 < c3) m1 = 4; else m1 = 3;
    }
    // cat 2 moves to the correct column and then to the mouse
    if (c2 != c3) {
        if (c2 < c3) m2 = 4; else m2 = 3;
    } else {
        if (r2 < r3) m2 = 2; else m2 = 1;
    }
    
    return (char)('A' + 5*m1 + m2);
}

public String catchMouse(int R, int C) {
    
    DR = new int[] { 0, -1, 1, 0, 0 };
    DC = new int[] { 0, 0, 0, -1, 1 };
    
    String answer = "";
    for (int r1=0; r1<R; ++r1) for (int c1=0; c1<C; ++c1) 
    for (int r2=0; r2<R; ++r2) for (int c2=0; c2<C; ++c2) 
    for (int r3=0; r3<R; ++r3) for (int c3=0; c3<C; ++c3) {
        if (r1 == r3 && c1 == c3) continue;
        if (r2 == r3 && c2 == c3) continue;
        answer += doMove(R, C, r1, c1, r2, c2, r3, c3);
    }
    return answer;
}

SpaceMission

We are going to do some casework and some combinatorics.

First we can make some simplifications to the problem, as follows:

• Clearly, minn[i] and maxn[i] can have the same parity as parity[i]: we can increment the minimum and decrement the maximum if they aren’t.
• If this created an empty range, there is no solution.
• We can send one person from each country that wants an odd number of people. This decreases the corresponding minn[] and maxn[] but also mint and maxt by 1.
• If now maxt is negative, there is no solution. If mint is negative, we set it to zero.
• Now we have the state where every country wants to have an even number of people. If mint or maxt are odd, we increment mint and/or decrement maxt to make them even.
• Again, if this creates an empty range of valid totals, there is no solution.
• At this point everything is even, so we can treat couples of people as units and divide everything by 2.
• Now we can send the required minimum of people from each country to the station and update mint and maxt accordingly.
• Yet again, if maxt is negative there is no solution and if mint is negative we can set it to zero.
• Finally, we have a much simpler task.

The simpler task is as follows: given some countries and the maximum value maxn[i] for each of them, how many ways are there to select a crew with total size in [mint,maxt]?

And there is one more (very standard) simplification we can make: instead of the above, we will count all crews with size in [0, maxt] and we’ll subtract all crews with size in [0, mint-1].

How to do the counting? We will use the inclusion-exclusion principle: count all ways of selecting at most maxt crewpeople with no restrictions on country numbers, then subtract those where we used too many people from some one country, then add back those where we had too many people from some two countries (as we just subtracted these twice), and so on.

What is the number of ways to select at most X people from N different countries? This is the binomial coefficient choose(X+N,N). Proof: we are counting all possible sequences of X actions “take a person” and N actions “move to the next country”. (People selected from “country N+1” do not count, this way we make sure to count all ways of selecting at most X and not just exactly X people.)

What changes if we have a subset of countries such that we took too many people from them? For each such country, we will start by explicitly taking maxn[country]+1 people. If we took a total of S people this way, we are left with choosing the remaining X-S people from N countries arbitrarily. This is still the same story: choose(X-S+N,N) ways. Note that if S>X, the binomial coefficient is zero: this happens in impossible situations.

All that remains is evaluating binomial coefficients choose(something large, something very small) quickly in modular arithmetics. One simple way to do this is to represent the value choose(Y,N) as the fraction with numerator Y(Y-1)…(Y-N+1) and denominator N!. We can keep the terms of the numerator separately, and then for each term in the denominator we go over all terms in the numerator and divide them as we can. (More precisely, we always compute gcd of the current term in the numerator and of what we still have left from the current term in the denominator.) Once the process is done, we simply multiply the numbers that remained in the numerator, modulo the given value.

int gcd(int x, int y) {
    while (y > 0) { int t = x%y; x = y; y = t; }
    return x;
}

int binomial(int n, int k, int modulus) {
    if (n < k) return 0;
    if (k == 0) return 1;
    int[] numerator = new int[k];
    for (int i=0; i<k; ++i) numerator[i] = n-i;
    for (int den=1; den<=k; ++den) {
        int curr = den;
        for (int i=0; i<k; ++i) {
            int d = gcd( numerator[i], curr );
            numerator[i] /= d;
            curr /= d;
        }
    }
    long answer = 1;
    for (int x : numerator) {
        answer *= x;
        answer %= modulus;
    }
    return (int)answer;
}

int countCouples(int[] maxn, int maxt, int modulus) {
    int N = maxn.length;
    int total = 0;
    for (int subset=0; subset<(1<<N); ++subset) {
        int popcnt = 0;
        for (int n=0; n<N; ++n) if ((subset & 1<<n) != 0) ++popcnt;
        int sign = (popcnt % 2 == 0 ? 1 : -1);
        int hore = maxt + N;
        for (int n=0; n<N; ++n) if ((subset & 1<<n) != 0) hore -= maxn[n]+1;
        int b = binomial(hore, N, modulus);
        total += sign * b;
        if (total >= modulus) total -= modulus;
        if (total < 0) total += modulus;
    }
    return total;
}


public int count(int[] minn, int[] maxn, int[] parity, 
                 int mint, int maxt, int modulus) {

    // adjust bounds to match parity
    int N = minn.length;
    for (int n=0; n<N; ++n) {
        if (minn[n] % 2 != parity[n] % 2) ++minn[n];
        if (maxn[n] % 2 != parity[n] % 2) --maxn[n];
        if (minn[n] > maxn[n]) return 0;
    }

    // send one person from each odd country
    for (int n=0; n<N; ++n) {
        if (parity[n] == 1) {
            --minn[n];
            --maxn[n];
            --parity[n];
            --mint;
            --maxt;
        }
    }
    if (maxt < 0) return 0;
    if (mint < 0) mint = 0;

    // adjust totals to match that now all countries are even
    if (mint % 2 == 1) ++mint;
    if (maxt % 2 == 1) --maxt;
    if (maxt < mint) return 0;

    // at this point everything is even and we can count everything as couples
    for (int n=0; n<N; ++n) {
        minn[n] /= 2;
        maxn[n] /= 2;
    }
    mint /= 2; maxt /= 2;

    // at this point we can forcibly satisfy the required lower bounds
    for (int n=0; n<N; ++n) {
        maxn[n] -= minn[n];
        mint -= minn[n];
        maxt -= minn[n];
    }
    if (maxt < 0) return 0;
    if (mint < 0) mint = 0;

    // at this point we only have to deal with the upper bounds
    int result = countCouples(maxn, maxt, modulus);
    if (mint > 0) {
        result -= countCouples(maxn, mint-1, modulus);
        if (result < 0) result += modulus;
    }
    return result;
}