lol, this is ABC250 submission!

Shortest paths actually

This line of thinking costs me 1 WA

You forgot that edges are bidirectional. Also your Dijkstra is slow, because you visit the same node multiple times.

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.

Probably because math.comb is a Python 3.8 feature.

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)

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}$$$.

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)

	cin>>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]<a[p])
					f[l][r]=(f[l][r]+g[l][p-1]*f[p][r]%MOD)%MOD;
		}
	cout<<g[1][n]<<"\n";

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.

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.:(

$$$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]$$$.

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.