### hmehta's blog

By hmehta, history, 13 days ago,

Hi Everyone,

TCO20 Algorithm Finals – the most awaited Topcoder tournament of the year is almost here. Will tourist reign supreme or does someone else in the group have what it takes?

16 top-rated members will be competing in the next few weeks for the ultimate title of Topcoder Open.

Here’s how the semifinal rounds look:

#### Semi-Final 2 Group

TCO20 Algorithm Rounds will be broadcasted live and you’ll be able to listen to the amazing hosts Errichto and Lewin during the contest as they will explain the problems, do live commentary, and show you the competitors’ screens. They will be joined by some amazing guest competitors on each broadcast and also there are some exciting post match interviews planned too.

Find the full schedule with all the details and signup links to the event here

#### TCO20 Special Rookie SRM with Prizes

If you are new to Topcoder, we are also organising an interesting educational beginner contest with prizes after Semifinal 2:

TCO20 Special Rookie SRM

Wednesday, November 18, 2020 13:00 UTC-5

The Rookie SRM is open to everyone and has some special cash prizes. It will only be **rated** for members who have competed in equal to or less than 5 rounds or if their current rating is less than 800 rating points.

Prizes:

• 1st :: $300 • 2nd ::$200
• 3rd :: $100 •$25 for 5 other random participants
• Topcoder T-shirt for Top 30
• *All prizes are only for members who are eligible to be rated.

We hope to see you there!

• +98

 » 13 days ago, # |   +18 Is it necessary for spectators to register somewhere? Why not just make a Youtube broadcast?
•  » » 13 days ago, # ^ |   +3 As far as I know, there will be Youtube broadcast too but there is no link yet. You should register to Hopin event if you want to ask us questions during a stream like "what about N=1" or "can you show tourist's screen".
•  » » 13 days ago, # ^ | ← Rev. 2 →   +11 It will be broadcasted on (I will update the Youtube link as soon as it is set)However as Errichto said — You should register to Hopin Event if you want to ask questions during the stream. :)
 » 13 days ago, # |   -41 Finally , a real match that isn't fix like MI vs DC where we can gamble and deserving will win . Not the person with more money (Ambani).Btw, please post YouTube link also
 » 13 days ago, # |   -53 if their current rating is less than 800 rating points.Can you please make it 1845 instead?Thanks and Regards,Aryan Choudhary
 » 13 days ago, # |   +23 hmehta, can we have official final standings together with decisions regarding challenges, finals quota and everything somewhere?
•  » » 12 days ago, # ^ |   +3 Hey KAN, The Final results were adjusted and updated: https://community.topcoder.com/stat?c=round_overview&er=5&rd=18398The announcement was made on the broadcast and we will also be doing an official post about it today later in the day on the Finalists Forum and also on the General Forums.
 » 13 days ago, # |   +6 I fixed some redundancy issues in my 500, and now I pass systests in 640 ms and 160 MB. But on my challenge case, my code takes over 20 seconds and several GB.I'm very curious now what the reference solution is. Is it possible that my challenge requests timed out because my test case timed out the reference solution?
•  » » 13 days ago, # ^ |   +76 Lewin confirmed that my test case breaks the reference solution. That explains why my challenges on Jacob kept getting "Your request timed out."Here's the test case: 1, 28, 41, 1, 6, 41, 38, 6, 4, 38, 48, 4, 14, 48, 52, 14, 12, 52, 31, 12, 22, 31, 27, 22, 11, 27, 39, 11, 23, 39, 35, 23, 9, 35, 30, 9, 7, 30, 47, 7, 20, 47, 44, 20, 3, 44, 40, 3, 8, 40, 33, 8, 24, 33, 49, 24, 16, 49, 32, 16, 10, 32, 34, 10, 5, 34, 37, 5, 17, 37, 51, 17, 13, 51, 36, 13, 15, 36, 46, 15, 21, 46, 43, 21, 2, 43, 29, 2, 19, 29, 45, 19, 26, 45, 42, 26, 18, 25, 42, 50, 25, 50, 28, 18 The main idea is that the numbers 1-26 are all independent and set up at an odd distance, but they each affect the numbers 27-52 differently. The test case is a shuffled and slightly modified version of the following test case: 1, 27, 28, 1, 2, 28, 29, 2, 3, 29, 30, 3, 4, 30, 31, 4, 5, 31, 32, 5, 6, 32, 33, 6, 7, 33, 34, 7, 8, 34, 35, 8, 9, 35, 36, 9, 10, 36, 37, 10, 11, 37, 38, 11, 12, 38, 39, 12, 13, 39, 40, 13, 14, 40, 41, 14, 15, 41, 42, 15, 16, 42, 43, 16, 17, 43, 44, 17, 18, 44, 45, 18, 19, 45, 46, 19, 20, 46, 47, 20, 21, 47, 48, 21, 22, 48, 49, 22, 23, 49, 50, 23, 24, 50, 51, 24, 25, 51, 52, 25, 26, 52, 27, 26 This way, after the first 26 choices there are exactly $2^{26}$ different states. The number of states peaks at about $10^8$, for the prefix of length 28.
•  » » » 13 days ago, # ^ |   +20 If TopCoder really managed to have problems with a model solution on finals two years in a row, I am quite impressed.
•  » » » 13 days ago, # ^ | ← Rev. 2 →   +31 I quite enjoyed that vibe "we have solved medium pretty much immediately, what are they doing, why are they going for hard" on stream. Yeah, we just decided that 2^26 * 26 is a bit too much and setter wouldn't go out of his way to set limitations to 52 if he wanted such solutions to pass.
 » 12 days ago, # | ← Rev. 2 →   +49 1000Let $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 $\binom{n}{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 $\binom{n-1}{x_1-1}\binom{n-x_1-1}{x_2-1}\binom{n-x_1-x_2-1}{x_3-1}\ldots$ ways to choose these components. There are $u = \binom{n}{2} - \sum \binom{x_i}{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)= \dfrac{1}{n^2} \displaystyle \sum_{\sum x_i = n} \left [ \left ( \binom{n-1}{x_1-1} \binom{n-x_1-1}{x_2-1}\ldots \right )(K-k)^{\binom{n}{2} + 1 - \sum (\binom{x_i}{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 $\binom{x_i}{2}$. So, the overall degree would be $\binom{n}{2} + 1 - \sum (\binom{x_i}{2} + 1) + \sum \binom{x_i}{2} \leq \binom{n}{2} - 1$. So, $F(n, k) - F(n, k - 1)$ is a polynomial in $k$ of degree $\binom{n}{2} - 1$. $F(n, k)$ is the prefix sum of this polynomial and hence has a degree $\binom{n}{2}$.We can find $F(n, k)$ for all $1 \leq n \leq N$, $1 \leq k \leq \binom{N}{2}$ using the recurrence above in $O(N^5)$ with a small constant and then use lagrange interpolation to recover $F(N, K)$. codepublic class UniqueMST{ int mod; int add(int a, int b){a += b; if(a >= mod) a -= mod; return a;} int sub(int a, int b){a -= b; if(a < 0) a += mod; return a;} int mul(int a, int b){return (int)((a * 1L * b) % mod);} int powr(int a, long b){ int ret = 1; for(; b > 0; b >>= 1, a = mul(a, a)) if(b % 2 == 1) ret = mul(ret, a); return ret; } int inv(int a){ return powr(a, mod - 2); } int lagrange(int [] v, int x){ int k = v.length - 1; if(x <= k) return v[x]; int ret = 0; for(int i = 0; i <= k; i++){ int num = 1, den = 1; for(int j = 0; j <= k; j++) if(j != i){ num = mul(num, sub(x, j)); den = mul(den, sub(i, j)); } ret = add(ret, mul(v[i], mul(num, inv(den)))); } return ret; } public int count(int N, int K, int M){ if(N == 2) return K; mod = M; int E = (N * (N - 1))/2; int [][] C = new int[N + 1][N + 1]; int [][] dp = new int[N + 1][E + 1]; int [] F = new int[N + 1]; int [] H = new int[N + 1]; for(int i = 0; i <= N; i++){ C[i][0] = 1; for(int j = 1; j <= i; j++){ C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } } for(int k = 0; k <= E; k++){ dp[1][k] = 1; dp[2][k] = k; } for(int n = 3; n <= N; n++){ for(int k = 1; k <= E && k < K; k++){ int inv_choices = inv(K - k); int curr = inv_choices, P = 1; F[0] = 1; for(int m = 1; m <= n; m++){ P = mul(P, inv_choices); H[m] = mul(mul(n * m, dp[m][k - 1]), curr); curr = mul(curr, P); F[m] = 0; for(int r = 1; r <= m; r++){ F[m] = add(F[m], mul(C[m - 1][r - 1], mul(H[r], F[m - r]))); } } dp[n][k] = mul(inv(n * n), mul(powr(K - k, (n * (n - 1)) / 2 + 1), F[n])); } } if(K <= E + 1) return dp[N][K - 1]; return lagrange(dp[N], K - 1); } } 
•  » » 12 days ago, # ^ |   +3 Nice problem! I was close, I thought for some reason that edges not in MST in smaller parts should also be smaller than $k$, so I had to try $O(n^4)$ values for transition (to get wrong answer), but everything else is pretty much the same.
 » 9 days ago, # | ← Rev. 2 →   -10 Gentle Reminder: Registration for the Rookie SRM is now open :)
 » 5 days ago, # |   +23 Finals will start in 25 minutes! Watch on Hopin or Twitch (https://www.twitch.tv/topcoder_official).
 » 4 days ago, # |   +3
 » 4 days ago, # |   -7 tourist aura?
 » 4 days ago, # |   -7 Feeling sad for um_nik with um_nik and 69 others.