### chokudai's blog

By chokudai, history, 6 weeks ago, We will hold AtCoder Beginner Contest 252.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation! Comments (40)
 » 6 weeks ago, # | ← Rev. 2 →   interesting thanks for sharing the contest
 » C++20 when
 » I hope I can solve A~D in one hour!(And E…)PS:ABC250E has weak testcases, I can use hashing to solve it.AC code
•  » » lol, this is ABC250 submission!
•  » » » Yes, but I can't find ABC250 announcement!
 » wasnt problem E a minimum spanning tree problem.
•  » » Shortest paths actually
•  » » » just because it is asking sum of distance from node 1?
•  » » » » not just that, major fact is the weight of edges are not negative + can be any positive number upto 10^9
•  » » This line of thinking costs me 1 WA
•  » » I did Dijkstra,I don't know anything about MST but I guess the intended solution was dijksta
 » D can also be solved with DP: Solution
 » Harder version of E : https://codeforces.com/problemset/problem/545/E
 » Can someone plz tell why my solution for E is failing? I used dijsktras algo only
•  » » You forgot that edges are bidirectional. Also your Dijkstra is slow, because you visit the same node multiple times.
•  » » » Thanks!
 » 6 weeks ago, # | ← Rev. 4 →   F regretSo sad I didn't notice pushing the extra bread will solve the problemApparently tourist had the same problem, it costs him 1 minute to fix (orz).
•  » » haha same lmao i didnt realize that either. instead, in contest, before popping the 2nd smallest elemnt i checked if the leftover bread was smaller than or equal to the smallest bread in the pq and if it was you combine them there.
 » Does anyone know why PyPy3 gives runtime error but Python does not (and passes)?https://atcoder.jp/contests/abc252/submissions/31857332
•  » » Probably because math.comb is a Python 3.8 feature.
 » 6 weeks ago, # | ← Rev. 2 →   Can someone please check why my dijsktra is failing on E: https://atcoder.jp/contests/abc252/submissions/31874731In priority queue I am storing {total d of next vertex through this edge, {from vertex, to vertex}}. And I am choosing the one with smallest d and take if this is possible otherwise rejectPS: It's different from Dijsktra because instead of choosing the vertex with least weight and finding weights for other vertex, I am choosing the vertex which has least value according the previous vertices. Which I think is equivalent. Right?
•  » » I used the same strategy, but couldn't notice what's wrong with your code... Try starting from scratch? (it doesn't solve the mistake, but sometimes the mistake is not worth debugging)
 » Nice problems, thanks to the writers again.For D, I missed the simple solution in editorials and used a more complicated one instead.Problem E is a good practice for Dijkstra algorithm. Sadly, it costs me several TLEs, since I forgot that priority queue will put the "largest" value on top by default.As for F, I was very lucky since I almost immediately realized that it is about Huffman tree.I find that problem G is segment/interval dp, which is a very nice topic! But, I still can not fully understand the editorials. Would anyone like to talk about this problem in more details?By the way, I notice that many participants on the first page solve A-F within 15-20 minutes. This is crazy :D
•  » » 6 weeks ago, # ^ | ← Rev. 7 →   Problem G:Assume $a_1 = \infty$. For each node $a_j$ in the tree, consider the "brother" $a_i$ immediately on its left (if it exists), and draw a segment between $a_i$ and $a_j$ in the array $a$.You can prove that a configuration of segments is valid if and only if there are no pairs of partially overlapping segments (i.e., if two segments intersect, either one of them lies completely inside the other, or their intersection is a single point); if there is a segment that connects $i$ and $j$ ($i < j$), $a_i < a_j$ holds. Now let $dp_{i,j}$ be the number of ways to draw segments in the subarray $[i, j]$.There are $2$ cases: There are no segments from $i$ to $[i+1, j]$. So, the number of ways is $dp_{i+1,j}$. There is a segment from $i$ to some $k$ in $[i+1, j]$ (it's only possible if $a_i < a_k$). Then, you can still add segments in $[i+1, k-1]$ and $[k, j]$. So, for each $k$ the number of ways is $dp_{i+1,k-1} \cdot dp_{k,j}$. The answer is $dp_{1,n}$.
•  » » » There is a simpler way to think about this problemThe root is node 1, let's see what the first subtree in its children will look like then we can decide about the other onesWe know that it will be some consecutive element of $a$ starting from $a_2$, and $a_2$ being its root. Let's brute force the size of that subtree, let that be $k$.The first subtree will have the preorder $a[2 \dots k + 1]$, and the we have $a[k + 2 \dots n]$ for the rest of the subtrees.Now let $f(i, j)$ be the number of trees rooted at some $p < i$ and their preorder is $a[i \dots j]$, the answer to our problem is $f(2, n)$.Using all of this, when we are doing brute force on the size of the first subtree of the root's children, $k$, then the number of ways is $f(3, k + 1)f(k + 2, n)$.The only thing left is to follow the condition that the children of a node are visited in increasing order, this can be handled with a simple if (see implementation below for more details). Implementation#include using namespace std; const int N = 502; const int md = 998244353; int n, a[N], dp[N][N]; int sol(int i, int j) { if (i >= j) { return 1; } int& ret = dp[i][j]; if (ret != -1) { return ret; } ret = 0; for (int k = i; k <= j; k++) { if (k + 1 > j || a[i] < a[k + 1]) { ret += (long long) sol(i + 1, k) * sol(k + 1, j) % md; ret %= md; } } return ret; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } memset(dp, -1, sizeof dp); cout << sol(1, n - 1) << '\n'; return 0; } 
•  » » » Thank you so much for providing your idea. I think using only one dp is much simpler to handle, and the transformation of "valid configuration of segments" is very intuitive and helps a lot for understanding.I rememebr that there is a trick, which combines preorder of tree with segment tree. If we write down the preorder of tree, then any subtree will correspond to some consecutive segment in the segment tree.Maybe this problem gives me another hint that preorder of tree is related to segment dp as well.
•  » » By the way, I notice that many participants on the first page solve A-F within 15-20 minutes. This is crazy :D Maybe E, F, G are typical problems for these well-practised participants? :p (sadly I stucked in F for half an hour since that at first I think Huffman Tree is a wrong solution for this problem) My solution for problem GLet $f_{l,r}$ be the number of forests that pre-order is $a_{l\cdots r}$, and $g_{l,r}$ be the number of trees that pre-order is $a_{l\cdots r}$. Thus, the answer is $g_{1,n}$.Initally, $f_{i,i}=g_{i,i}=1(1\le i\le n)$.Let's enumerate each $[l,r]\in [1,n]$, then we have $g_{l,r}\leftarrow f_{l+1,r}$. (Let $l$ be the root of the tree.)As for $f_{l,r}$, initally $f_{l,r}\xleftarrow{+} f_{l+1,r}$ (a single tree can be a forest). Then, we enumerate $p$ as the root of other trees in the forest. So we have $f_{l,r}\xleftarrow{+} [a_l>n; for(int i=1;i<=n;i++) cin>>a[i],f[i][i]=g[i][i]=1; for(int d=2;d<=n;d++) for(int l=1,r=d;l<=n-d+1;l++,r++){ g[l][r]=f[l][r]=f[l+1][r]; for(int p=l+1;p<=r;p++) if(a[l] •  » » » Thank you so much for your kind reply. I will try to understand your solution.Hope that someday we could solve A-F within 20 mimutes as well :)  » In problem E ,can someone please provide the proof that minimum distance for any node is always obtainable. •  » » 6 weeks ago, # ^ | ← Rev. 7 → Dijkstra gives you$N-1$edges in the shortest path tree from city 1 to other cities. Path from i to j always exist,$M \geq N-1$(it is in the problem statement).$d_i$in the Dijkstra tree is the shortest path, therefore the sum of$d_i$is the minimum possible. •  » » » thanks  » 6 weeks ago, # | ← Rev. 2 → In editorial of F, proof part, He has defined C' twice and did not define C. . Can somebody define plz?UPD: C is cost of concatenating A1+A2, A3, ... , An •  » » 4 weeks ago, # ^ | ← Rev. 2 → Hey bro,do you know the meaning of$DX$of the second proof part? Does it mean "Depth of node x multiplies its weight"?If so,why can we construct such a tree with cost not greater than original tree?This part really confused me.:(  » 5 weeks ago, # | ← Rev. 2 → In the editorial of problem G, "If Vertex 0 has other vertices, and if the next smallest vertex is Vertex$A_k$, then Vertices are descendants of$A_l$, in which there are$dp[l+1][k]$ways to do so; on the other hand, there are$dp[k][r]$possible trees as a result of removing Vertex$A_l$and its descendants." What does "next smallest vertex" means? Also I don't understand the part$dp[l + 1][k] * dp[k][r]$. Isn't it suppose to be$dp[l + 1][k] * dp[k][r]$? •  » »$dp[l][r]$is the number of tree rooted at vertex$l$. We iterate over cutting vertex$k$for$a[l + 1] < a[k]$. Number of forest is$dp[k - 1][r]$. Therefore it contributes$dp[l + 1][k - 1] * dp[k - 1][r]$to$dp[l][r]$. Note that if you multiply it by$dp[k][r]$you are assuming vertex$l$only has only two children, subtree$[l, k - 1]$and subtree$[k, r]$. Instead, it shoud be subtree$[l, k - 1]$and forest$[k, r]\$.
•  » » » Thanks! That's exactly what I'm missing.
 » https://atcoder.jp/contests/abc252/submissions/31966974 This solution of E should give the wrong answer but passing the test for E. For test case:- 4 6 1 2 1 1 3 1 1 4 1 2 3 1 1 2 3 3 4 1 My solution gives 5 2 3 which is wrong as answer is 123
 » 5 weeks ago, # | ← Rev. 2 →   I solved problem E with dijkstra ,I didn't know concept of mst at that time.Is it solvable with mst ?? I just want to know that.Also if it works why does it work and if not why it doesnot work?
•  » » It is not solvable with mst. We want to reach every node as early as possible to make the sum of all distances minimum. This is exactly what dijkstra is doing.
 » For problem Ex Kth beautiful necklace, can someone explain the step 1 of editorial please. Specifically, I could not understand why we did not simply use AM GM inequality and get that the product of n_c = (N/C)^C