Single Round Match 758 Editorials

LongJump2

The implementation is fairly straightforward. The main thing we need to realize is that it is not sufficient to keep track of the longest jump so far, we also need to know who made that jump. This is because if the same contestant later improves the maximum, the leader will not change.

    public int countNewLeaders(int N, int[] jumpLengths) {
        int currentLeader = -1;
        int currentBest = -1;
        int answer = 0;
        int nextJump = 0;
        for (int round=1; round<=3; ++round) {
            for (int jumper=1; jumper<=N; ++jumper) {
                int currentJump = jumpLengths[nextJump++];
                if (currentJump > currentBest) {
                    currentBest = currentJump;
                    if (currentLeader != jumper) {
                        currentLeader = jumper;
                        ++answer;
                    }
                }
            }
        }
        return answer;
    }

WildSequence

There are multiple patterns that work and are easy to implement, but a little bit of care was needed: e.g., many implementations will fail the cases when head is either the smallest or the largest of all elements.

Here’s one possible technique. First, imagine that head is smaller than anything in rest. One really easy solution is to alternately take the largest and the smallest element of rest to guarantee that the sequence goes up and down alternately. If head isn’t the smallest of all values, we can start by taking the smallest element of rest first (as that one is definitely smaller than head) and then fall back to the above strategy.

    public int[] construct(int head, int[] rest) {
        Arrays.sort(rest);
        boolean nextSmallest = true;
        if (rest.length > 0 &amp;&amp; head < rest[0]) nextSmallest = false;
        int lo = 0, hi = rest.length;

        int[] answer = new int[1+rest.length];
        answer[0] = head;
        for (int i=0; i<rest.length; ++i) {
            if (nextSmallest) answer[i+1] = rest[lo++];
            else answer[i+1] = rest[--hi];
            nextSmallest = !nextSmallest;
        }
        return answer;
    }

A slightly different valid strategy is to simply split the array [head]+rest in the middle into “small” and “large” elements, and then alternately take any small element and any large element. (The two technical details are that you need to take head first, and if the total number of elements is odd, you need to break the tie so that the half that contains the head is the one with more elements than the other one.)

SelfDescFind

This problem required you to make three simple observations.

The first one is the following one: if you are given D digits, the number you are constructing will have exactly 2D digits. The digits you are given are the b[i] of the number, and you have to find the corresponding a[i]. As the corresponding a[i] must describe the whole number, we now know that the sum of all a[i] must be exactly 2D.

The second observation: Each valid sequence of a[i] is some integer partition of 2D into exactly D ordered positive parts. For D=20, there are only (19 choose 9) = 92,378 such partitions (and some of them are invalid because they have some a[i] exceed 9). This means that we can simply try all of them. If we fix one sequence a[i], we know the exact multiset of digits we will have in our number, and we need to verify whether it works by counting the number of actual occurrences of each digit and comparing these counts to a[i].

The third observation is the easiest. Once we have some pairs (a[i],b[i]) that work, we can produce the smallest number that contains them simply by sorting the pairs lexicographically.

    ArrayList< ArrayList<Integer> > partitions(int sum, int length) {
        ArrayList< ArrayList<Integer> > answer 
            = new ArrayList< ArrayList<Integer> >();
        if (length == 1) {
            if (1 <= sum &amp;&amp; sum <= 9) {
                ArrayList<Integer> onlyOption = new ArrayList<Integer>();
                onlyOption.add(sum);
                answer.add(onlyOption);
            }
            return answer;
        }
        for (int last=1; last<=9 &amp;&amp; sum-last >= length-1; ++last) {
            ArrayList< ArrayList<Integer> > tmp = partitions(sum-last,length-1);
            for (ArrayList<Integer> one : tmp) {
                one.add(last);
                answer.add(one);
            }
        }
        return answer;
    }

    public String construct(int[] digits) {
        String answer = "";
        int D = digits.length;
        ArrayList< ArrayList<Integer> > options = partitions(2*D,D);
        for (ArrayList<Integer> one : options) {
            int[] actualCounts = new int[10];
            for (int d=0; d<D; ++d) ++actualCounts[ one.get(d) ];
            for (int d=0; d<D; ++d) ++actualCounts[ digits[d] ];

            int[] declaredCounts = new int[10];
            for (int d=0; d<D; ++d) declaredCounts[ digits[d] ] = one.get(d);

            if (!Arrays.equals(actualCounts, declaredCounts)) continue;

            int[] pieces = new int[D];
            for (int d=0; d<D; ++d) pieces[d] = 10*one.get(d) + digits[d];
            Arrays.sort(pieces);

            String curr = "";
            for (int x : pieces) curr += x;

            if (answer.equals("")) answer = curr;
            if (curr.compareTo(answer) < 0) answer = curr;
        }
        return answer;
    }

LollipopHoney

The condition from the problem statement can be restated as follows: pick 2K tastiest lollipops, given that you cannot pick more than K lollipops from any one flavor.

The optimal total deliciousness can be solved greedily. We simply sort all lollipops into batches according to their deliciousness, and then we process the batches in decreasing order of deliciousness and we always take all lollipops we can. Clearly, this way we only discard a lollipop if we are full (of more delicious ones) or if we already have K of its type.

The above algorithm can also be extended to count the number of ways in which the optimal selection of lollipops can be made. First, note that when processing the batches as described above, there are three states. First, there are some batches where we take everything (except for stopping at K for each flavor). Then, there may be one batch where we take something and end up with 2K lollipops. Finally, there are some batches we discard completely.

Handling batches of the first type is easy: all choices are unique, except for the one where we have choose(A,B) options which B of A available lollipops to keep if the limit “K per flavor” is stopping us.

For the special batch we will use dynamic programming. For each flavor we know the number of lollipops available, and we know the maximum number we are still allowed to take. We process the flavors one at a time, and for each flavor we try all possible numbers of lollipops. The values computed are the values ways[i] = in how many ways could I pick exactly i lollipops of the already processed flavors?

    def count(self, K, flavor, deliciousness):
        distinct_f = set(flavor)
        distinct_d = set(deliciousness)

        sorted_lollipops = { d:[] for d in distinct_d }
        for f, d in zip(flavor, deliciousness): sorted_lollipops[d].append(f)
        
        taken_from_flavor = { f:0 for f in distinct_f }
        taken_total = 0
        deliciousness_total = 0
        ways_total = 1

        for d in reversed(sorted(distinct_d)):
            will_take = []
            for f in distinct_f:
                has_f = sorted_lollipops[d].count(f)
                will_take += [f] * min(has_f, K - taken_from_flavor[f])
            if taken_total + len(will_take) <= 2*K:
                # take all you have, sample those that have too many
                taken_total += len(will_take)
                deliciousness_total += d * len(will_take)
                for f in distinct_f:
                    has_f = sorted_lollipops[d].count(f)
                    took_f = will_take.count(f)
                    ways_total *= binomial(has_f,took_f)
                    ways_total %= MOD
                    taken_from_flavor[f] += took_f
            else:
                # take a subset that is large enough for your needs
                items_remains = 2*K - taken_total
                taken_total = 2*K
                deliciousness_total += d * items_remains

                ways_dp = [ 0 for _ in range(items_remains+1) ]
                ways_dp[0] = 1
                for f in distinct_f:
                    has_f = sorted_lollipops[d].count(f)
                    max_f = min(has_f, K - taken_from_flavor[f])
                    new_ways_dp = [ 0 for _ in range(items_remains+1) ]
                    for i in range(items_remains+1):
                        for j in range(max_f+1):
                            if i+j <= items_remains:
                                new_ways_dp[i+j] += ways_dp[i]*binomial(has_f,j)
                    ways_dp = [ x%MOD for x in new_ways_dp ]
               
                ways_total = (ways_total * ways_dp[-1]) % MOD
                break

        if taken_total < 2*K:
            return []
        return (deliciousness_total, ways_total)


PrettyLiar

In this task the main trick we need to make the solution run in time is the ability to “undo” one part of the computation of a dynamic programming table instead of recomputing said table from scratch.

The general outline of how we will count all pairs of permutations for which Kaede wins will look as follows:

  • Try all possibilities for the last number L played by Kanade when she loses the game.
  • Try all possibilities for the number F of full rounds played before the round in which Kanade lost.
  • Try all possibilities for the number of stones K removed by Kanade in the first F rounds.
  • In each of the situations described above, compute the answer as follows:
    • Take the number of ways in which Kanade can remove exactly K stones in exactly F rounds, without using the one move we chose for round F
    • Take the total number of ways in which Kaede can achieve a valid score such that Kaede’s score + K < S but Kaede’s score + K + L >= S. (This is always some contiguous range of scores.)
    • Multiply those two counts.

We will treat each of the girls roughly the same, but with some differences.

For Kaede:

  • We will use dynamic programming to compute the number of subsets of her sequence with each possible sum and each possible size.
  • Once we have those, we will compute the prefix sums of those values in the direction of increasing scores.
  • Once we have the prefix sums, we can answer the queries we need for the above solution in constant time. (Note that as we counted subsets, we then need to multiply that count by an appropriate pair of factorials to get the numbers of all permutations in which there is first the subset we want in any order, and then the remaining elements also in any order.)

For Kanade:

  • We will use the same dynamic programming as for Kaede.
  • Each time we choose a specific index in her sequence to get the value L she will play in the round in which she loses, we can now compute the new values for the dynamic programming. Doing this quickly is the crucial step of this solution.

Suppose we have the values kanade_subsets[size][sum] that tell us the number of subsets of Kanade’s sequence with a given size and sum. We now want to compute the values kanade_subsets_fixed that count the same if we cannot use element L. Doing this from scratch requires N^2 * maximum sum time, but we need to do it in N*maximum sum time instead.

The observation we need is that we can indeed “undo” any one step of the computation of the dynamic programming. The values computed in kanade_subsets do not depend on the order in which we processed the elements, so we can imagine that L was the last value processed. How do we undo its processing and recompute the values that were in kanade_subsets previously?

The values in kanade_subsets[0] are obviously correct. When computing the values in kanade_subsets[1] we always took some value from kanade_subsets[0] and we added L to contribute to a value in kanade_subsets[1]. We can now undo these steps and thus get the correct values in kanade_subsets_fixed[1]. Using those we can now fix kanade_subsets[2] to kanade_subsets_fixed[2], and so on.

The whole solution therefore runs in O(N^2 * maximum sum).

    int count(int S, vector<int> kaede, vector<int> kanade) {
        int N = kanade.size();

        // precompute factorials and their products we'll use
        vector<long long> factorial(101,1);
        for (int n=1; n<=100; ++n) factorial[n] = (factorial[n-1] * n) % MOD;
        vector<long long> coefficients(N);
        for (int n=0; n<N; ++n) {
            long long curr1 = (factorial[n+1] * factorial[n]) % MOD;
            long long curr2 = (factorial[N-n-1] * factorial[N-n-1]) % MOD;
            coefficients[n] = (curr1 * curr2) % MOD;
        }

        // for each number of items and each sum, 
        // precompute the number of matching subsets of kaede/kanade
        vector< vector<int> > kaede_subsets(N+1, vector<int>(100*N+1,0));
        vector< vector<int> > kanade_subsets(N+1, vector<int>(100*N+1,0));
        kaede_subsets[0][0] = 1;
        kanade_subsets[0][0] = 1;
        for (int n=0; n<N; ++n) {
            // add thing number n for kaede/kanade
            for (int sz=N-1; sz>=0; --sz) {
                for (int i=0; i<=100*n; ++i) {
                    kaede_subsets[sz+1][i+kaede[n]] += kaede_subsets[sz][i];
                    if (kaede_subsets[sz+1][i+kaede[n]] >= MOD)
                        kaede_subsets[sz+1][i+kaede[n]] -= MOD;
                    kanade_subsets[sz+1][i+kanade[n]] += kanade_subsets[sz][i];
                    if (kanade_subsets[sz+1][i+kanade[n]] >= MOD)
                        kanade_subsets[sz+1][i+kanade[n]] -= MOD;
                }
            }
        }

        // do prefix sums for kaede
        vector< vector<int> > kaede_psums(N+1, vector<int>(100*N+2,0));
        for (int n=0; n<=N; ++n) for (int i=0; i<=100*N; ++i)
            kaede_psums[n][i+1] = (kaede_psums[n][i] + kaede_subsets[n][i]) % MOD;

        long long answer = 0;
        // try all possibilities for kanade's last number
        for (int last=0; last<N; ++last) {
            // recompute the subsets for kanade 
            // if she cannot use the chosen number
            int chosen = kanade[last];
            vector< vector<int> > kanade_subsets_fixed = kanade_subsets;
            for (int sz=1; sz<=N; ++sz) for (int i=0; i<=100*N; ++i) 
            if (kanade_subsets_fixed[sz-1][i]) {
                kanade_subsets_fixed[sz][i+chosen] -= kanade_subsets_fixed[sz-1][i];
                if (kanade_subsets_fixed[sz][i+chosen] < 0)
                    kanade_subsets_fixed[sz][i+chosen] += MOD;
            }
            // try all possibilities for the number of full rounds without a loss,
            // and all possibilities for kanade's score in them
            for (int full=0; full<N; ++full)
            for (int kanade_score=0; kanade_score<S; ++kanade_score) {
                // kaede's score from full+1 rounds must be such 
                // that kaede_score + kanade_score < S 
                // but kaede_score + kanade_score + chosen >= S
                int kaede_score_lo = max(0, S - kanade_score - chosen );
                int kaede_score_hi = min(100*N + 1, S - kanade_score);
                if (kaede_score_lo > kaede_score_hi) continue;
                if (kanade_score > 100*N) continue;

                long long kanade_ways = kanade_subsets_fixed[full][kanade_score];
                long long kaede_ways = kaede_psums[full+1][kaede_score_hi] 
                                       - kaede_psums[full+1][kaede_score_lo];
                if (kaede_ways < 0) kaede_ways += MOD;
                long long add = ((kaede_ways * kanade_ways) % MOD) * coefficients[full];
                answer = (answer + add) % MOD;
            }
        }
        return answer;
    }