November 17, 2020 2020 TCO Algorithm Semi Final 1 Editorials

Easy:

There are two important observations:

• For any n, final(n) = final(f(n)).
• For any n in [1, 10^18 – 1], 1 <= f(n) <= 1026. (each digit contributes <= 57, and number of digits <= 18).

So, we can first find for each s in [1, 1026], how many integers 1 <= n <= N have f(n) = s. This is a standard digit DP problem.

Define dp[L][s] to be the number of strings of length L, each of whose characters is in range [‘0’, ‘9] and the sum of ascii values of all its characters is s.

Then dp[L][s] = sum_{i in [48, 57]} dp[L – 1][s – i].

Let L be the length of the decimal representation of N. First, let’s find the contribution of integers with length < L. For each length l < L and the most significant digit d >= 1, we can find the contribution as:

for(int l = 1; l < L; l++){
           for(int d = 1; d < 10; d++){
               int v = '0' + d; // The contribution of the most significant digit.
               for(int s = 0; s + v < MAXS; s++){
                   freq[s + v] += dp[l - 1][s]; // The remaining l - 1 digits have ascii sum s
               }
           }
       }

Now, we need to add the contribution of all integers n with length = L and value <= N. Let digs[i] be the coefficient of 10^i in the decimal representation of N. Here, we iterate over the first position i where n and N have a different digit, and the digit d at that position:

int s = 0;
       for(int i = L - 1; i >= 0; i--){
           // All digits at positions > i are the same in n and N, and the sum of ascii values at these positions is s
           for(int d = (i==L-1); d < digs[i]; d++){ // If i == L - 1, we can't have the first digit as 0
               int v = '0' + d; // the i-th digit in n
               for(int x = 0; x + v + s < MAXS; x++){
                   // x = ascii sum in the remaining i digits.
                   // Total sum = x + v + s
                   freq[x + v + s] += dp[i][x];
               }
           }
           s += '0' + digs[i];
       }
       freq[s]++; // add the contribution of n = N

After we have found all the frequencies, we simply need to return the sum of freq[i] * f(i) for each i in [1, 1026].

Hard: Unique MST

Let \(K\) be a constant. For some \(k \leq K\), let \(F(n, k)\) be the number of ways to assign each edge of a complete graph with \(n\) nodes a weight in \([1, K]\), such that the all the edges in its unique MST (say \(T\)) have weights \( \leq k\). We’ll prove that \(F(n, k)\) for a fixed \(n\) is a polynomial in \(k\) of degree \({n}\choose{2}\).

Consider the forest obtained by removing all edges of \(T\) with weight equal to \(k\). Let the component sizes be \(x_1, x_2, \ldots, x_r\) (such that the component containing \(1\) has size \(x_1\), the component containing the smallest node not in the component of node \(1\) has size \(x_2\), so on). There are \({{n-1}\choose{x_1-1}}{{n-x_1-1}\choose{x_2-1}}{{n-x_1-x_2-1}\choose{x_3-1}}\ldots\) ways to choose these components. There are \(u = {{n}\choose{2}} – \sum {{x_i}\choose{2}} – r + 1\) non-MST edges with endpoints in different components. These \(u\) edges must have weight strictly greater than \(k\) (else \(T\) won’t be an MST or it won’t be the unique MST). So, we need to multiply by \((K-k)^u\). Now, in each component, there must be a unique MST and weights on MST must be \(< k\). So, we need to multiply by \(\prod F(x_i, k – 1)\). Also, we can connect these components with weight \(k\) MST edges in \(\displaystyle n^{r-2} \prod x_i \) ways (generalized cayley’s theorem).

So, overall,

$$F(n, k)= \frac{1}{n^2} \displaystyle \sum_{\sum x_i = n} \left [ \left ( {{n-1}\choose{x_1-1}}{{n-x_1-1}\choose{x_2-1}}\ldots \right )(K-k)^{{{n}\choose{2}} + 1 – \sum ({{x_i}\choose{2}} + 1)} \prod (n x_i F(x_i, k – 1)) \right ]$$

\(F(1, k) = 1\) is clearly a polynomial of degree \(0\).

For any \(n > 1\), if the number of components is greater than 1, all \( x_i < n \), and by induction \(F(x_i, k-1)\) is a polynomial in \(k\) of degree \({x_i}\choose{2}\). So, the overall degree would be \({{n}\choose{2}} + 1 – \sum ({{x_i}\choose{2}} + 1) + \sum {{x_i}\choose{2}} \leq {{n}\choose{2}} – 1\). So, \(F(n, k) – F(n, k – 1)\) is a polynomial in \(k\) of degree \({{n}\choose{2}} – 1\). \(F(n, k)\) is the prefix sum of this polynomial and hence has a degree \({n}\choose{2}\).

We can find \(F(n, k)\) for all \(1 \leq n \leq N\), \(1 \leq k \leq {{N}\choose{2}}\) using the recurrence above in \(O(N^5)\) with a small constant and then use lagrange interpolation to recover \(F(N, K)\).