atcoder_official's blog

AtCoder Beginner Contest 336 Announcement
By atcoder_official, history, 10 months ago, In English

We will hold AtCoder Beginner Contest 336.

We are looking forward to your participation!

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

»
10 months ago, # |
  Vote: I like it +14 Vote: I do not like it

After the contest ends, I will be live discussing soln of ABC 336

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

Hope to solve:A,B,C,D!

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

First round of ATcoder

Hope to get A,B,C,D,E.

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

Hope to solve:A,B,C,D,E!

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

E>500 Round? Hope not as hard as 332.

→ Reply
»
10 months ago, # |
  Vote: I like it +2 Vote: I do not like it

D&F too hard.

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

Funny B solution

→ Reply
»
10 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Problem E is exactly the same as LUOGU P4127

And it seems that the first solver just copied his code from his luogu submission...

I have checked that the code is exactly the same, lol...

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Are you a multi-account of sunkuangzheng bro :(

    Both of your submissions start with

    /**
 *    author: sunkuangzheng
 *    created: xxxxxx
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
debug_helper deg;
#endif

    even without changing the author name...

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

      I suspect you're also a multi-account of sunkuangzheng :(

      Most of your submissions start with the following code:

      /**
 *    author: sunkuangzheng
 *    created: xxxxxx
**/

      Moreover, in the introduction of the Luogu account _sunkuangzheng_, it's mentioned that both tril0713 and little_dog belong to him.

      Hint: Due to policy restrictions, you can't directly access the Luogu user's introduction. However, you can observe in the HTML code of the page that there are references to <a href="https://codeforces.net/profile/little_dog"> & <a href="https://codeforces.net/profile/tril0713">.

      → Reply
»
10 months ago, # |
  Vote: I like it +29 Vote: I do not like it

I guess, in problem G we have to calculate number of Euler paths. How to do it? The graph looks specific, do we need to use this fact?

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    BEST theorem can solve the Euler path counting problem.

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

      Kirchhoff's theorem?

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
        ← Rev. 2   Vote: I like it +15 Vote: I do not like it

        Not entirely.You can see it in this.

        → Reply
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it +20 Vote: I do not like it

          Wow, the number of Euler cycles is $$$ST \cdot \Pi_v{(din_v - 1)!}$$$, where $$$ST$$$ is number of spanning trees in graph, and $$$din$$$ is degree-in.

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

I wonder if G is a inclusion-exclusion problem lol, I'm looking for some ideas.

→ Reply
»
10 months ago, # |
  Vote: I like it +8 Vote: I do not like it

E (:

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

How to write check function for D optimally?

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

    I did it using segment tree but there must be a better approach

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

      The best solution is O(n).

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

      I am the same, even though time is not excellent

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

      How segment tree? can u pls share

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Code
        → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      No need for segment tree, it can be solved with basic prefix and suffix dp, Here is the code- Link.

      → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    For the prefix- suffix dp solution we have to observe that the Pyramid will only increase by 1 else it will be the minimum (length of the previous Pyramid, current point). 49307707

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

E has the same problem in Luogu,even harder than E

https://www.luogu.com.cn/problem/P4127

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

F seems to be a search, but I don't have enough time to complete it:（

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

    I do think F is IDA*, but I can't construct the evalueat function.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      No, it's just a Meet-in-the-middle :)

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

      I also thought that, and I have a evalueat function but it's too hard to write. Then I gave it up.

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

Even C is easily available at the internet

Atcoder Copy paste round.

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

Copycoder

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

Can D be done using bin search??

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

    yes but check function need a quick way to find min in a range in less than $$$O(N)$$$.

    I used sparse table and sliding window approach. (submission)

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

      Mind explaining your solution in a bit detail.

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

        sure, so in the sliding window, we need to quickly check if a range is strictly increasing or decreasing which helps us to know about (strict) bitonic sequence. Let's solve for checking a range is increasing or not (the reverse can find the decreasing). For each index we subtract it's index which maintains the strictness condition which helps us to check increasing nature by just finding any minimum element which is negative.

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

          Explain E

          → Reply
          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            It's a straightforward digit dp problem. The only thing that might mess up is the sum of digits which needed to have a remainder state beforehand. So we will iterate over all possible digit sums and do normal digit dp (finding no of element less than or equal to N with a remainder with the current value as 0 and sum as current value). submission

            → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      My binary search solution used a $$$O(n)$$$ greedy check function. You start at index 1 and start trying to build up your pyramid. Assume that you're at index $$$i$$$ and up to index $$$i - 1$$$ you were able to build up your pyramid with no problems. Let $$$H$$$ be the height needed to continue building up our pyramid at this point. If $$$A_i$$$ is greater than or equal to $$$H$$$, you just move on to index $$$i + 1$$$, and update $$$H$$$ to $$$H + 1$$$ or $$$H - 1$$$ depending on if we're going up or down currently; if it's smaller than $$$H$$$, we failed and we should try starting building up another pyramid. However, by our hypthosesis, we were able to build a pyramid with height at least $$$H - 1$$$ at index $$$i - 1$$$, and since $$$H - 1 \geq A_i$$$, we have the guarantee that we could've built a pyramid with height $$$A_i$$$ at index $$$i$$$, so just move on to index $$$i + 1$$$ and $$$H := A_i + 1$$$ (making sure we're going up).

      → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    yo , check function is just greedy https://atcoder.jp/contests/abc336/submissions/49319491 iterate the array from beginning and set a value $$$p$$$=1 , if $$$v[i] \ge p$$$ increase p by 1 if $$$p<mid$$$ and $$$p$$$ hasn't reached mid yet else decrease p by 1 and if $$$v_i<p$$$ set $$$p=v_i+1 $$$assuming it has just reached mid or never reached mid if new $$$p<mid$$$ , if $$$p$$$ ever reaches 1 after reaching mid check function returns $$$true$$$

    → Reply
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Please , do release english editorial as well...

→ Reply
»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

F is too classic imo, from the constraint you can easily observe a meet-in-the-middle solution. idk why so few people passed it.

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

how to solve E to not fit in 5000ms?

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

I had the same idea for E , but was going from lower digits , and hence was stuck on how to handle <= N constraint.

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

Passed F doing a double BFS from original grid and from target grid (max depth 10), and joining the states using a map.

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Two problems were directly available in different sites Problem-C and Problem-E

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

my lambda style digit dp in E

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

why there isn't a editorial in English.. (T⌓T)

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

For problem E, I use dp[i][j][k][r][0/1] to denote the number of ways such that, i denotes that we have determined the first i digits(from high to low), and j denotes that the sum of the first i digits is j, while k and r denote that the current integer module k is r, and finally 1/0 denotes that we have arrived at the upper bound or not.

The final answer is dp[len][j][j][0][0]+dp[len][j][j][0][1], where len denotes the number of digits in n.

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

+1

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

+1

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

thanks a lot i had no idea of C

→ Reply