valerikk's blog

Codeforces Round #876 (Div. 2) Editorial
By valerikk, history, 18 months ago, In English

1839A - The Good Array

Hint
Hint
Solution

1839B - Lamps

Hint
Solution

1839C - Insert Zero and Invert Prefix

Hint
Hint
Hint
Solution

1839D - Ball Sorting

Hint
Hint
Solution

1839E - Decreasing Game

Hint
Hint
Hint
Hint
Solution
  • Vote: I like it
  • +266
  • Vote: I do not like it

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

Fast editorial !!!

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

You are faster than Hennessey Venom

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

Nice problems and fast editorial!

→ Reply
»
18 months ago, # |
  Vote: I like it -11 Vote: I do not like it

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

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

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

    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

Task E is very beautiful!

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +58 Vote: I do not like it

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.

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

tnx for fast editorial

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

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?

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

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

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

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

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

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

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

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

    subset sum DP and backtracking to find the indices

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

    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.

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

    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:

    int brute (vector<int> v) {
    bitset<90000> bs;
    bs[0] = true;
    int sum = 0;
    for (int i = 0; i < v.size(); i++) {
        bs |= (bs << v[i]);
        sum += v[i];
    }
    if (sum % 2 == 1) {
        return 1;
    }
    if (bs[sum/2]) {
        return 2;
    }
    return 1;
}

    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

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

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

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

    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 ?

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

      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

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

Thanks! Find contest very interesting.

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

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

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

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

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

finally a healthier contest than me

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

my best contest performance ever :)

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

    Can u explain your code of Problem C

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

      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

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

nice editorial thanks

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

problem c was quite good!

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

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 ?

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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}

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

          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.

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

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

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

            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.

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

        Here is my solution

        https://codeforces.me/contest/1839/submission/208369014

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

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

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

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

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

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.

→ Reply
»
18 months ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I think its just basic logic that if the last element of array A is 1, we won't be able to produce that array using 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.

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

      "If there are multiple solutions, you can output any of them."

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

      → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    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://codeforces.me/contest/1839/submission/208391614

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 5   Vote: I like it +8 Vote: I do not like it

      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

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

    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.

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

    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.

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

      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.

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

(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.

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

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

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 5   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I believe what the solution intends to say is that we must choose the 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$$$.

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

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.

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

    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.

    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

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?

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

    Instead of 

    if (A[a] == A[b]) s.erase(a), s.erase(b);
if (A[a] >  A[b]) s.erase(b), A[a] -= A[b];
if (A[b] >  A[a]) s.erase(a), A[b] -= A[a];

    write

    if (A[a] == A[b]) s.erase(a), s.erase(b);
else if (A[a] >  A[b]) s.erase(b), A[a] -= A[b];
else if (A[b] >  A[a]) s.erase(a), A[b] -= A[a];

    208859535

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

      Got it! Thank you so much for the help.

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

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:

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

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

→ Reply