November 26, 2019 TCO19 Algorithm Semi Final 1 Editorials

RaceCondition

Let’s go through each of the cases, simplifying the problem. First let’s get rid of lines with zero people.

If there is only one line with people, the answer is just the number of people in the line (similar to the first sample case). There’s no way we can do any better since we can’t rearrange the sequence of events.

Next, if the answer is one, the answer must look something as follows:

(events with no writes) a (events with no a’s or A’s) A 

This is possible to achieve only when the shortest line has one person, which we can detect.

Now, it is tempting to say that the answer at this point is just the minimum of the number of people in some line. However, we claim we can always achieve two.

In this case, we have at least two lines, and all lines have at least two people. To achieve two, we can have something that looks as follows:

a (events with no a’s or A’s) A b (events with no b’s or B’s) B

Here, a and b are different, so we can put all the extra people in a’s line in the second block, and all the extra people in b’s line in the first block, and any other extra people in other lines in either block. This way, we can always get two.

Sample code:

public String minimize(int[] gates) {
    int N = gates.length;
    String answer = "";
    for (int n=0; n<N; ++n) if (gates[n] == 1) {
        answer += (char)('a'+n);
        for (int i=0; i<N; ++i) if (i != n) for (int j=0; j<gates[i]; ++j) { answer += (char)('a'+i); answer += (char)('A'+i); }
        answer += (char)('A'+n);
        return answer;
    }
    int a=-1, b=-1;
    for (int n=0; n<N; ++n) if (gates[n] != 0) { if (a == -1) a = n; else { if (b == -1) b = n; } }
    if (a == -1) {
        return answer;
    }
    if (b == -1) {
        for (int j=0; j<gates[a]; ++j) { answer += (char)('a'+a); answer += (char)('A'+a); }
        return answer;
    }
    answer += (char)('a'+a);
    for (int i=0; i<N; ++i) if (i != a && i != b) for (int j=0; j<gates[i]; ++j) { answer += (char)('a'+i); answer += (char)('A'+i); }
    for (int j=0; j<gates[b]-1; ++j) { answer += (char)('a'+b); answer += (char)('A'+b); }
    answer += (char)('A'+a);
    answer += (char)('a'+b);
    for (int j=0; j<gates[a]-1; ++j) { answer += (char)('a'+a); answer += (char)('A'+a); }
    answer += (char)('A'+b);
    return answer;
}

SlideCardsLeft

We can guess that we always move the leftmost card that matches its position. We can write a brute force and notice some patterns.

To prove that this is optimal, consider a binary number where the i-th bit is one if number (i-1) is in position (i-1). Initially, this number is 2^n – 1. At each step, this number must strictly decrease. To show this, consider the number x being moved. That position changes from 1 to 0, and any higher order bits are not affected. Lower bits may possibly change, but this doesn’t affect that the new position is already strictly less. Thus, we get an upper bound of 2^n – 1, and we always uniquely choose the move that decreases this by one.

Using this observation, we can get a simple solution. Start from highest bit to the lowest bit. If the i-th bit is set, swap the i+1th element and 0-th element. Notice that the binary number decrements by exactly 2^i, and now, we no longer move any bits from i or higher (so effectively, we can say (i+1) is equivalent to zero and solve a smaller problem). This leads to the very short code below:

vector <int> SlideCardsLeft::getPosition(int N, long long steps) {
  vector<int> a(N);
  iota(a.begin(), a.end(), 0);
  for (int b = 60; b >= 0; b--) {
    if (steps & (1LL << b)) {
      if (b + 1 >= N) {
        return vector<int>();
      }
      swap(a[b + 1], a[0]);
    }
  }
  return a;
}

SpanningNoLine

We use inclusion exclusion and generalized cayley’s formula. 

If you fix the edges that must be in the spanning tree on the line, you can get a formula for the number of ways to complete the spanning tree. Here you can use Prufer to get a formula based on the sizes of the components after fixing some edges (see link here).

This is way too slow, with 2^m states for inclusion exclusion, so the way to do it is to batch it by the number of edges. If we fix k edges, we will get m-k components. We want to find sum of a_1*a_2*…*a_(m-k) over all ways where a_i are positive integers and sum a_i = m (and we multiply this sum by n^(n-k-2) * (-1)^k and sum it up to get the final answer). Two ways are different if some a_i is different.

To get the combinatorial interpretation, we can do a variation of bars and stars. We use three objects instead of two (bars, stars, and dots).

Start with m dots, then place m-k-1 bars to split into some buckets, each with at least one dot. In each bucket, choose one dot to become a star. For example, the following picture is a valid example:

.*|..*.|..*.|..*.

There is exactly one star in each bucket, so the number of ways this particular arrangement contributes after fixing bars is exactly equal to the product of the sizes of the buckets. 

More specifically, we will have m-k stars, m-k-1 bars, and k dots. Next, to force each bucket to have exactly one star, we can notice this is equivalent to forcing the bars and stars to alternate (starting with a star). We can combine these into one object. The total number of ways is then C(m+m-k-1, k) total ways.

All of these things can be computed in linear time, which leads to a linear time solution overall.

public class SpanningNoLine {
    int mod = 998244353;
    long exp(long b, long e) {
        long r = 1;
        while(e>0) {
            if (e % 2 == 1) r = r * b % mod;
            b = b * b % mod;
            e >>= 1;
        }
        return r;
    }
    long[] fact, ifact, inv;
    void getFIF(int max, int mod) {
        fact = new long[max];
        ifact = new long[max];
        inv = new long[max];
        inv[1] = 1;
        for (int i = 2; i < max; i++) {
            inv[i] = (mod - mod/i) * inv[mod % i] % mod;
        }
        fact[0] = 1;
        ifact[0] = 1;
        for (int i = 1; i < max; i++) {
            fact[i] = fact[i-1] * i % mod;
            ifact[i] = ifact[i-1] * inv[i] % mod;
        }
    }
    public long comb(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[n-k] % mod * ifact[k] % mod;
    }
    public int countSpanning(int n, int m) {
        getFIF(m+m, mod);
        long mult = mod - exp(n, n-1);
        long ivn = mod - exp(n, mod-2);
        long ans = 0;
        for (int i = 0; i < m; i++) {
            mult = mult * ivn % mod;
            ans = (ans + mult * comb(m - i - 1 + m, i)) % mod;
        }
        return (int)(ans % mod);
    }
}