We will hold AtCoder Beginner Contest 336.
- Contest URL: https://atcoder.jp/contests/abc336
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240114T2100&p1=248
- Duration: 100 minutes
- Writer: Nyaan, math957963
- Tester: nok0, yuto1115
- Rated range: ~ 1999
- The point values: 100-200-300-400-525-550-650
We are looking forward to your participation!
After the contest ends, I will be live discussing soln of ABC 336
Hope to solve:A,B,C,D!
Me too!
Hope to solve:A,B,C,D,E!
+1
C is hard!!!!
yesss
Prob C is not but D is!
how C???
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
You CANT tell another people the Solution!!! This is violation of competition rules!!!!!!
competition ended over 3 weeks ago, now study time
OH,sorry...
convert n to base 5 and multiply by 2
Reality: A, B, C.
First round of ATcoder
Hope to get A,B,C,D,E.
Hope to solve:A,B,C,D,E!
E>500 Round? Hope not as hard as 332.
D&F too hard.
Funny B solution
Or just use CTZ :P.
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...
Are you a multi-account of sunkuangzheng bro :(
Both of your submissions start with
even without changing the author name...
I suspect you're also a multi-account of sunkuangzheng :(
Most of your submissions start with the following code:
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">.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?
BEST theorem can solve the Euler path counting problem.
Kirchhoff's theorem?
Not entirely.You can see it in this.
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.
I wonder if G is a inclusion-exclusion problem lol, I'm looking for some ideas.
E (:
How to write check function for D optimally?
I did it using segment tree but there must be a better approach
The best solution is O(n).
I am the same, even though time is not excellent
How segment tree? can u pls share
No need for segment tree, it can be solved with basic prefix and suffix dp, Here is the code- Link.
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
E has the same problem in Luogu,even harder than E
https://www.luogu.com.cn/problem/P4127
F seems to be a search, but I don't have enough time to complete it:（
I do think F is IDA*, but I can't construct the evalueat function.
No, it's just a Meet-in-the-middle :)
I also thought that, and I have a evalueat function but it's too hard to write. Then I gave it up.
Even C is easily available at the internet
Atcoder Copy paste round.
Copycoder
Can D be done using bin search??
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)
Mind explaining your solution in a bit detail.
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.
Explain E
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
okay
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).
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$$$
Please , do release english editorial as well...
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.
how to solve E to not fit in 5000ms?
<200ms here
Code in python
:)it is TLE, I need solutionJust look at any AC code in python
Same algorithm in c++ takes < 200ms Code
I believe this is the reason for very high TL (10s).
I had the same idea for E , but was going from lower digits , and hence was stuck on how to handle <= N constraint.
Passed F doing a double BFS from original grid and from target grid (max depth 10), and joining the states using a map.
Two problems were directly available in different sites Problem-C and Problem-E
thanks a lot i had no idea of C
my lambda style digit dp in E
why there isn't a editorial in English.. (T⌓T)
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.
+1
+1
thanks a lot i had no idea of C