Fast editorial !!!

You are faster than Hennessey Venom

Nice problems and fast editorial!

rank ~380 is solve ABC fast, performance of 2050 but there are also ranks ~3800, who solved ABC without ANY Wrong Answer. They have performance of barely a pupil.

If this isnt speedforces, then what is? :(

Nice E as an interesting interactive problem! Trapped me 20min.

Task E is very beautiful!

An alternative (easier?) explanation of the strategy of the first player (make any move) in E

Lets say that at some point it became possible to divide into two sets with equal sum and it was impossible in the last round. Lets divide, take element that become 0, put it into another set relative to the second element from last round, reverse last operation, now we have two sets with equal sum, contradiction.

tnx for fast editorial

In my (208341484) Knapsack code for E, I messed up and only considered sums/differences of elements that had absolute value not exceeding 9000, instead of absolute value not exceeding 90000. It still got AC.

I am struggling to think of a case that hacks this, can anyone help me?

In problem E, how do you find the subset with sum (a1+..+an)/2?

https://www.youtube.com/watch?v=_2AfC92j0ZE&ab_channel=tyroWhiz

I created the Screencast and tried to Explain Solutions For All the Problems from A — E

Thanks! Find contest very interesting.

proof with tree in problem E is very cool, it's unfortunate that this concept was not really needed to solve a problem

This round could be brilliant if you added a problem between C and D, but, anyway, great job! E was awesome

finally a healthier contest than me

my best contest performance ever :)

nice editorial thanks

problem c was quite good!

valerikk ,

For problem D. suppose my color sequence is...

{ 2 , 1 , 3 , 5 , 4 } ...

Now, there are 4 different LIS ...

1) {2 , 3 , 5}

2) {2 , 3 , 4}

3) {1 , 3 , 4}

4) {1 , 3 , 5}

This is where I got confused, which one should I fix and which one should I keep mobile.

This is what I couldn't figure out for 15 minutes during contest. Can you please give some insights here ?

Finally Void thanks for the great contest and great editorial <3

I had a different construction for problem C. We can define a solution recursively:

f([0]) = [0]
f([a_1, a_2, .. a_(n-2), 0, 0]) = [0] + f([a_1, a_2, .. a_(n-2), 0])
f([a_1, a_2, .. a_(n-2), 1, 0]) = f([!a_1, !a_2, .. !a_(n-2), 0]) + [n-1]

The logic is that if a sequence of operations B constructs a binary array A, then [0] + B will construct A + [0], and B + [|A|] constructs (negation of B) + [0]. The recursive definition just inverses that.

But if we think a little further, we can see that we will only prepend 0s, and append numbers greater than 0 in increasing order, so the final array B will consist of a prefix of 0s followed by a strictly increasing suffix of integers, which are exactly the indices $$$i$$$ where $$$a_i ≠ a_{i+1}$$$). For example: $$$f([1, 0, 0, 1, 1, 0]) = [0, 0, 0, 1, 3, 5]$$$.

This leads to an extremely simple solution. Example solution in Python (my solution during the contest was a little more convoluted).

I didn't find the tree analogy very helpful for problem E.

For one, it doesn't seem to be strictly true: the graph is not a tree but a forest of trees. The simplest example is A=[1,1,7,7]. If the first player selects 1, the second selects 2, then the first selects 3, and the second selects 4. This creates edges 1-2 and 3-4: a forest of two separate trees, not a single tree. Of course, the conclusion that the graph is bipartite still holds!

For another, it doesn't seem necessary. If the array can be partitioned into two parts with equal sum, then player 2 has a winning strategy, as described; this doesn't require the tree analogy. And to show that player 1 has a winning strategy in the other case doesn't require the tree analogy either: it suffices to point out that if the array wasn't partitionable before moves (i, j), then it won't be afterwards.

Proof by contradiction: if after we decrease A[i] and A[j] by d=min(A[i], A[j]) it becomes partitionable into two parts with equal sum, that means there exists a partition where i and j belong to different parts (this follows from the observation that at least one of A[i] has A[j] must be zero after the move, and 0-elements can be freely moved between parts without changing sums), then this is also a valid partition of the original part, contradicting the assumption,

That being said, I thought it was a very cool problem! The solution is quite elegant, but obscure enough that I couldn't figure it out during the contest.

How to write the checker for problem C? Is it using fenwick / segment tree / difference array to do range sums efficiently and checking if the final values are correct? Is it by trying to build increments over ranges in the correct order when inserting the correct 0s? I am not sure

Maybe we can use stack, for every element we append we will also append the number of elements to flip it by, then when we build the final sequence we can maintain the counts? Idk

EDIT: I am asking for the checker, not the solution. I know the solution already.

(Unable to write in English well.Wish to be understood.)

Another $$$O(n)$$$ solution for C.I wrote an $$$O(n\log n)$$$ algorithm while taking the contest but I realized that it could be optimized into $$$O(n)$$$ later.

We only consider that $$$a_n=0$$$.There must have been an operation that inserted a $$$0$$$ at the end of the sequence(simply considered as $$$n$$$ now,how to transform the answer will be shown later).Then we take a look at $$$a_{n-1}$$$.If it turns out to be $$$0$$$,then the operation that inserted the $$$0$$$ in the position $$$n-1$$$ must be after the operation that inserted the $$$0$$$ in the position $$$n$$$,vice versa.More generally,if $$$a_i=0$$$,its operation should be before an even number of operations for which $$$j\ge i$$$,simply take it as $$$0$$$ is ok;If $$$a_i=1$$$,then simply take it as $$$1$$$.We further realized that it is ok to maintain the operation sequence $$$p$$$ simply using swap,such as this:

for (int i = n; i; --i)
  if ((a[i] ^ i ^ n) & 1) swap(p[i], p[i + 1]);

(Initially $$$p_i=i$$$ holds for all $$$1\le i\le n$$$.)

We also realized that $$$q_i=\sum_{j=1}^{i-1}[p_j<p_i]$$$ turns out to be the answer.To solve this,I used a BIT.But actually,it can be easily maintained during the swap process.

Submission:https://codeforces.me/contest/1839/submission/208379619.

This method also enables us to count how many different constructions there can be.

For problem D, I transformed it into a much easier one, the result for k=i can be described as the optimal way to choose m intervals (m<=i) such that after removing these intervals we get an increasing array with the maximal size (assume its size is S), answer for k=i is n-S

For problem D, how is O(n^3) passing so easily? My submission took 78ms. I thought 1e8 operations take ~1sec

Can anyone please explain this in problem D...

As every mobile ball has to be moved at least once, there must be at least one zero-coloured ball in each such segment, which means that f(s) <= k

Suppose we have sequence { 5 , 4 , 3 , 2 , 1 }.

In this case, we have 5 different LIS ( Longest increasing sequences )

If I fix value '5' , or '1' , then above bold statement holds true. But if I fix value {2} , {3} , or {4} then f(s) <= k does not hold.

explanation for fixing {2} , suppose I fix {2}, so, number of fixed values are k = 1, then segments which are not part of this S = ([1-1], [3,5]), so f(s) = 2 .

f(s) < = k is contradiction ( 2 < = 1 doesn't hold ).

Which elements to fix, can someone please explain the solution in more depth with 100 % clear generalised proof.

Can someone point out what is the problem in my submission for B : 208323266

I have implemented the same logic as mentioned in the editorial but am getting wrong answer on pretest 2.

in A (good arrays) for the test case n=9 and k =5 shouldn't the answer be 2 , the array being [1,0,0,0,0,0,0,0,1]. the answer given is 3 and through the above editorials formula its also coming 3 . can someone please explain

I was writing my solution for problem E and I got a TLE on test case 2 on this submission however I added assert(A[a] > 0) where A is the array and a is the input index which is this submission and somehow everything worked, can someone give me an answer on why this might be the case?

Problem E is quite amazing! Once we think it as graph then everything become trivial, but I was wondering what's the intuition behind this? For me the problem seems completely unrelated to graph at all D:

I am not able to understand the first testcase example of problem C , can Anyone help