Блог пользователя maroonrk

Автор maroonrk, история, 2 года назад, По-английски

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!

  • Проголосовать: нравится
  • +128
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится

problem A was terrible

»
2 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +56 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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]

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +68 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

C and D are really great problems!

»
2 года назад, # |
Rev. 6   Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Problem C was very nice!

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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"?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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,

»
2 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

C was such a genius problem.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?