maroonrk's blog

AtCoder Regular Contest 156 Announcement
By maroonrk, history, 21 month(s) ago, In English

We will hold AtCoder Regular Contest 156.

The point values will be 400-500-600-700-800-1000.

We are looking forward to your participation!

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

Comments Comments (36)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +23 Vote: I do not like it

I hope the problems of this contest have fewer corner cases.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +46 Vote: I do not like it

Amazing round.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

hope everyone get good rating

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing round.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +28 Vote: I do not like it

cpp 20 when

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

Good luck! (I still have $$$+\infty$$$ homework)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +47 Vote: I do not like it
  1. Thank you for the contest! Today I learned that Lucas's theorem works for multinomial coefficients too.
  2. Why in the first two problems N is large but for some reason in the third one it’s small? I was doubting whether my linear solution was correct for a long time…
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +77 Vote: I do not like it

    Probably you can not write checker in O(N) for the third?

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    2: Maybe it's because of the checker complexity.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +67 Vote: I do not like it

    I believe the checker for C is not easy when $$$N$$$ is large. (In fact, it's not obvious even for $$$O(N^2)$$$ time.)

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    My solution of C is $$$O(n^2)$$$.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve the problem B?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint 1:
    Hint 2:
    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Assume, the mex of the final set is $$$x$$$. In this case, all numbers less than $$$x$$$ are in set. The ones, that are not, have to be added. Assume, we added $$$y$$$ of such numbers.

    Now, we have to add $$$k - y$$$ more numbers. These are numbers from $$$0$$$ to $$$x - 1$$$. We are counting number of sets, so we have to "find number of non-decreasing arrays of length $$$k - y$$$ with elements from $$$0$$$ to $$$x - 1$$$". Now, not easy combinatorial step: we have to put $$$x - 1$$$ stages into $$$k - y + 1$$$ positions. This is number of "combinations with repetitions": $$$C_R(k - y + 1, x - 1)$$$. Rewrite as usual combinations: $$$C_R(a, b) = C(a + b - 1, a)$$$.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve C ?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    For an $$$x$$$, define $$$q_x$$$ as the number such that $$$p_{q_x}=x$$$.

    The minimum similarity has to be at least 1, as one can choose path $$$(x,q_x)$$$ to make it 1. So consider constructing a permutation that makes the answer 1.

    Let's consider a leaf $$$x$$$. If this node makes a contribution of 1 to the final answer, than the final path must contain path $$$(x,q_x)$$$. As $$$x$$$ is a leaf, $$$x$$$ will be the first element in the LCS. Then we only need to ensure that there is no other same element after $$$q_x$$$. One simple way to do this is to make $$$q_x$$$ the leaf. Then we get the idea to shuffle the indexes of the leaves. It's not hard to prove that if we do this, any LCS with a leaf will have length of at most 1.

    Then return to the original problem. Note that since leaves will not make any further contribution, we can simply delete them and do the same thing on the resulting tree again and again, until there's only 0/1 nodes left. Then we can do some trivial assignments and the whole process is finished. It can be proved that in this case, the answer is at most 1, which is obviously the best answer we can get.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

INF corner cases in A

B was good problem

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

anybody cares to explain problem B question not solution ?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +20 Vote: I do not like it

yet another weird screencast

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    :) Видео недоступно Оно содержит материалы партнера SME. Он заблокировал ролик в вашей стране из-за нарушения авторских прав.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did u find a test case on problem F where your code dosen t work, because i had WA on the same tests an was wondering where the mistake could be.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      It doesn't work on the second sample. I need to choose which elements to delete in trees more carefully, I don't yet know how exactly.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, is there a name for dp code in D? Is it some kind of trick for powers of 2?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The dp itself is ad-hoc here, it's not something standard. If you want to categorize it, I would say it is similar to knapsack, but it's not just textbook.

      The idea of the whole solution is from Lucas's theorem. I think that my solution is the same as the one in the editorial.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I read the editorial and understood the first part. And that we need to do a weird knapsack on 60 bits. But the dp itself is not obvious

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Linear time solution to E. It's nothing inspiring compared to a quadratic time solution, just beating up the quadratic code till it falls in place.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How does the computing of inverses modulo MOD work in this editorial precomputation?

inv.append(-inv[MOD % i] * (MOD // i) % MOD)

Where does this equation inv(x) mod MOD = -inv(MOD mod x) * floor(MOD/x) mod MOD come from?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone explain the editorial solution for problem D? It would be of great help...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the problem F can be solve in $$$O(n\sqrt{n})$$$ time.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wander how to write the code that judges the solution for C.

→ Reply