maroonrk's blog

AtCoder Regular Contest 141 Announcement
By maroonrk, history, 2 years ago, In English

We will hold AtCoder Regular Contest 141.

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

We are looking forward to your participation!

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

Comments Comments (25)
| Write comment?
»
2 years ago, # |
  Vote: I like it -41 Vote: I do not like it

problem A was terrible

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

    i think so

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

    The sample is really weak :(

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

      Mine passed samples, but failed all system tests XD

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it
        It took me 40 mins to find this edge case
        → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Couldn't agree more

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

Me after reading problem A -
"Why did I register as rated?"

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

Feel honored that problem B is similar to my probelm in Codeforces: 1329B - Dreamoon Likes Sequences. :)

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

    lol, I solved it 2 years ago with a sane DP, today I solved it with Matrix Exponentiation.

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

How to solve B?

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

    The mst of Ai must be greater than the previous value. Thus the maximum possible length will be atmost 60. Rest it can be solved using 2d dp.

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

    I think the main idea to solve B is that if the xor of your prefix have k bit then the next element can't not only have k bit because the k-th bit will be appear even number of time which make the xor small than previous, also the a[i] have to be greater than a[i-1] so you can't not use less than k bit -> a[i] has to have more bit than a[i-1]

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

More and more ARC T1 can't solve, what should I do?

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

Submit A for so many times but still can't solve it..

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

Very nice problems, thanks! F is a bit nasty to implement, but the idea behind the solution is nice nonetheless.

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

C and D are really great problems!

→ Reply
»
2 years ago, # |
← Rev. 6   Vote: I like it +1 Vote: I do not like it

I don't understand why my Problem A failed at first. I think I did the same the editorial says. I looked at the first $$$k$$$ digits of $$$N$$$, call them $$$N'$$$. Then I concatenated $$$N'$$$ first and then $$$N'-1$$$ to create periodic numbers and checked which one was the biggest. This failed for me.

Then in a rush I randomly tried adding $$$N'-2$$$ to the checks and it passed.

Can someone enlighten me what I did wrong or find an counterexample for my first solution and esp. why adding $$$N'-2$$$ makes it pass? I was clueless duting the contest and I still am and assume some form of error in the implementation...

Edit: Oh dear, got it: Testcase $$$11001$$$ breaks it. $$$9999$$$ will never be checked and it will output $$$1111$$$ as answer. Adding $$$N'-2$$$ to checks, adds "accidently" a check for $$$9999$$$ with $$$11-2=9$$$. I guess this is explicitly what the last paragraph of the editorial warns about.

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

    I did $$$N'$$$ and $$$N' - 1$$$, and initially set ans to 99.... .

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

Problem C was very nice!

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

I didn't understand the editorial for D, can someone explain? Are there any resources to read the "typical problem of choosing such k by getting upper limit and lower limit"?

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

    Did you get some related resources? Would be nice if you can share them.

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

Nice problems, thanks to writers and testers.

For problem A, somehow I realized the solution quickly and also noticed the special case 999...9, and feel lucky to get AC with only one try.

Problem B needs some observation that it is sufficient to deal with N up to about 60. Then, if you are familiar with problems, like, longest increasing subsequence, maximum sum of substring, then one could come up with dp, with a classic definition of state, dp[end at index i][if the i-th index has value j]=the number of possible sequences.

Finally, I spent a lot of time on problem C, but, have to end up with nothing. I think this problem really needs quite deep observation and strong logics to reach the conclusion. Would anyone like to share your solution, or your ideas about this problem :)

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

For A, I wasted a few WAs by directly comparing strings instead of first converting strings to long longs then compare.

In particular, string "999" is > string "1010" when compared as strings. Lesson learned,

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

C was such a genius problem.

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

The editorial for problem C wrote:

For simplicity, we consider the case S is a correct parenthesis sequence or its reversal. The general case can be proved in the same way, using the fact that a general S can be represented as the concatenation of correct parenthesis sequences and their reversals.

I can understand the case when S is a correct parenthesis sequence or its reversal. But how to prove the general case？

→ Reply