umm... No?

What you didn't wanted has come true, how do you feel?

Turned out true

LOL, this is me being a bit too self-conscious. I've tested maybe 10 rounds by this point and I can only remember recommending participation for one (https://codeforces.net/blog/entry/76777?#comment-613771 ), as I feel that testers recommending every contest feels insincere (not every round can be the best round ever, you know?)

But then I think people might read too much into me not saying anything, so probably just never saying anything is better, and I thought it would be best to announce this to the world.

I think the contest is great, a little challenging but not too adhoc.

I thought E was very cool and none of the other problems looked particularly bad to me, but there was a very large amount of "guessforces" involved in A-D and I thought that would be a bit offputting.

• A: I guessed separating positive and negative values would work. It was A so I didn't prove it.
• B: I copied the idea of the second sample (swap first B with last N), submitted, didn't prove it either.
• C: I actually solved this one legit as I like game theory problems, and think the perspective change idea is simple but cute. But I wondered how many people would write a bruteforce and guess from that instead.
• D: I essentially started this one by guessing again: "This operation looks OP, I think answer <= 2". And it's easy to notice if length is even you can only affect one of a[l] and a[r] in one move, so it's possible to do in 2 moves iff you can zero either a[l] or a[r] in one move. As it turns out, my initial guess was correct and this condition for 2 moves also applies for the general case.
• E: Very cool problem. There are many wrong paths to choose here (for example, trying to do some inclusion-exclusion is unlikely to work, but it almost works), and this can be either impossible if you get stuck in one of those paths, or very easy if you see the intended counting method quickly.

no.

That's just nested Binary search, adamant had wrote some blog on nested ternary search or smth.

I love any problem contains alice and bob most of them are very hard and take much of thinking.

Huh, and here I thought thinking and stimulating your brain was the point of CP

It requires taking lot of examples and finding which one gives answer

1)taking parity of minimum or parity of array length ? or parity of total sum ? or is it parity of some other thing like parity sum-(n-1) ?

I am bad at solving problems which require a lot of case work and I thought this problem was one of that kind

orz, I could not figure it out for 2 hours straight lol, I'm so terrible

I agree, the idea seems nice.

The element that Alice chooses is the element that Bob has to check for 0 and decrements in the next turn, and the element that Bob chooses is the element that Alice has to check for 0 and decrements in the next turn. Furthermore, the element Alice chooses is guaranteed to be outside index 1 when it's her next turn, and likewise, the element Bob decrements is guaranteed to be outside index 1 when it's his next turn.

Therefore, the fastest way to get an element to 0 is to always pick the same element (and this is guaranteed to always be available). Specifically, it should be the smallest element available to them, since they want to have decremented to 0 first.

Let's refer to the first element of the initial array as $$$x$$$. Alice should pick the smallest element available to her, which is the minimum of all elements except $$$x$$$. Let's say this element is $$$y$$$.

What can Bob do? Everything except $$$x$$$ and $$$y$$$ was originally $$$\geq y$$$ and would now be $$$> y$$$ when it's Bob's turn to choose, so Alice would win this race if Bob picks any of these. Bob cannot pick $$$y$$$, because Alice claimed it. So Bob's only possible hope of victory is to pick $$$x$$$. If, at the original array, $$$y \geq x$$$, then Bob wins. Even when they're equal, Alice has to decrement $$$x$$$ before performing the swap, so Bob wins that race.

Overall, the solution is very simple: find $$$y$$$ as the minimum of all elements except the first element ($$$x$$$). If $$$y \geq x$$$, Bob wins. Otherwise, Alice wins.

if you have the first turn you can always force the opponent to decrease the minimum element from the array. How? It's easy, just move the minimum element to the a[0], now your opponent is forced to decrease the a[0] and swap, and you just repeat and force him again. However, if the minimum element is already at a[0] then you are doomed because your opponent will beat you with the same strategy

Here is my complete logic: Is 1 showing up somewhere? If showing up as a1, then Bob will always win. Why? Because after Alice operation, a1 will be 0 and swap with ai. So Bob can always take this 0 back to a1 in the next step. So Alice lose. Else if showing up as a2/a3…, then Alice will always win. Why? Because after Alice operation, she can take 1 as new a1, then following the first half of this paragraph, Bob will lose.Now what if 1 is not showing up? Let’s focus on 2. If showing up at a1, then we know after Alice operation, ai will become 1, then following the logic from step1, Bob will always win. Else if showing up at a2/a3…, following the logic from step1, Alice will always win. …we can observe that the location of the smallest value matters: if at a1, then Bob win, otherwise, Alice win.

That's cool! I use similar approach to solve game theory problems, writing small states as winning or losing helps a lot and usually the winning/losing strategy hidden becomes obvious :)

You have a nice explanation. I finally understand the problem! Thank you!

thank you guy

oh wow

Use prefix xor-sum.Note $$$XOR[i]=a[1]⊕a[2]⊕...⊕a[i]$$$.

We just find $$$x$$$,which makes $$$XOR[x]==XOR[l-1]$$$ and $$$x-l+1$$$ is odd.

Store all positions where $$$XOR$$$ values and parity are the same in a linear table.Then we just do binary search to find $$$x$$$.

just maintain 2 sets

You can store all prefix xor values in a map value : vector of indexies and then take lower_bound for l in map[prefix xor value of l-1] that will give us the nearest next index with the prefix xor = prefix xor of l-1 and if val^y=val we know that y = 0 so we can use it if y <= r. We should also care about segment to be with an odd length — for this we can have two maps — one for even indexies and the second for odd. My approach works so.

Completely agree ... I wanted to know this part the most !

In this case,$$$a[l]=0$$$,so we just do operation $$$[l+1,r]$$$ ,the answer is $$$1$$$(see the previous line).

Consider an operation sequence: $$$[?,?], [?,?],..., [l, p] $$$, we can prove that the operation $$$[l, p] $$$is always equivalent to $$$a [l] ⊕ a [l+1] ⊕ ... ⊕ a [q] $$$, no matter what the previous operations are.

but how to prove this solution?

you mean that it is just an imp problem?

true. But if they are not one then the answer is going to be 2 right? assuming we can split the segment into two part of total xor 0.

Why do you think this is the issue? The abs function defined on <cmath> and <cstdlib> has the overloads for long long, so it should be returning a long long, same as what they passed to the arguments.

I see a lot of the same solutions from other people and they use abs for long long. It works for them. I am really angry that my code doesn't work on second pretests and can't understand why it doesn't work