November 8, 2021 Single Round match 818 Editorials

In this round, division 2 got a set of array-based problems, while division 1 got an easier-than-average set of problems from different areas.

GlobalWarmingCheck

As the length of the segments is constant, the segment with the smallest / largest average is also the segment with the smallest / largest sum. (The average of a segment is always its sum divided by the constant Y.) This observation allows us to avoid using floating-point numbers.

We can simply iterate over all segments and check the sum of each of them. In order to do this efficiently, we need to avoid recomputing the sum of each segment from scratch. Instead, when we move from the segment T[a]..T[a+Y-1] to the segment T[a+1]..T[a+Y], we take the old sum, subtract the element T[a] that is no longer in the segment, and add the new element T[a+Y].

Another way of solving this task in O(N) time is to use precomputed prefix sums. These are values P[0]..P[N], where P[i] is the sum of the first i elements in T. The code below shows how to precompute them in linear time: the sum of the first i elements is the sum of the first i-1 elements, plus the next element.

Once we have the array P, we can compute the sum of any segment of T in constant time: the sum of T[a]..T[b-1] is simply P[b] – P[a].

public int[] solve(int N, int M, int Y) {
    int[] T = new int[N];
    for (int n=0; n<N; ++n) T[n] = (int)( (1L*n*n + 4*n + 7) % M );

    int[] P = new int[N+1];
    P[0] = 0;
    for (int n=0; n<N; ++n) P[n+1] = P[n] + T[n];

    int lo = -1, hi = -1;
    int minSum = 1_000_000_007, maxSum = -1;
    for (int z=0; z+Y<=N; ++z) {
        int currSum = P[z+Y] - P[z];
        if (currSum < minSum) { minSum = currSum; lo = z; }
        if (currSum >= maxSum) { maxSum = currSum; hi = z; }
    }
    return new int[] {lo, hi};
}

EqualPiles

We have a collection of N values. We can decrease at most T of them. Our goal is to produce as many equal values as possible.

Lemma: There is always an optimal solution in which the most frequent value in the end is one of the values that appeared in the original collection.

Proof: Take any optimal solution. Let V be the most frequent value in the end. Look at all the original numbers that become Vs in the end. Let W be the smallest original value among these numbers. Clearly, V <= W because we cannot increase numbers. And also clearly, if V < W, instead of changing all those numbers to Vs we could change all of them into Ws (which saves some steps and does not require any new ones).

Let W be a value that appears in the original collection. How many Ws can we have in the end?

Let E(W) be the count of numbers in our collection with value exactly W, and let G(W) be the count of numbers with values greater than W. The best we can do is to leave all E(W) of those that are already Ws untouched, and to decrease as many bigger ones as we can to W. Remember that we have a limited amount of time: if there are too many bigger values, we can only process T of them. Thus, the maximum number of Ws we can get in the end is E(W) + min(T, G(W)).

Given these observations, we can now solve this task in O(N log N) time. We will start by sorting our collection. Then we can process all numbers from the largest to the smallest, keeping track of E(W) and G(W) for the value W we are currently processing. This way we process all possible values of W and we pick the best of all solutions found.

public int equalize(int N, int M, int T) {
    int[] candy = new int[N];
    for (int n=0; n<N; ++n) {
        long tmp = n; tmp *= n; tmp %= M; ++tmp;
        candy[n] = (int)tmp;
    }

    Arrays.sort(candy);

    int greater = 0, equal = 0, answer = 0;
    for (int n=N-1; n>=0; --n) {
        if (n==N-1 || candy[n]<candy[n+1]) {
            greater+=equal; equal=1;
        } else {
            ++equal;
        }
        int current = equal + Math.min( T, greater );
        answer = Math.max( answer, current );
    }
    return answer;
}

MedianSegments

We have an array A such that the value A[K] is unique. We want to count all contiguous segments of A such that their length is odd and A[K] is their median.

Each other element of A is either greater than A[K] or smaller than A[K]. A segment is good if and only if it contains A[K], and along with it contains the same number of greater and smaller elements.

Suppose we replace each greater element with a +1, each smaller element with a -1, and the element A[K] itself with a 0. Then clearly we want precisely the segments that have sum zero and an odd length. 

From this point there are multiple ways how to proceed. One possibility is that we can do the prefix sums of the new array, and then iterate over them. For each value, we then ask the question how many times we have previously seen this value at an index of the same parity as ours.

Another possibility, implemented below, is to go outwards from K in both directions. We want to take some elements on the left of index K and some on the right. If we take more big elements on the left, we must compensate by taking more small elements on the right to balance it out.

This is easy to rephrase in terms of sums of those segments. For example, if we take a segment with sum -3 on the left of K, it means that we now have three extra small elements. Thus, we must take a segment with sum 3 on the right of K to add three extra big elements.

In order to count all options efficiently, we can precompute, for each sum x, L[x] = how many possible segments going left have that sum, and R[x] = how many possible segments going right have that sum. Then the answer we seek is the sum of L[x] * R[-x], over all x.

int[] generateA(int N, int[] Aprefix, int M) {
    int[] A = new int[N];
    int L = Aprefix.length;
    for (int i=0; i<L; ++i) A[i] = Aprefix[i];
    long state = Aprefix[L-1];
    for (int i=L; i<N; ++i) {
        state = (state * 1103515245 + 12345) % (1L << 31);
        A[i] = (int)(state % M);
    }
    return A;
}

public long count(int N, int K, int[] Aprefix, int M) {
    int[] A = generateA(N, Aprefix, M);

    long[] countLeft = new long[2*N+1];
    long[] countRight = new long[2*N+1];
    int curr = N;
    ++countLeft[curr];
    for (int l=K-1; l>=0; --l) {
        if (A[l] < A[K]) --curr; else ++curr;
        ++countLeft[curr];
    }
    curr = N;
    ++countRight[curr];
    for (int r=K+1; r<N; ++r) {
        if (A[r] > A[K]) --curr; else ++curr;
        ++countRight[curr];
    }
    long answer = 0;
    for (int n=0; n<=2*N; ++n) answer += countLeft[n] * countRight[n];
    return answer;
}

PStepsGame

This is an easy dynamic programming problem, and the only reason why it’s in a medium slot is the extra need to be a bit careful in terms of time complexity: O(NP^2) solutions will time out, we need to make our solution run in O(NP) time.

The O(NP^2) solution is essentially a simple simulation, one person at a time. After each person we are in one of O(P) possible states, where the state is simply the number of pairs of bottles in which we already know which one has water. For each of those states, we take the next person and iterate over all possibilities what happens during their game.

This way, we can determine the probability of reaching each state and thus also the probability of winning the game for each player. By linearity of expectation the answer we seek is then simply the sum of the probabilities of individual players surviving.

Somewhat surprisingly, we can improve the time complexity by introducing more states: not just after a player finished playing, but also during their game. The new state will be the pair (the player currently playing, the number of revealed pairs of bottles). For each of these O(NP) states we then only have to examine two options: what happens the next time the current player drinks from an unknown bottle.

In the code below we implement this DP as follows: in the array probs[] we have the probabilities of ending in each of the O(P) original states after the last processed player. We then iterate over all new states for the next player, starting with the one with no known bottles. For each such state there are two ways in which it can be reached: either by the current player from the state with one fewer known bottles (by drinking and being lucky), or by starting here after the previous player’s game was over. Each time we move to the next state, we know the total probability of reaching it by drinking, and we add the probability of reaching it by starting there to get the aggregate probability of being in that particular state.

public double solve(int N, int P) {
    double[] probs = new double[P+1];
    probs[0] = 1.;
    double answer = 0;
    for (int n=0; n<N; ++n) {
        double[] new_probs = new double[P+1];
        new_probs[P] = probs[P];
        answer += probs[P];
        double carrying = probs[0];
        for (int p=1; p<=P; ++p) {
            carrying /= 2;
            new_probs[p] += carrying;
            if (p < P) carrying += probs[p];
        }
        answer += carrying;
        new_probs[P] += carrying;
        probs = new_probs;
    }
    return answer;
}

SixCandyBags

As we can generate all triples of bags within the time limit, this is essentially a meet-in-the-middle problem. We just need to make sure not to take the same bag twice. One way to do this is as follows:

• Use brute force to iterate over all sets of 1, 2, and 3 indices into the sequence of bags.
• Iterate over all possibilities for the fourth smallest index. While you do so, keep a data structure that describes what you can get from exactly three indices, all of them smaller than the one we are currently processing. For each fourth index:
  • Take just this bag, then iterate over all possibilities for the fifth index, then iterate over all possibilities for the fifth+sixth index. This gives you all possibilities for the “second half” of a solution.
  • For each of these “second halves” you know the exact number of candies you are missing and the maximum amount of cash you can spend on those missing candies. Use the data structure to look up the best match among what you can get from the first three indices.
  • Update the data structure by adding all triples of indices in which the largest one is the index we just finished processing.

The data structure we need is an ordered set of pairs (exact number of candies in a triple of bags, exact cost of those three bags). The pairs are sorted lexicographically – first by # of candies, then by price. In that set we can then in logarithmic time look up the largest pair that does not exceed (candies we need, money we have left) and check whether we got the desired number of candies (yay!) or some smaller number (boo!).

The total time complexity of this approach is O(N^3 * log N).

The sample implementation shown below could have been nicer. One way to make it nicer (and shorter) is to add five empty bags and then look just for solutions with exactly six bags.

long improve(int limit, long oldval, long candidate) {
    if (candidate > limit) return oldval;
    return Math.max( oldval, candidate );
}

long finish(long oldval, long wantPieces, long haveMoney, long gotPieces, long spentMoney, TreeSet<Long> options) {
    long wantRest = wantPieces - gotPieces;
    long priceRest = haveMoney - spentMoney;
    if (wantRest < 0) return oldval;
    if (priceRest < 0) return oldval;
    long ideal = (wantRest << 30) | priceRest;
    Long found = options.floor(ideal);
    if (found == null) return oldval;
    long foundval = found;
    long foundrest = foundval >> 30;
    if (foundrest != wantRest) return oldval;
    long foundprice = foundval & ((1L << 30) - 1);
    return Math.max( oldval, spentMoney + foundprice );
}

public int buy(int[] candies, int[] price, int wantPieces, int haveMoney) {
    int N = candies.length;
    long best = -1;

    // check options with 1-3 purchases
    for (int a=0; a<N; ++a) if (0L + candies[a] == wantPieces) best = improve(haveMoney, best, 0L + price[a]);
    for (int a=0; a<N; ++a) for (int b=0; b<a; ++b) if (0L + candies[a] + candies[b] == wantPieces) best = improve(haveMoney, best, 0L + price[a] + price[b]);
    for (int a=0; a<N; ++a) for (int b=0; b<a; ++b) for (int c=0; c<b; ++c) if (0L + candies[a] + candies[b] + candies[c] == wantPieces) best = improve(haveMoney, best, 0L + price[a] + price[b] + price[c]);

    // check options with 4-6 purchases by iterating through the fourth
    TreeSet<Long> options = new TreeSet<Long>();
    for (int d=0; d<N; ++d) {
        // process all options in which d is the fourth purchase
        best = finish(best, wantPieces, haveMoney, 0L + candies[d], 0L + price[d], options);
        for (int e=d+1; e<N; ++e) best = finish(best, wantPieces, haveMoney, 0L + candies[d] + candies[e], 0L + price[d] + price[e], options);
        for (int e=d+1; e<N; ++e) for (int f=e+1; f<N; ++f) best = finish(best, wantPieces, haveMoney, 0L + candies[d] + candies[e] + candies[f], 0L + price[d] + price[e] + price[f], options);

        // then, add new triples to the options for first three purchases
        for (int a=0; a<d; ++a) for (int b=a+1; b<d; ++b) {
            long pieces = 0L + candies[a] + candies[b] + candies[d];
            long cents = 0L + price[a] + price[b] + price[d];
            if (pieces > wantPieces || cents > haveMoney) continue;
            options.add( (pieces << 30) | cents );
        }
    }
    return (int)best;
}