We will hold ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168).
- Contest URL: https://atcoder.jp/contests/arc168
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20231119T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: maroonrk
- Tester: maspy, potato167
- Rated range: — 2799
The point values will be 300-400-600-700-800-1100.
We are looking forward to your participation!
Wasn't able to solve D during the contest :(
https://atcoder.jp/contests/arc168/submissions/47766688
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.
Sprague grundy theorem
As if we needed more evidence that listening to K-pop increases CP abilities
Can't D be done greedily by picking up ranges of minimum length.Using segment tree of some shit
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
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?
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$$$.
$$$Case 1:$$$ If $$$M_2 - 1$$$ is not present. Alice can always take $$$M_2 - 1$$$ from $$$M_2$$$ and Bob cannot choose a value such that the new xor-sum can be $$$0$$$ as currently all value are less than $$$M_2 - 1$$$.
$$$Case 2:$$$ If $$$M_2 - 1$$$ is present. Alice will always take $$$1$$$ from $$$M_2 - 1$$$ making it $$$M_2 - 2$$$ and now all values are less than or equal to $$$M_2 - 2$$$ except $$$M_2$$$, As bob has to take $$$1$$$ for xor-sum to be $$$0$$$ in next move.
If bob takes $$$1$$$ from $$$M_2$$$, next time alice will take it and bob cannot choose any other $$$M_2 - 1$$$ as currently all are less than or equal to $$$M_2 - 2$$$ otherwise if bob takes $$$1$$$ from any other value less than $$$ M_2$$$ then alice can use $$$Case 1$$$.