September 23, 2021 Single Round Match 813 Editorials

LightbulbRow

We can proceed as follows:

1. Count the currently lit bulbs. Determine whether we need more or less (or whether we are good).
2. Move from the starting location all the way to the leftmost bulb.
3. For each bulb: If we need more lit bulbs and it’s off, turn it on. If we need fewer lit bulbs and it is on, turn it off. Then, if this is not the last bulb, take a step right.

The first phase requires no actions at all. The second phase requires at most N-1 steps. The third phase requires at most N lightbulb toggles and N-1 steps. Together, we need at most 3N-2 actions.

public String solve(String bulbStates, int startIndex, int goalCount) {
    int N = bulbStates.length();
    boolean[] bulbs = new boolean[N];
    for (int n=0; n<N; ++n) bulbs[n] = (bulbStates.charAt(n) == 'O');

    int currentlyLit = 0;
    for (boolean bulb : bulbs) if (bulb) ++currentlyLit;

    String answer = "";
    int where = startIndex;
    while (where > 0) { answer += '<'; --where; }

    for (int n=0; n<N; ++n) {
        if (currentlyLit < goalCount && !bulbs[n]) { 
            answer += 'S'; ++currentlyLit;
        }
        if (currentlyLit > goalCount && bulbs[n]) {
            answer += 'S'; --currentlyLit;
        }
        if (currentlyLit == goalCount) return answer;
        answer += '>';
    }
    return answer;
}

Challenge: Can you solve the same problem if we decrease the limit from 3*N to at most 2.5*N actions?

LooRollPyramid

For an obvious reason, our pyramid sizes are called triangular numbers in math. The size of a pyramid with bottom length n is triangle(n) = 1+2+…+n = n(n+1)/2. Thus, if we know the bottom length of our pyramid, we can calculate its full size, and from that we can determine the number of rolls we are missing.

Our partial pyramid surely consists of two parts:

• At the bottom, zero or more rows with some rolls.
• At the top, zero or more completely empty rolls.

Thus, the rolls we are missing from a complete pyramid are the C rolls that finish the current potentially-incomplete row, plus the rolls used to fill the remaining completely empty rows. All we need to determine C is to determine the number of empty rows.

The number of empty rows is the largest r such that triangle(r) is at most equal to the total number of rolls we are missing from a complete pyramid. And once we make this observation, we can find this r efficiently: We can either derive a formula for r, or we can find it in O(log A) time using binary search.

(It was also possible to find the number of non-empty rows this way: here, we are looking for the smallest n such that A + (A-1) + … + (A+n-1) is greater than or equal to B. The approach is essentially the same as above, only the math is a tiny bit more complicated.)

Once we find r, the answer we need is C = triangle(A) – B – triangle(r), and we are done.

long triangle(long side) { 
    long x = side, y = side+1;
    if (x % 2 == 0) x /= 2; else y /= 2;
    return x*y;
}

public int[] countMissing(int Q, int[] A, long[] B) {
    int[] C = new int[Q];
    for (int q=0; q<Q; ++q) {
        long full = triangle( A[q] );
        int lo = 0, hi = A[q]+1;
        while (hi - lo > 1) {
            int med = (lo + hi) / 2;
            if (B[q] + triangle(med) <= full) lo = med; else hi = med;
        }
        C[q] = (int)(full - B[q] - triangle(lo));
    }
    return C;
}

PartialRaceResults

The key to solving this task is realizing that each information of the form “X:YZ” can be represented as two separate pieces of information: Y must finish before X, and X must finish before Z. These pieces of information can be stored as directed edges of a graph. Once we do this, all that remains is finding any one finishing order that matches all the information we have – i.e., a topological order in the digraph we just constructed.

Given how small the graph is (at most 62 vertices), we can use essentially any polynomial-time algorithm. The simplest implementation is probably obtained by implementing Warshall’s transitive closure algorithm (which is a simpler but almost identical version of the Floyd-Warshall all-pairs shortest paths algorithm). If there are any cycles in the graph – i.e., if any vertex is reachable from itself – there is no topological order. Otherwise, we can construct one valid order by sorting all vertices according to the number of incoming edges they have in the transitive closure. (Of course, a standard DFS-based implementation of the topological order algorithm can be used instead of the algorithm we just described. This approach solves the problem in linear time.)

int toID(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';
    if (c >= 'A' && c <= 'Z') return 26 + c - 'A';
    if (c >= '0' && c <= '9') return 52 + c - '0';
    return -47;
}

char toChar(int id) {
    if (id < 26) return (char)(id + 'a');
    if (id < 52) return (char)(id - 26 + 'A');
    return (char)(id - 52 + '0');
}

public String reconstruct(String[] memories) {
    boolean[] present = new boolean[62];
    boolean[][] G = new boolean[62][62];
    for (String memory : memories) {
        int x = toID(memory.charAt(0));
        int y = toID(memory.charAt(2));
        int z = toID(memory.charAt(3));
        present[x] = present[y] = present[z] = true;
        G[y][x] = true;
        G[x][z] = true;
    }
    for (int k=0; k<62; ++k) for (int i=0; i<62; ++i) for (int j=0; j<62; ++j)
        G[i][j] = (G[i][j] || (G[i][k] && G[k][j]));
    for (int k=0; k<62; ++k) if (G[k][k]) return "";
    
    int[] dependencies = new int[62];
    for (int i=0; i<62; ++i) for (int j=0; j<62; ++j)
        if (G[i][j]) ++dependencies[j];

    int P = 0;
    for (boolean p : present) if (p) ++P;
    int[] order = new int[P];
    for (int i=0; i<62; ++i) if (present[i]) order[--P] = i;

    P = order.length;
    for (int i=0; i<P; ++i) for (int j=i+1; j<P; ++j)
        if (dependencies[order[j]] < dependencies[order[i]]) {
            int t=order[i]; order[i]=order[j]; order[j]=t;
        }
    
    String answer = "";
    for (int x : order) answer += toChar(x);
    return answer;
}

RaftingOnDunajec

There are multiple ways of counting these combinatorial objects. We will show one of them.

If there was no restriction that each sight must be covered by some company, we could easily count all ways in which C companies can offer their services: each company has (S+1 choose 2) options which service to offer, their choices are independent, so there are arbitrary(S,C) = (S+1 choose 2)^C total schedules.

In order to count the good schedules, we will now count the bad schedules and subtract those from the total. Let good(S,C) and bad(S,C) denote the number of good and bad schedules with S sights and C companies, respectively.

In each bad schedule there are some sights that are never covered. We can divide all bad schedules into disjoint groups based on which is the first (smallest-numbered) sight that is not covered by any company.

Suppose we are in group f – i.e., sight f (using 0-based numbering) is the first uncovered sight. This means that each company operates either completely before f, or completely after. We can further divide the schedules in this group into buckets based on the number x of companies that are operating upstream of sight number f.

As all the buckets are disjoint, we can compute bad(S,C) simply by summing the sizes of all the buckets.

Now, consider any bucket (f,x). How many different schedules does it contain? We have:

• (C choose x) ways to choose which companies operate before the first bad sight f.
• good(f,x) ways to choose the offers for those companies so that they completely cover the sights before sight f
• arbitrary(S-f-1,C-x) ways to choose the offers for the remaining companies anywhere on the sights after sight f

And as all three choices we can make are mutually independent, the size of the bucket (f,x) is the product of the three values described above.

This recurrence gives us an O(S^2 C^2) algorithm to compute good(S,C) using dynamic programming.

public int count(int S, int C) {
    long MOD = 1_000_000_007;
    long[][] comb = new long[1001][];
    for (int n=0; n<=1000; ++n) {
        comb[n] = new long[n+1];
        for (int k=0; k<=n; ++k) {
            if (k == 0 || k == n) {
                comb[n][k] = 1;
            } else {
                comb[n][k] = (comb[n-1][k-1] + comb[n-1][k]) % MOD;
            }
        }
    }

    long[][] good = new long[S+1][C+1];
    long[][] arbitrary = new long[S+1][C+1];
    good[0][0] = 1;
    for (int s=0; s<=S; ++s) arbitrary[s][0] = 1;

    for (int s=1; s<=S; ++s) for (int c=1; c<=C; ++c) {
        arbitrary[s][c] = comb[s+1][2];
        if (c > 1) {
            arbitrary[s][c] *= arbitrary[s][c-1];
            arbitrary[s][c] %= MOD;
        }
    }

    for (int s=1; s<=S; ++s) for (int c=1; c<=C; ++c) {
        good[s][c] = arbitrary[s][c];
        // iterate over the first bad (unvisited) sight
        for (int fb=0; fb<s; ++fb) {
            // iterate over the # of companies before sight #fb
            for (int left=0; left<=c; ++left) {
                long curr = comb[c][left];
                curr *= good[fb][left];
                curr %= MOD;
                curr *= arbitrary[s-fb-1][c-left];
                curr %= MOD;

                good[s][c] -= curr;
                good[s][c] += MOD;
                good[s][c] %= MOD;
            }
        }
    }
    return (int)good[S][C];
}

PrettyPrimes

As above, this problem also has multiple approaches that can get you to a working solution. We’ll describe one we like because it uses some number theory insights to keep the implementation reasonably simple.

For small values of D we can easily solve the task by iterating over all D-digit numbers. This is always a good idea, as it automatically gets rid of all small special cases. Depending on the approach used for the rest of the task, cases like pattern=11 and D=2 can be nasty. (This is the only pattern of the form XX that actually has all D-1 possible occurrences. Within our constraints all bigger numbers with all digits equal are composite.)

The insight we’ll need for bigger D is that primes are quite frequent: according to the prime number theorem, around the number n there is approximately one prime in each ln(n) numbers. This means that on average one out of 28 random 12-digit numbers will be prime. If we restrict ourselves to numbers that aren’t obviously composite due to their last digit, the expectation goes down to roughly one prime per 11 attempts.

As soon as we have a number that is not just the copies of our desired pattern but also a few extra digits, the count of such numbers quickly becomes quite large – and even though these number aren’t distributed exactly the same way an uniformly random subset would be, their distribution is still arbitrary enough (in a way unrelated to primes). Thus, we should expect that for large D there will always be some almost-perfect solutions. And the number of candidates for almost-perfect solutions is so small that we can generate and check all of them. In fact, the number of possible inputs is so small that we can afford to do this for all possible inputs. In the best-case scenario, we will know that we are done with the task. (Spoiler: this is what actually happens.) In a theoretically possible worse scenario, we may identify several problematic inputs where we need to deepen our search. But if worse comes to worst, those inputs can then always be precomputed using brute force.

In the next two paragraphs we go in detail over two examples to illustrate the above intuition in detail.

For the first example let’s consider the case where pattern=47 and D=12. The only 12-digit number with six occurrences of our pattern is 474,747,474,747, and that clearly isn’t a prime – it’s a multiple of 47. (This will clearly always be the case.) The next best thing are five occurrences of the pattern. There are 2,040 such numbers, which is way more than 28. Even though these aren’t chosen exactly uniformly at random, we expect that an appropriate fraction among them should be prime. And indeed, they are. In this particular case, 169 out of those 2,040 numbers are prime, which is roughly one in 12 – about what we would expect for a collection of random numbers in which most numbers end in a 7.

For the second example consider pattern=42 and D=12. Here, most of the numbers with five occurrences of the pattern will end in 42 and therefore they will be composite. But still, among the 2,040 twelve-digit numbers with five occurrences of this pattern there are 236 that end with 1, 3, 7, or 9. (One of the extra digits is the last odd digit. We have six possible positions and usually ten possible values for the other extra digit.) Out of those 236, 21 are prime – which is again somewhere between one in 11 and one in 12. Seeing 21 primes in this example case makes it highly unlikely that for any other two-digit pattern the number of primes will drop all the way to zero.

In the sample implementation shown below we generate a set of candidates by taking the repeated pattern and inserting at most three extra digits into it in all possible ways. Note how we do it without special-casing each number of extra digits. Also note that this generates some numbers with a smaller number of pattern occurrences if we insert the new digits in dumb places, but we don’t care about those, as they will never get processed in the later steps and the total number of candidates is still small enough.

Then we group the candidates by the number of pattern occurrences they actually contain, and we then test everything in those groups for primality until we find a group that works. We can easily verify that in each case that group is still one of those for which we generated all possible members, and therefore the solutions we found are all correct.

set<long long> generate_candidates(int pattern, int D) {
    // generate all numbers that can be obtained from a repeated pattern
    // by inserting at most three extra digits
    set<long long> answer;
    vector<int> repeated = { pattern/10, pattern%10 };
    if (repeated[0] == 0) repeated[0] = repeated[1];
    for (int a=0; a<D+3; ++a)
    for (int b=a+1; b<D+3; ++b) 
    for (int c=b+1; c<D+3; ++c) {
        for (int va=0; va<10; ++va)
        for (int vb=0; vb<10; ++vb)
        for (int vc=0; vc<10; ++vc) {
            if (a == 0 && va == 0) continue; // no leading zeros
            long long curr = 0;
            for (int i=0, p=0; i<D; ++i) {
                if (i == a) curr = 10*curr + va;
                else if (i == b) curr = 10*curr + vb;
                else if (i == c) curr = 10*curr + vc;
                else curr = 10*curr + repeated[(p++)%2];
            }
            answer.insert(curr);
        }
    }
    return answer;
}

bool is_prime(long long N) {
    if (N < 2) return false;
    for (long long d=2; ; ++d) {
        if (d*d > N) return true;
        if (N%d == 0) return false;
    }
}

int count_occurrences(long long N, int pattern) {
    int answer = 0;
    if (pattern >= 10) {
        while (N >= 10) {
            if (N % 100 == pattern) ++answer;
            N /= 10;
        }
    } else {
        while (N > 0) {
            if (N % 10 == pattern) ++answer;
            N /= 10;
        }
    }
    return answer;
}

int solve(int pattern, int D) {
    map<int, vector<long long> > buckets;
    for (auto cand : generate_candidates(pattern, D))
       buckets[ count_occurrences(cand,pattern) ].push_back(cand);
    for (int d=D; d>=0; --d) {
        vector<long long> found;
        for (auto cand : buckets[d]) if (is_prime(cand)) found.push_back(cand);
        if (!found.empty()) {
            long long answer = 0;
            for (auto cand : found) answer = (answer + cand) % 1000000007;
            return answer;
        }
    }
    return -47;
}