maroonrk's blog

ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168) Announcement
By maroonrk, history, 13 months ago, In English

We will hold ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168).

The point values will be 300-400-600-700-800-1100.

We are looking forward to your participation!

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

Comments Comments (6)
| Write comment?
»
13 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Wasn't able to solve D during the contest :(

https://atcoder.jp/contests/arc168/submissions/47766688

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Fellow programmers, Someone please explain Problem C (Change ABC string with k swaps), and Problem D (maximum number of times operations can chnage state of white squares to black). I went through editorial, solution of other people I didnot understand. Please explain it. Thanks.

And also how to practice nim game problems, it took me alot of time to solve problem B, good problem suggestions to understand the nim theory or grundy numbers? Thanks again.

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

As if we needed more evidence that listening to K-pop increases CP abilities

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

I know this is a quite old problem but I have a question regarding problem B editorial

It is mentioned in the last paragraph that

Let $$$M$$$ be the maximum value of $$$v$$$ for which $$$C_v$$$ is odd. If $$$k \ge M$$$, the condition is not satisfied

Why is that so? What is the proof that the xor sum will always be 0 for such case? And any example to demonstrate this?

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hi, I tried this problem yesterday but eventually had to look up at the editorial. Let me try to explain what I understood, correct me if I am wrong

    In nim game if the xor-sum is non-zero, first player always wins. So in this problem if xor-sum of array $$$A$$$ is non-zero, we have no maximum value for $$$k$$$. Here answer is $$$-1$$$.

    Now our xor-sum of array is equal to $$$0$$$.

    So, if $$$M = max(A_i), (1 \leq i \leq N)$$$ we should have $$$k \lt M$$$. As all values of $$$A_i \leq M$$$ taking any value of $$$k \geq M$$$ bob can always win according to the xor-sum strategy, Suppose alice takes any value of $$$x$$$ from $$$i$$$, array must have also present $$$x$$$ somewhere at $$$j$$$ for the xor-sum to be $$$0$$$.

    Lets say we have an array of two same integers $$$[B, B]$$$ no matter what $$$k$$$ we choose and currently alice has its move. If it takes $$$x, (1 \leq x \leq k)$$$ from one of the $$$B$$$, now bob will take $$$x$$$ from the other $$$B$$$ making array $$$[T, T], (T = B - x)$$$, It goes on until $$$T = 0$$$. So bob has always a winning strategy for an array if all its integers occurrence are even. So here answer is $$$0$$$.

    Now taking only those values for which there is odd occurrence in array, all are distinct and finding the maximum of those values say $$$M_2$$$ the answer is always $$$M_2 - 1$$$.

    Why?
    → Reply