#### Good job! You’re all caught up

Earlier Dismiss All

## 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)$$.

jy_25

Guest Blogger

categories & Tags

UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close