maroonrk's blog

Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138）Announcement
By maroonrk, history, 3 years ago, In English

We will hold Daiwa Securities Co. Ltd. Programming Contest 2022 Spring（AtCoder Regular Contest 138）.

The point values will be 400-500-600-700-1000-1000.

We are looking forward to your participation!

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

Comments Comments (39)
| Write comment?
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

thanks for leaving $$$N=K=1$$$ as a testcase in D

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

    I failed on that case, too. (38 ACs and 1 WA

    → Reply
»
3 years ago, # |
  Vote: I like it +167 Vote: I do not like it

Remind me why ARCs are not rated for 2800+?

→ Reply
»
3 years ago, # |
  Vote: I like it +126 Vote: I do not like it

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...

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

I find B easier than A

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

    Same, C was also really nice

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

    Could you please explain B solution?

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

      You can check my video editorial of A and B if you have any confusion

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 6   Vote: I like it +18 Vote: I do not like it

      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)

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

Im painful. Anyone can tell me about just one WA TC? Submission

→ Reply
»
3 years ago, # |
  Vote: I like it +72 Vote: I do not like it

Problem D appeared last year on Luogu Monthly Contest. Fun fact, the writer participated in this contest.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Also it can be solved by doing a naive DFS. We can't prove that, but it got AC.

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

      Someone had proved it in Luogu Discuss。

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

        Well, I don't understand very clearly.

        So I still can't figure out why dfs is right.

        → Reply
»
3 years ago, # |
  Vote: I like it +109 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

What is basis in Editorial of D?

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Note that problem D is same with a problem on a Chinese online judge.

link:https://www.luogu.com.cn/problem/P7949

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

    Actually, you can copy the solution and change the 01into a Yes No.

    Then you can get it accepted.

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

D is a famous problem and you can get the solution on a Chinese online judge. Many Chinese coder pass this problem quickly lol

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks for task D Rolling_Code.

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

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.

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

fun contest

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

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 :)

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

I have hard time understanding the editorial for problem B. Can somebody explain?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

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

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.

→ Reply