April 18, 2022 TCO22 Round 1A Editorial

SkyscraperReconstruction

Both this and the hard problem in the round have the same setting: we have N skyscrapers in a row, and their heights are a permutation of 1-N. When viewed from a side, some skyscrapers are at least partially visible (e.g., the first skyscraper is always completely visible) and some are completely hidden by previous ones. Here is a figure from the problem statement: one configuration of N=7 skyscrapers, with visible floors shown as ‘O’ and floors hidden from the observer as ‘X’.

->                   O
->                   O  X
->          O        X  X
->          O  X     X  X
->    O     X  X     X  X
->    O     X  X  X  X  X
->    O  X  X  X  X  X  X
=============================

We are given the top view of such a row of skyscrapers (in our example, this would , and our goal is to reconstruct one possible sequence of skyscraper heights.

We can make two observations:

• A skyscraper is completely hidden if and only if there is a taller skyscraper on its left. Thus, intuitively, we want to assign small heights to the skyscrapers that should be hidden.
• On the other hand, a skyscraper is visible only if it’s taller than everything to its left. And this means that as we go from left to right, heights of visible skyscrapers increase – the next one always needs to be taller than the previous one in order to be visible. (And in particular, the last visible skyscraper must always have height N.)

This leads us to a simple greedy strategy that always creates a valid configuration of skyscrapers:

1. Going from the right to the left, assign heights N, N-1, N-2, … to the visible skyscrapers.
2. Assign the remaining heights to the other skyscrapers arbitrarily.

(This can also be done in a single pass from right to left: whenever you see a skyscraper that should be visible, give it the largest available height, and whenever you see one that should remain hidden, give it the smallest available height.)

It should be clear that once this algorithm is done, all skyscrapers that should be hidden are hidden (as they are all smaller than the very first skyscraper) and all skyscrapers that should be visible are visible (as they form an increasing sequence from the left to the right, and the other skyscrapers are too small to block them).

An alternate solution

Many other greedy approaches will also produce valid solutions. 

For example, another valid strategy is to start with the permutation (1, 2, …, N) and then split the input string into blocks of the form OX…X, and reverse the segment of the permutation that corresponds to each such block. For example, the sample input can be divided into OX + OXX + OX, so the final permutation will be (2, 1) + (5, 4, 3) + (7, 6).

As the order of the blocks is preserved, the visible skyscrapers do again form an increasing sequence. (In our example this is the sequence 2, 5, 7.) And within each block the reversal makes the visible skyscraper taller than the immediately following hidden ones.

Both solutions can be implemented to run in O(N) time. Below we show a third possible implementation that uses two passes. In the first pass it counts how many of the skyscrapers are visible and in the second pass it then assigns the heights so that both the visible and the invisible skyscrapers increase from the left to the right.

public int[] reconstruct(String visibility) {
    int N = visibility.length();
    int countVisible = 0;
    for (int n=0; n<N; ++n) if (visibility.charAt(n) == 'O') ++countVisible;
    int nextVisible = N+1-countVisible;
    int nextInvisible = 1;
    int[] answer = new int[N];
    for (int n=0; n<N; ++n) if (visibility.charAt(n) == 'O') {
        answer[n] = nextVisible++;
    } else {
        answer[n] = nextInvisible++;
    }
    return answer;
}

SingleOrDouble

This problem can be solved by treating the whole situation as a Markov process with two states: either the last roll was B (in which case another B wins it for Bob) or the last roll wasn’t B (in which case only Alice can win in the next roll). We can have one variable for each state (“if we start from this state, what is the probability Alice will win?”) and we can solve a system of two linear equations to determine their values.

However, by doing a slightly more clever analysis we can derive an even simpler formula.

Let pA be the probability of getting a single A, and let pB be the probability of getting a single B. 

Then, let p be the probability that Alice eventually wins the game, i.e., the value we should output.

We can now argue as follows:

• If the first roll is A, Alice wins (this happens with probability pA)
• If the first roll is B and the second roll is A, Alice wins (prob. pB*pA)
• If the first roll is B and the second roll is B, Bob wins (prob. pB*pB)
• If the first roll isn’t A, or if the first roll is B and the second is something other than A and B, we are back where we started, and from this position Alice wins with probability p – the dice have no memory 🙂

Thus, we now get a single linear equation: p = pA*1 + pB*pA*1 + pB*pB*0 + (1-pA-pB*pA-pB*pB)*p

This solves to p = (pA + pB*pA) / (pA + pB*pA + pB*pB).

We can determine both values pA and pB by doing some math or by computing them using a very simple application of dynamic programming: Let pp[i][j] = the probability of getting sum j when rolling i dice. We have pp[0][0] = 1, and then each pp[i+1][j] is the sum of pp[i][j-k] / D over k=1..D. We then have pA = pp[N][A] and pB = pp[N][B].

public double probAlice(int N, int D, int A, int B) {
    // dynamic programming: compute the probabilities
    double[][] pp = new double[N+1][];
    pp[0] = new double[1];
    pp[0][0] = 1;
    for (int n=1; n<=N; ++n) {
        pp[n] = new double[n*D+1];
        for (int i=0; i<=(n-1)*D; ++i) {
            for (int d=1; d<=D; ++d) pp[n][i+d] += pp[n-1][i]/D;
        }
    }
    
    double pA = pp[N][A], pB = pp[N][B];
    return (pA + pB*pA) / (pA + pB*pA + pB*pB);
}

SkyscraperCounting

We have intentionally kept the bounds for this problem quite low to allow all kinds of polynomial-time solutions.

Below we will show two of them. First an O(N^3) solution that can be derived by doing one type of observations that are (at least in our humble opinion) more mechanical. Then we will show an O(N) solution that is very simple to implement but requires (again, in our humble opinion) a somewhat more clever observation.

Cubic solution

For our O(N^3) solution, imagine that we are assigning heights from N down to 1. If we want to end with a valid solution, we need to make sure that we never violate the given visibility. How to do this?

Height N must be assigned to the tallest (i.e., rightmost) visible skyscraper. Each of the following heights must either be placed to the right of the last assigned visible skyscraper (so that it remains hidden), or it must be assigned to the next visible skyscraper. 
Let states be the moments when we assign some height to a visible skyscraper. For each state we want to count the number of ways in which it can be reached. An easy way to do this is a forward DP: starting from the state “the last visible skyscraper just got height N” we process all states from the right to the left, and for each state we iterate over all possibilities of how many invisible skyscrapers we add before the next visible one.

public int count(String visibility) {
    if (visibility.charAt(0) == 'X') return 0;
    long MOD = 1_000_000_007;
    int N = visibility.length();
    
    int K = 0;
    for (int n=0; n<N; ++n) if (visibility.charAt(n) == 'O') ++K;
    int[] visible = new int[K];
    for (int i=0, n=0; n<N; ++n) {
        if (visibility.charAt(n) == 'O') visible[i++] = n;
    }

    long[][] dp = new long[K][N];
    dp[K-1][N-1] = 1;
    for (int k=K-1; k>0; --k) for (int n=0; n<N; ++n) {
        if (dp[k][n] == 0) continue;
        int totalSpotsRight = N - visible[k] - 1;
        int alreadyPlacedRight = N - n - 1;
        int availableSpotsRight = totalSpotsRight - alreadyPlacedRight;
        // for each p, try to place the next p skyscrapers to the right
        // of the current one, and then the next one as the next visible one
        long currentWays = 1;
        for (int p=0; ; ++p) {
            int nextId = n - 1 - p;
            if (nextId < 0) break;
            dp[k-1][nextId] += dp[k][n] * currentWays;
            dp[k-1][nextId] %= MOD;
            if (availableSpotsRight <= 0) break;
            currentWays *= availableSpotsRight;
            currentWays %= MOD;
            availableSpotsRight -= 1;
        }
    }

    long answer = 0;
    for (int n=0; n<N; ++n) if (dp[0][n] > 0) {
        long curr = dp[0][n];
        // finalize: place skyscrapers smaller than the first one
        for (int i=1; i<=n; ++i) curr = (curr * i) % MOD;
        answer += curr;
    }
    return (int)(answer % MOD);
}

Linear solution

Another way of thinking about the problem is as follows:

Suppose I know the total number of solutions for some visibility string V. Then, the number of solutions for the string V+’O’ is exactly the same. This is because in the new instance the last skyscraper has to be the globally tallest one, and we are left with assigning heights to the skyscrapers described by V.

And what can we tell about the number of solutions for the string V+’X’?

Let N = length(V+’X’). The last skyscraper should not be visible, so its height must be between 1 and N-1, inclusive. Thus, we have N-1 options for its height. And what happens once we choose the height X of this skyscraper? We are left with assigning heights {1, 2, …, X-1, X+1, …, N} to the skyscrapers described by V.

But it’s clear that the actual heights play no role, only their relative order matters. In other words, there is a clear bijection between these solutions and solutions in which we assign the heights {1, 2, …, N-1} to the skyscrapers described by V: take any solution of the first type and subtract 1 from all heights that are > X to get a solution of the second type, and vice versa.

Thus, the number of solutions for V+’X’ equals (N-1) times the number of solutions for V.

This gives us the promised simple formula: in order to count all solutions for a given V, just take the product of all 0-based indices of ‘X’ characters. (And note that we don’t even need to special-case the inputs that start with an ‘X’.)

public int count(String visibility) {
    long MOD = 1_000_000_007;
    long answer = 1;
    for (int n=0; n<visibility.length(); ++n) {
        if (visibility.charAt(n) == 'X') {
            answer *= n;
            answer %= MOD;
        }
    }
    return (int) answer;
}