chokudai's blog

By chokudai, history, 6 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +65
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

interesting thanks for sharing the contest

»
6 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

C++20 when

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

wasnt problem E a minimum spanning tree problem.

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

D can also be solved with DP: Solution

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone plz tell why my solution for E is failing? I used dijsktras algo only

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

»
6 weeks ago, # |
Rev. 4   Vote: I like it +14 Vote: I do not like it
F regret

Apparently tourist had the same problem, it costs him 1 minute to fix (orz).

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know why PyPy3 gives runtime error but Python does not (and passes)?

https://atcoder.jp/contests/abc252/submissions/31857332

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably because math.comb is a Python 3.8 feature.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please check why my dijsktra is failing on E: https://atcoder.jp/contests/abc252/submissions/31874731

In 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 reject

PS: 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?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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)

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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   Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      There is a simpler way to think about this problem

      The root is node 1, let's see what the first subtree in its children will look like then we can decide about the other ones

      We 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
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 G
    My Code for Problem G
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E ,can someone please provide the proof that minimum distance for any node is always obtainable.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 7   Vote: I like it +1 Vote: I do not like it

    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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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