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

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

So, overall,

$$F(n, k)= \frac{1}{n^2} \displaystyle \sum_{\sum x_i = n} \left [ \left ( undefined + 1)} \prod (n x_i F(x_i, k - 1)) \right ]$$

[latex]F(1, k) = 1[/latex] is clearly a polynomial of degree [latex]0[/latex].

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

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