**Hint**

**Hint**

**Solution**

**Hint**

**Solution**

1839C - Insert Zero and Invert Prefix

**Hint**

**Hint**

**Hint**

**Solution**

**Hint**

**Hint**

**Solution**

**Hint**

**Hint**

**Hint**

**Hint**

**Solution**

# | User | Rating |
---|---|---|

1 | tourist | 3751 |

2 | Benq | 3727 |

3 | cnnfls_csy | 3691 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | orzdevinwang | 3559 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 164 |

5 | maroonrk | 163 |

6 | SecondThread | 160 |

7 | nor | 157 |

8 | -is-this-fft- | 154 |

9 | kostka | 146 |

10 | Geothermal | 144 |

The first and last elements are always equal to $$$1$$$.

There are at least $$$\lceil \frac{n - 1}{k} \rceil$$$ ones among the first $$$n - 1$$$ elements.

Tutorial is loading...

Try to solve the problem if all $$$a_i$$$ are equal.

Tutorial is loading...

1839C - Insert Zero and Invert Prefix

After every operation, the last element of $$$b$$$ is equal to $$$0$$$.

If the last element of $$$a$$$ is $$$0$$$, then you can always achieve $$$b = a$$$ with some sequence of operations.

Try to solve the problem if $$$a$$$ consists of $$$k$$$ ones followed by single zero.

Tutorial is loading...

Consider the set of balls that were never moved by operations of type 2.

The relative order of these balls never changes, so their colors must form an increasing sequence.

Tutorial is loading...

Consider the graph with $$$n$$$ vertices $$$1, 2, \ldots, n$$$, and on each round of the game, connect vertices $$$i$$$ and $$$j$$$. What can you say about this graph?

This graph is a tree.

Vertices of a tree can be divided into two parts, such that all edges connect vertices from different parts.

If the second player won the game, then sums of elements in both parts were equal in initial array $$$a$$$.

Tutorial is loading...

Tutorial of Codeforces Round 876 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/27/2023 12:28:24 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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? :(

Instead of complaining, just try to solve more problems. I don't think there is anything to blame for this contest.

codeforces ?

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?

Hacks are disabled. But I think $$$149$$$ pieces of $$$150$$$, and $$$150$$$ pieces of $$$149$$$ would be a countertest.

Thank you!

300 * 300 = 9000 ... xD ...

I made same mistake... while trying after contest...

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

subset sum DP and backtracking to find the indices

https://leetcode.com/problems/partition-equal-subset-sum/

If you know how to solve this, u might get gist of how to get the actual subsets.

You actually don't even need to find the actual subset with sum $$$\frac{a_1 + a_2 + ... + a_n}{2}$$$.

Another approach is you have a function which doesn't tell you the actual subset itself, but tells you if such a function exists. You can do this with bitsets:

If for our original vector v,

`brute(v) = 1`

, then person 1 should play first. Person 1 can move however they like, so it's quite a simple case.More complicated is if

`brute(v) = 2`

, in which case person 2 should play first. Say person 1 picks index $$$i$$$, then what should player 2 do? One idea is to iterate over all $$$j$$$ and see what happens if person 1 picks $$$i$$$ and person $$$2$$$ picks $$$j$$$. Using`brute`

, we can check if person 2 still wins. This works, but it is too slow, since it is possible that we have a case like [1, 1, 1, 1, 1, 1, 1, .... , n — 1], in which case on each iteration we have to loop through everybody. We can make this faster by skipping people we've already seen before. There's no need to check two elements with the same value.Proof by AC: 211559245

I liked ur approach

What a joke, n^5/64 AC?

https://www.youtube.com/watch?v=u9QHyBszuq8

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

i have watched your video, I could see after solving E, u were struggling to solve D for more than 20-25 minutes.

can you please elaborate further on D ?

Initially I had correct Idea about how I pick elemeents, but I was unclear about the states for a wrong time which made it quite difficult, than I realized that we can have max_eleement as one of the states and remove index from states

DP[i][j][k] = (min moves required to sort before i such that we have placed j balls and k is the largest elements among the elements I am not touching)

the elements that we don't select should be in sorted order thats how we can put selected elements in their correct places

0000111100011100 // this is one of the examples here all 1's we selected so there are 2 groups we can use 2 balls two choose them, now all the other zeros should have some elements which should be in sorted order

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

Can u explain your code of Problem C

you can generate any 0 1 sequence if the last element isn't 1

you just push zeroes until you want to split sequence to be ones so you enter the number of ones to split them

you just generate the sequence backward

nice editorial thanks

problem c was quite good!

How can we optimize the solution using the segment tree in Problem D?

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 ?

It doesn' matter, they all will produce answer 2 for $$$k >= 2$$$

That is true for this example for k >= 2. but for k = 1 it affects...

Moreover, for

{ 3 , 2 , 1 , 6 , 5 , 4 , 9 , 8 , 7 , 12, 11 , 10 }

now, there are 3 ^ 4 different LIS. What will happen in this case ?

I am looking for more generalised solution, on which subsequence to pick.

in case, it doesn't matter which subsequence we pick, I am looking for proof that why it doesn't affect answer.

I like the way you ask questions ^^

I think you need a proof for why LIS approach by DP is correct

Suppose we have these array

A B C D

LIS for the array is the maximum between

D + LIS til A

D + LIS til B

D + LIS til C

there is no other way to go, so if we guarantee that LIS til A, B and C are correct, The solution for D will be correct.

We can get the solutions for A, B and C first, with the same approach.

So we go bottom up until we reach the solution for the last element.

I think this is enough to prove the DP approach for LIS. The solution for this problem has the same approach with a little modification to include the other state of the allowed segments

DP[i][j] = MAX LIS til i, with max of j allowed mobile segments

For the first note you said, when k = 1, none of these LIS would work becuase all of them need more than 1 segment

You need to find other LIS that have less segments like {2}, or {4}

Thank you for such good explanation. From this few doubts are cleared.

Although my questions were

1) If there are more than 1 LIS, which LIS to pick ?2) If picking any LIS doesn't affect the answer than what is proof for that ?Although, After reading your solution, I have started understanding the approach. Will check your solution. Thanks again.

I would still appreciate, if valerikk can give generalised proof for this.

Do you get any idea, i have similar doubt on this

The subsequence of fixed balls must divide the initial sequence in no more than $$$k$$$ segments, as otherwise we would need more than $$$k$$$ $$$0$$$-balls. LIS (Longest Increasing Subsequence) doesn't always satisfy that condition, and there might not even be any LIS that satisfies that condition. The solution only considers subsequences that satisfy that condition, and picks the longest of them using dynamic programming.

Here is my solution

https://mirror.codeforces.com/contest/1839/submission/208369014

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

Why isn't it [n/k] for A?

Last element has to be 1. Testcase n = 4, k = 2, array satisfying conditions from the front will be [1, 0, 1, 0] then you have to place one at the end which is where the +1 comes from. Formula will be [n/k] + 1 (+1 if necessary, if 1 isn't at the end already).

But how are you certain that this problem won't arise for any other index other than the last index?

NVM got it.

draw a solution array by yourself. you will understand it

or you can see my solution and see the result of my vector

1839A - The Good Array we can also do A as follows from different perspective (0ms)

my first comment

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

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.

I think its just basic logic that

if the last element of array A is 1, we won't be able to produce that arrayusing the operations given since we are inserting only 0s and to make any 0 -> 1, we would need an element after it which is not the case for the last element."If there are multiple solutions, you can output any of them."

So how would you check for this efficiently? n is large

If the last element of the vector is 1 than we can't generate.. intially if we take our ans vector and push back 0 and then if u travrse the array from the last n-2 index and check if its 0 then u push 0 if it is 1 then count how many continues 1's are there and while counting u pushback 0 to our answer and after counting all contigious 1's u pop back an element from ans array for making all 0's to 1 by flipping u just now push the count that ur answer

and here is my solutions https://mirror.codeforces.com/contest/1839/submission/208391614

Please read my question properly again. I am NOT asking for how to solve the question, I have already solved it. What I am asking for is how does the judge check for whether the sequence array B that we generated will give the correct array A efficiently.

For example there can be multiple arrays B that we generate that gives the answer (as stated by somebody's alternative solution below). How does it check for whether our answer is correct?

Once again, I know the solution to C, both of you have misread what I am saying

Sorry I haven't read ur comment properly.. sorry[user:drugkeeper]

Treap with lazy propagation of inverting can work. It can do inserts for log(n) and inverting a subarray can be done lazily for log(n) by storing a bool in the node if a subarray needs to be inverted or not. Whenever the node is visited the flag is pushed down onto both children and the element itself is inverted.

It's an interesting question! Maybe valerikk can explain it?

If you want to simulate the operations efficiently, the hard part isn't even flipping prefixes efficiently (this can be easily done with a lazily updated segment/fenwick tree), but the fact that inserting 0 in the middle moves all following elements around.

I tried solving it slightly differently and using a bunch of non-standard datastructures I ended up with this O(N log N) solution: https://gist.github.com/maksverver/d88df1ca4329da6f0ad79ab01cbab814

But I have a feeling there must be a simpler way to do it.

I'm also pretty sure that it can be done with a binary tree where you keep the subtree sizes in the interior nodes. This allows efficient insertion at an arbitrary index, and it allows efficient flipping if you can mark entire subtrees flipped as you go down the tree. The tricky part is that you do need to rebalance the tree when it becomes too deep, especially for the case where the operations are [0, 0, 0, ..] or [0, 1, 2, 3, ..], and that seems annoying to implement by hand.

The checker used fenwick tree.

For each operation, it finds the position where the zero that was inserted on this operation will end up in final array. To do that, you can go from $$$n$$$-th operation to $$$1$$$-st, and maintain set of free positions (intially, it is $$$ \{ 1, 2, \ldots, n \} $$$). If on $$$i$$$-th operation zero was inserted on position $$$p_i$$$, then its final position is just $$$p_i$$$-th element of this set. Then we delete this element from set and continue. We can maintain this set in fenwick tree, which is able to find $$$k$$$-th element.

After that, to find if zero from $$$i$$$-th operation will be inverted in the final array or not, we can find parity of number of zeroes from operations $$$i + 1, i + 2, \ldots, n$$$ that ended up on bigger positions than this zero in the final array.

Can anyone explain the good array problem for n=9 And k=3 step by step by filling the array I don't able to understand the questions as well as editorial why I need to put 1 at the 1+x.k that part specially by taking forward and backward array please

Who has a solution to problem D based on the Analysis of tasks. Clear code. If there is, please give me.

(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:(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://mirror.codeforces.com/contest/1839/submission/208379619.

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

Can Anyone Guess what is the rating for the B problem

1000 or 1100

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

yes i did the same Code

can anyone please tell me the difference in these two codes why using a regular vector is giving me wrong answer instead of using a vector of pair 208386606 and 208387037

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

dp array is small (~1mb) and access is very cache friendly. If it was 100s of mb and access was random, it would be like 10x slower giving you that 1e8 op/sec estimate.

That was a great insight! Thanks

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) <= kSuppose 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.

I believe what the solution intends to say is that we must

choosethe increasing subsequence $$$S$$$ in such a way that $$$f(S) \leq k$$$, not that this holds true in general. In this particular case, for $$$k=1$$$ we can only choose the first or last elements.Edit: The expression I put for the final answer was wrong, here it is corrected: For a particular $$$k$$$, we first find the maximum $$$|S|$$$. This is either $$$max_{j \leq k}(dp_{n, j})$$$ (Max size of increasing subsequences ending at the last element with less than $$$k$$$ mobile subarrays) or $$$max_{i < n} (dp_{i, j-1})$$$ (Max size of an increasing subsequence ending at anything other than the last element — this means we have one extra mobile segment from the last element of the increasing subsequence till the end of the array). We take the maximum of these 2 values and subtract it from $$$n$$$.

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 your code, you're only decrementing

`on`

once when you erase an element from the set. You should be decrementing by the number of lamps with that $$$a_i$$$ value.Oh right , got it. Thanks a lot !

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

Apply 1st rule for the first i=8 elements. i/k = 8/5 = 1.6. 1.6 rounded up is 2. But that prefix [1,0,0,0,0,0,0,0] has only one element of value 1. So, that array isn't a good array after all.

Oh yes... got it thanks pal

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?

Instead of

write

208859535

Got it! Thank you so much for the help.

Edit: kindly ignore

Is anyone using Python at all? For problem 1839B, my Python 3 code sorts the input once in place, and then uses two pointers. Still, it exceeds 1,000 ms on test 3.

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:

The solution for 1839B - Lamps seems to be wrong. It would fail in case of:

1

5

1 1

3 10

3 10

3 10

3 10

here the algo given in solution would give 31, but the optimal solution could be 40 (switch on all the bulbs of ai=3 one by one).

I implemented this logic, and it failed the testcases (209256805)

and when I changed it to the logic given in the solution(209257360) it passed, even though it is giving sub-optimal results.

valerikk can you clarify on this?

Yeah, yeah... the solution is wrong... but, no people pointed this out! Do they even try ??