### valerikk's blog

By valerikk, history, 4 months ago,

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
• +266

 » 4 months ago, # |   +20 Fast editorial !!!
 » 4 months ago, # |   +15 You are faster than Hennessey Venom
 » 4 months ago, # |   +3 Nice problems and fast editorial!
 » 4 months ago, # |   -11 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? :(
•  » » 4 months ago, # ^ |   +74 Instead of complaining, just try to solve more problems. I don't think there is anything to blame for this contest.
•  » » 8 days ago, # ^ |   0 codeforces ?
 » 4 months ago, # | ← Rev. 2 →   0 Nice E as an interesting interactive problem! Trapped me 20min.
 » 4 months ago, # |   +70 Task E is very beautiful!
 » 4 months ago, # | ← Rev. 2 →   +58 An alternative (easier?) explanation of the strategy of the first player (make any move) in ELets 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.
 » 4 months ago, # |   +3 tnx for fast editorial
 » 4 months ago, # |   0 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?
•  » » 4 months ago, # ^ |   +53 Hacks are disabled. But I think $149$ pieces of $150$, and $150$ pieces of $149$ would be a countertest.
•  » » » 4 months ago, # ^ |   0 Thank you!
•  » » 4 months ago, # ^ |   0 300 * 300 = 9000 ... xD ...I made same mistake... while trying after contest...
 » 4 months ago, # |   +19 In problem E, how do you find the subset with sum (a1+..+an)/2?
•  » » 4 months ago, # ^ |   0 subset sum DP and backtracking to find the indices
•  » » 4 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ |   0 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 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
•  » » » 2 months ago, # ^ |   +3 I liked ur approach
•  » » » 2 months ago, # ^ |   0 What a joke, n^5/64 AC?
 » 4 months ago, # |   0
 » 4 months ago, # |   +20 https://www.youtube.com/watch?v=_2AfC92j0ZE&ab_channel=tyroWhizI created the Screencast and tried to Explain Solutions For All the Problems from A — E
•  » » 4 months ago, # ^ |   0 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 ?
•  » » » 4 months ago, # ^ |   +3 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 statesDP[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 places0000111100011100 // 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
 » 4 months ago, # |   0 Thanks! Find contest very interesting.
 » 4 months ago, # |   +11 proof with tree in problem E is very cool, it's unfortunate that this concept was not really needed to solve a problem
 » 4 months ago, # |   +22 This round could be brilliant if you added a problem between C and D, but, anyway, great job! E was awesome
 » 4 months ago, # |   0 finally a healthier contest than me
 » 4 months ago, # |   0 my best contest performance ever :)
•  » » 4 months ago, # ^ |   0 Can u explain your code of Problem C
•  » » » 4 months ago, # ^ |   0 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
 » 4 months ago, # |   0 nice editorial thanks
 » 4 months ago, # |   +2 problem c was quite good!
 » 4 months ago, # |   0 How can we optimize the solution using the segment tree in Problem D?
 » 4 months ago, # |   +4 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 ?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 It doesn' matter, they all will produce answer 2 for $k >= 2$
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 I like the way you ask questions ^^I think you need a proof for why LIS approach by DP is correctSuppose we have these arrayA B C DLIS for the array is the maximum between D + LIS til AD + LIS til BD + LIS til Cthere 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 segmentsDP[i][j] = MAX LIS til i, with max of j allowed mobile segmentsFor the first note you said, when k = 1, none of these LIS would work becuase all of them need more than 1 segmentYou need to find other LIS that have less segments like {2}, or {4}
•  » » » » » 4 months ago, # ^ |   0 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.
•  » » » » » » 4 months ago, # ^ |   0 Do you get any idea, i have similar doubt on this
•  » » » » » » 4 months ago, # ^ |   +18 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.
•  » » » » 4 months ago, # ^ |   0 Here is my solutionhttps://codeforces.com/contest/1839/submission/208369014
 » 4 months ago, # |   0 Finally Void thanks for the great contest and great editorial <3
 » 4 months ago, # |   0 Why isn't it [n/k] for A?
•  » » 4 months ago, # ^ |   0 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).
•  » » » 4 months ago, # ^ |   0 But how are you certain that this problem won't arise for any other index other than the last index?
•  » » » » 4 months ago, # ^ |   0 NVM got it.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 draw a solution array by yourself. you will understand itor you can see my solution and see the result of my vector
 » 4 months ago, # | ← Rev. 2 →   0 1839A - The Good Array we can also do A as follows from different perspective (0ms) int n , k; cin>> n >> k; std::vector v(n+1); int ct = 0; for(int i = 1 ; i <= n ; i+=k){ v[i]=1; ct++; } if(v.back()!=1){ ct++; } cout << ct << '\n'; my first comment
 » 4 months ago, # |   +2 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).
 » 4 months ago, # |   0 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.
 » 4 months ago, # | ← Rev. 3 →   +3 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 sureMaybe 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? IdkEDIT: I am asking for the checker, not the solution. I know the solution already.
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 4 months ago, # ^ |   0 "If there are multiple solutions, you can output any of them."So how would you check for this efficiently? n is large
•  » » 4 months ago, # ^ |   -6 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 answerand here is my solutions https://codeforces.com/contest/1839/submission/208391614
•  » » » 4 months ago, # ^ | ← Rev. 5 →   +8 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
•  » » » » 3 months ago, # ^ |   0 Sorry I haven't read ur comment properly.. sorry[user:drugkeeper]
•  » » 4 months ago, # ^ |   +3 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.
•  » » 4 months ago, # ^ |   +1 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/d88df1ca4329da6f0ad79ab01cbab814But 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.
•  » » » 4 months ago, # ^ |   +11 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.
 » 4 months ago, # |   0 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
 » 4 months ago, # |   0 Who has a solution to problem D based on the Analysis of tasks. Clear code. If there is, please give me.
 » 4 months ago, # |   +3 (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  » 4 months ago, # | 0 Can Anyone Guess what is the rating for the B problem •  » » 4 months ago, # ^ | 0 1000 or 1100  » 4 months ago, # | 0 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 •  » » 4 months ago, # ^ | ← Rev. 2 → 0 yes i did the same Code  » 4 months ago, # | 0 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  » 4 months ago, # | ← Rev. 2 → 0 For problem D, how is O(n^3) passing so easily? My submission took 78ms. I thought 1e8 operations take ~1sec •  » » 4 months ago, # ^ | ← Rev. 5 → +3 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. •  » » » 4 months ago, # ^ | 0 That was a great insight! Thanks  » 4 months ago, # | ← Rev. 2 → 0 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. •  » » 4 months ago, # ^ | ← Rev. 3 → 0 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$.  » 4 months ago, # | 0 Can someone point out what is the problem in my submission for B : 208323266I have implemented the same logic as mentioned in the editorial but am getting wrong answer on pretest 2. •  » » 4 months ago, # ^ | 0 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.
•  » » » 4 months ago, # ^ |   0 Oh right , got it. Thanks a lot !
 » 4 months ago, # | ← Rev. 2 →   0 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
•  » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   0 Oh yes... got it thanks pal
 » 4 months ago, # |   0 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?
•  » » 4 months ago, # ^ |   +3 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
•  » » » 4 months ago, # ^ |   +10 Got it! Thank you so much for the help.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Edit: kindly ignore
 » 4 months ago, # |   0 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.
 » 4 months ago, # |   0 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:
 » 4 months ago, # |   0 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?
•  » » 3 months ago, # ^ |   0 Yeah, yeah... the solution is wrong... but, no people pointed this out! Do they even try ??