atcoder_official's blog

AtCoder Beginner Contest 336 Announcement
By atcoder_official, history, 2 years 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

Comments Comments (60)
| Write comment?
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

First round of ATcoder

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Funny B solution

→ Reply
»
2 years ago, hide # |
 
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
  • »
    »
    2 years ago, hide # ^ |
     
    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
    • »
      »
      »
      2 years ago, hide # ^ |
       
      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://mirror.codeforces.com/profile/little_dog"> & <a href="https://mirror.codeforces.com/profile/tril0713">.

      → Reply
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

E (:

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to write check function for D optimally?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    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
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      The best solution is O(n).

      → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      How segment tree? can u pls share

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it
        Code
        → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      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
  • »
    »
    2 years ago, hide # ^ |
    ← 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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Even C is easily available at the internet

Atcoder Copy paste round.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

Copycoder

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can D be done using bin search??

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    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
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Mind explaining your solution in a bit detail.

      → Reply
      • »
        »
        »
        »
        2 years ago, hide # ^ |
         
        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
    • »
      »
      »
      2 years ago, hide # ^ |
      ← 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
  • »
    »
    2 years ago, hide # ^ |
    ← 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 \lt mid$$$ and $$$p$$$ hasn't reached mid yet else decrease p by 1 and if $$$v_i \lt p$$$ set $$$p=v_i+1 $$$assuming it has just reached mid or never reached mid if new $$$p \lt mid$$$ , if $$$p$$$ ever reaches 1 after reaching mid check function returns $$$true$$$

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Please , do release english editorial as well...

→ Reply
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +5 Vote: I do not like it

how to solve E to not fit in 5000ms?

→ Reply
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

my lambda style digit dp in E

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
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