We will hold Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138）.
- Contest URL: https://atcoder.jp/contests/arc138
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220409T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: maroonrk
- Tester: maspy, satashun
- Rated range: — 2799
The point values will be 400-500-600-700-1000-1000.
We are looking forward to your participation!
thanks for leaving $$$N=K=1$$$ as a testcase in D
I failed on that case, too. (38 ACs and 1 WA
Remind me why ARCs are not rated for 2800+?
Nice problems, but I am not sure if putting problems like EF in ARC is even reasonable if there are $$$5$$$ and $$$2$$$ ACs in the end...
Interesting fact: since 2021, maroonrk has authored $$$8$$$ ARCs and $$$1$$$ AGC alone, has coauthored $$$3$$$ ARCs and $$$1$$$ AGC, and wrote an entire OpenCup set (and there may be many more I am not aware of). How to be so productive...
I find B easier than A
Same, C was also really nice
Could you please explain B solution?
You can check my video editorial of A and B if you have any confusion
B solution that may be easier than editorial solution:
First, consider the problem in reversed time (so you start with the given array and want to reduce it to empty. Op A is "remove first element, which must be 0, then flip remaining elements", op B is "remove last element, which must be 0")
Notice that op B should always be done if possible. That's because if op B is possible, doing some number of op A first would either make it not possible anymore, or simply make it possible again, and then performing op B then would just put you in the same position as if you did op B before those ops A. The operation choice is now deterministic and can be easily tried by simulation (using a parity bit to emulate flipping the array, or just notice that it's equal to the parity of your left-pointer)
Im painful. Anyone can tell me about just one WA TC? Submission
Problem D appeared last year on Luogu Monthly Contest. Fun fact, the writer participated in this contest.
Also it can be solved by doing a naive DFS. We can't prove that, but it got AC.
Someone had proved it in Luogu Discuss。
Well, I don't understand very clearly.
So I still can't figure out why dfs is right.
Thanks for participating! I didn't intend to make ARC this challenging, but E and F were much harder than I thought.
BTW, is D known in China?
D is same as a Chinese contest's problem
task D appeared in luogu contest last year :https://www.luogu.com.cn/contest/55488
this problem
When you translate it into Japanese you'll find that THEY ARE EXACTLY SAME
Here is the author Rolling_Code >_<
Well, I was the writer:(
It is the same problem as a Chinese contest's div1 A/div2 C.
The same problem also appeared in IZhO 2019.
Link
\abcorz/
E and F are very good and interesting. Thank you for these problems. I like them very much!
They are better than polynomial problems lol.In fact E can become a polynomial problem by changing n to $$$10^5$$$.
What is basis in Editorial of D?
OK, it is some kind of linear algebra.
Here is great tutorial on xor basis: https://mirror.codeforces.com/blog/entry/68953.
I used it's implementation to find basis and solve the problem: https://atcoder.jp/contests/arc138/submissions/30920108
Thanks for detailed tutorial.
Note that problem D is same with a problem on a Chinese online judge.
link:https://www.luogu.com.cn/problem/P7949
Actually, you can copy the solution and change the
01into aYes No.Then you can get it accepted.
D is a famous problem and you can get the solution on a Chinese online judge. Many Chinese coder pass this problem quickly lol
Thanks for task D Rolling_Code.
Change your name now!!!!!!!
Problem A&B is much easier than before,and problem D appeared on luogu,a Chinese online judge.It's surprising that there are 16 Chinese contestants in the top 20.
fun contest
The idea behind problem C is so wonderful! I never tried to guess that we are always able to get the maximum N/2 values. Moreover, the trick of proving this fact and construction is also amazing, really beyond my imagination. Problem writer has done a great job, thank you :)
I have hard time understanding the editorial for problem B. Can somebody explain?
For B, I used deque as the data structure because I planned to both pop in the front and pop at the back of the deque. In the beginning, I kept popping '0' at the back of the deque until I cannot. Then I check if the front of the deque is '0' and if so, I pop_front() and then flip the remaining deque. Otherwise, the front of the deque is '1', return 'No'. I keep doing the above until the deque is empty. If I can reach empty deque, the answer is yes. The above is the brute force way. It will TLE. Therefore, make a boolean flag to record the current state is flipped or not. Then there is no need to flip the deque. Based on the current state of flip, we treat '0' as '0' or treat '0' as '1' and '1' as '0'. Then, there will be no TLE.
In this contest I registered unrated and I didn't have any submission. Why this contest still rated for me
?. link. maroonrk Pls check. Thanks u.