### atcoder_official's blog

By atcoder_official, history, 4 months ago,

We will hold AtCoder Beginner Contest 336.

We are looking forward to your participation!

• +72

 » 4 months ago, # |   +14 After the contest ends, I will be live discussing soln of ABC 336
 » 4 months ago, # |   0 Hope to solve:A,B,C,D!
•  » » 4 months ago, # ^ |   0 Me too!
•  » » 4 months ago, # ^ |   +5 Hope to solve:A,B,C,D,E!
•  » » » 4 months ago, # ^ |   0 +1
•  » » » 4 months ago, # ^ |   -8 C is hard!!!!
•  » » » » 4 months ago, # ^ |   0 yesss
•  » » » » 4 months ago, # ^ |   +1 Prob C is not but D is!
•  » » » » » 4 months ago, # ^ |   0 how C???
•  » » » » » » 4 months ago, # ^ |   0 create array g with values [0,2,4,6,8], read n, n--, create empty array r, for (n>0) { r.push_back(g[n%5]); n/=5 }, print r from end
•  » » » » » » » 4 months ago, # ^ |   -10 You CANT tell another people the Solution!!! This is violation of competition rules!!!!!!
•  » » » » » » » » 4 months ago, # ^ | ← Rev. 3 →   0 competition ended over 3 weeks ago, now study time
•  » » » » » » » » » 6 weeks ago, # ^ |   0 OH,sorry...
•  » » » » » » 4 months ago, # ^ |   0 convert n to base 5 and multiply by 2
•  » » » 4 months ago, # ^ |   0 Reality: A, B, C.
 » 4 months ago, # |   0 First round of ATcoderHope to get A,B,C,D,E.
 » 4 months ago, # |   0 Hope to solve:A,B,C,D,E!
 » 4 months ago, # |   0 E>500 Round? Hope not as hard as 332.
 » 4 months ago, # |   +2 D&F too hard.
 » 4 months ago, # |   0
•  » » 4 months ago, # ^ |   +5 Or just use CTZ :P.
 » 4 months ago, # |   +21 Problem E is exactly the same as LUOGU P4127And 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...
•  » » 4 months ago, # ^ |   +18 Are you a multi-account of sunkuangzheng bro :(Both of your submissions start with /** * author: sunkuangzheng * created: xxxxxx **/ #include #ifdef DEBUG_LOCAL #include debug_helper deg; #endif even without changing the author name...
•  » » » 3 months ago, # ^ |   0 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  & .
 » 4 months ago, # |   +29 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?
•  » » 4 months ago, # ^ |   +24 BEST theorem can solve the Euler path counting problem.
•  » » » 4 months ago, # ^ |   0 Kirchhoff's theorem?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +15 Not entirely.You can see it in this.
•  » » » » » 4 months ago, # ^ |   +20 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.
 » 4 months ago, # |   0 I wonder if G is a inclusion-exclusion problem lol, I'm looking for some ideas.
 » 4 months ago, # |   +8 E (:
 » 4 months ago, # |   0 How to write check function for D optimally?
•  » » 4 months ago, # ^ |   0 I did it using segment tree but there must be a better approach
•  » » » 4 months ago, # ^ |   0 The best solution is O(n).
•  » » » 4 months ago, # ^ |   0 I am the same, even though time is not excellent
•  » » » 4 months ago, # ^ |   0 How segment tree? can u pls share
•  » » » » 4 months ago, # ^ |   0 Codebool check(vector&a,int peak){ int n=a.size(); vectortmp(n,1); segtree st; st.build(tmp); for(int i=0;i=peak){ return true; } } return false; } 
•  » » » 4 months ago, # ^ |   +1 No need for segment tree, it can be solved with basic prefix and suffix dp, Here is the code- Link.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 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
 » 4 months ago, # |   0 E has the same problem in Luogu,even harder than Ehttps://www.luogu.com.cn/problem/P4127
 » 4 months ago, # |   0 F seems to be a search, but I don't have enough time to complete it:（
•  » » 4 months ago, # ^ |   0 I do think F is IDA*, but I can't construct the evalueat function.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +5 No, it's just a Meet-in-the-middle :)
•  » » » 4 months ago, # ^ |   0 I also thought that, and I have a evalueat function but it's too hard to write. Then I gave it up.
 » 4 months ago, # |   0 Even C is easily available at the internetAtcoder Copy paste round.
 » 4 months ago, # |   -9 Copycoder
 » 4 months ago, # |   0 Can D be done using bin search??
•  » » 4 months ago, # ^ |   0 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)
•  » » » 4 months ago, # ^ |   0 Mind explaining your solution in a bit detail.
•  » » » » 4 months ago, # ^ |   0 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.
•  » » » » » 4 months ago, # ^ |   0 Explain E
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » » » 4 months ago, # ^ |   0 okay
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +1 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).
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 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
 » 4 months ago, # |   +1 Please , do release english editorial as well...
 » 4 months ago, # |   +5 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.
 » 4 months ago, # | ← Rev. 2 →   +5 how to solve E to not fit in 5000ms?
•  » » 4 months ago, # ^ |   0 <200ms here
•  » » 4 months ago, # ^ |   0
•  » » » 4 months ago, # ^ |   0 :) it is TLE, I need solution
•  » » » » 4 months ago, # ^ |   0 Same algorithm in c++ takes < 200ms Code I believe this is the reason for very high TL (10s).
 » 4 months ago, # |   0 I had the same idea for E , but was going from lower digits , and hence was stuck on how to handle <= N constraint.
 » 4 months ago, # |   0 Passed F doing a double BFS from original grid and from target grid (max depth 10), and joining the states using a map.
 » 4 months ago, # | ← Rev. 2 →   0 Two problems were directly available in different sites Problem-C and Problem-E
•  » » 4 months ago, # ^ |   0 thanks a lot i had no idea of C
 » 4 months ago, # |   0
 » 4 months ago, # |   0 why there isn't a editorial in English.. (T⌓T)
 » 4 months ago, # |   0 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.
 » 4 months ago, # |   0 +1
 » 4 months ago, # |   0 +1
 » 4 months ago, # |   0 thanks a lot i had no idea of C