### errorgorn's blog

By errorgorn, 19 months ago,

## 1491A - K-th Largest Value

Setter: syksykCCC
Prepared by: syksykCCC

Hint 1
Hint 2
Solution
Code (C++)
Code (Python) (vim1729)

## 1491B - Minimal Cost

Setter: syksykCCC
Prepared by: syksykCCC

Hint 1
Hint 2
Solution
Code (C++)

## 1491C - Pekora and Trampoline

Setter: oolimry
Prepared by: errorgorn

Hint 1
Hint 2
Solution
Code (C++)
Code (Python)

## 1491D - Zookeeper and The Infinite Zoo

Setter: errorgorn
Prepared by: errorgorn

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)
Code (C++) (gamegame)
Code (Python)

## 1491E - Fib-tree

Setter: Widowmaker
Prepared by: Widowmaker and syksykCCC

Hint
Solution
Code (C++)

## 1491F - Magnets

Setter: 3.141592653 and star_xingchen_c
Prepared by: 3.141592653 and star_xingchen_c

Hint 1
Hint 2
Hint 3
Solution
Code (C++)

## 1491G - Switch and Flip

Setter: errorgorn and oolimry
Prepared by: errorgorn

Hint 1
Hint 2
Hint 3
Solution
Code (C++)
Code (Python)

## 1491H - Yuezheng Ling and Dynamic Tree

Setter: Ynoi
Prepared by: Widowmaker and Ynoi

Hint 1
Solution
Code (C++)

## 1491I - Ruler Of The Zoo

Setter: oolimry
Prepared by: oolimry

As the solution to this problem is very long, the full editorial is split into $4$ parts. If you want to challenge yourself, you can try reading one part at a time and see if you get any inspiration. You can also try to read the specific hints for each part.

Part 1 Hint 1
Part 1
Part 2 Hint 1
Part 2 Hint 2
Part 2 Hint 3
Part 2
Part 3 Hint 1
Part 3 Hint 2
Part 3 Hint 3
Part 3 Hint 4
Part 3 Hint 5
Part 3 Hint 6
Part 3
Part 4
Code (C++)
Code (C++) (errorgorn)

• +255

 » 19 months ago, # |   +53 oolimry orz
•  » » 19 months ago, # ^ |   +15 oolimry orz
•  » » » 19 months ago, # ^ |   +5 What is orz?
•  » » » » 19 months ago, # ^ |   +174 seems it:
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   +6 We can alternatively use OTL
•  » » » » » » 19 months ago, # ^ |   -10 OTP?
•  » » » » » » 19 months ago, # ^ |   +38 i prefer nO
•  » » » » » » 19 months ago, # ^ |   +5 OTL????
•  » » 19 months ago, # ^ |   +11 oolimry orz
 » 19 months ago, # |   0 Wow!! Really fast editorial
 » 19 months ago, # |   -55 Downvote me
 » 19 months ago, # |   0 Is there any stream coming up for post-contest discussions?
•  » » 19 months ago, # ^ |   0 No one as per I notice for this contest.
 » 19 months ago, # |   0 so fast
 » 19 months ago, # |   +32 In the editorial for D, it has the & thing
•  » » 19 months ago, # ^ |   0 yep it was fixed. writing & on codeforces latex equations is finnicky :/ you have to do \\&
•  » » » 19 months ago, # ^ |   +9 There is still the & thing in the solution part for D
 » 19 months ago, # | ← Rev. 4 →   +4 I thought D very differently Observations :-If you want to reach from X to Y 1) X>Y this case is a clear NO. it needs no explanation. 2) THE NUMBER OF SET BITS IN Y can never be greater than X if you want to reach from X to Y. 3) IF YOU HAVE AN ODD X then you can reach every Y which has number of set bits less than of equal to Number of set bits in X. 4) NOW IF YOU HAVE AN EVEN X , I was stuck on this case and had no patterns to observe , if anyone has done it this way , please share your approach
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 I think your case 3 is wrong. Consider X=1000110 and Y=0111001 where least significant bit is on the left. We cannot obtain Y from X.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 I think the case you have given me has number of Set Bits in Y as 4 and number of set bits in X is 3 , My case 3 says for Odd X we can reach any Y which has number of set bits less than or equal number of set bits in X.
•  » » » » 19 months ago, # ^ | ← Rev. 3 →   -9 wait sorry. X=10011100 and Y=01100001Another thing you have to check is that there exists a matching. Here, the $2$ bits in Y can only use $1$ bit in X.
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 ok lemme see this case once
•  » » 19 months ago, # ^ | ← Rev. 3 →   +1 I have got accepted in this way. Idea was if you want to reach X to Y then Y have to be smaller or equal than X, number of setbits in Y should be less or equal than number of setbits in X and all setbits index in Y should be later or in same index corresponding to X. Because if one of the setbit of Y is before the corresponding setbit of X then you will never decrease Y to X.
 » 19 months ago, # | ← Rev. 2 →   +61 As a Chinese writer, here is the Chinese version of the tutorial (A-H).Hope you enjoy it. :DUPD: The tutorial of problem I has been attached.
•  » » 19 months ago, # ^ |   -67 Can Chinese visit internet? I heard that China is the censorship king? Are you here through a VPN?
•  » » » 19 months ago, # ^ |   +5 You spelled north korea wrong
 » 19 months ago, # |   0 Fast editorial...!
 » 19 months ago, # | ← Rev. 2 →   +55 A perfect round I see.And I want to explain why some people fst on H.They pushdowned lazytag to every a in the block.It's wrong actually. Its complex is $O(n^{\frac{5}{3}})$I am sorry to say that I thought it when I doing with my data, but I think no one would write like that because it's easy to change it into just pushdown when query.Sorry for the fster.FST is the soul of CF. —— Sooke
•  » » 19 months ago, # ^ | ← Rev. 3 →   +5 [user:Wodiwmaker] What is "fst" ?Edit: Ans->FST is short for failed in system testing.
 » 19 months ago, # |   -18 In the problem B there are some cases when |a[i] — a[i — 1]| > 1, but answer is not 0.One of that cases is:n = 4 a[1] = 1 a[2] = 3 a[3] = 1000001 a[4] = 1000000If we want to reach to the node (4, 1000001), we will move one of the obstacles in node (3, 1000001) or (4, 1000000).This means, that in this case answer is not equal to 0.
•  » » 19 months ago, # ^ |   +19 1 <= a[i] <= 10^6
 » 19 months ago, # | ← Rev. 3 →   +270 I'm sorry, but I'm honestly not sure how it's even possible to write such egregiously weak pretests. My E fails on any test case where N is not a Fibonacci number, as it doesn't return after printing no (and thus prints either yes or a second no afterwards), and yet it passes all pretests and ultimately gets FST24. I would understand the FST if I had some minor bug in an edge case, but a generator that outputs trees completely at random would fail my submission nearly 99.99% of the time. (And evidently, pretests for A, B, C, and G weren't so strong, either...)I would have assumed y'all were intentionally aiming for weak pretests if not for the comment on the other thread hoping for few FSTs. Especially given that comment, I think it was pretty reasonable to assume that a test covering this sort of case was included in pretests. I appreciate the preparation that went into the remaining problems, but it probably shouldn't be too hard to understand why losing 90 rating over this FST sours my opinion of this round in general.
•  » » 19 months ago, # ^ |   +64 LOL the same thing happened to me too. I got RE on test 24 (my code also fails in any test where n is not a fibonacci number). That's very upsetting because I could have found my bug in a few minutes and the effect of this minor error cost me over a 100 rating points (and a t-shirt :( )
•  » » 19 months ago, # ^ | ← Rev. 2 →   +63 I want to say a lot, but I can just say sorry now.I did write a generator for that case.It has 1/5 posibility to generate a non-fibonacci-number $n$.For some reason, I just upload it and add a test to tell them I have written a generator for E.But they write a new generator and forget this case.So finally We just used that to create a test however. And unluckily, it's not in that case.Sorry again :sadness:
 » 19 months ago, # |   +1 I saw tourists solution of C in O(n) using DSU, how to solve it using DSU?
 » 19 months ago, # |   0 Typo in the solution for 1491D?  bit from v from u from the
 » 19 months ago, # |   0 Can we get an example for this — 1491D  We can convert any u+v move to a series of u+v′ moves where u&v′=v′ and v′=2k.
 » 19 months ago, # |   +239 You serious? Part 1 Hint 1Part 1Part 2 Hint 1Part 2 Hint 2Part 2 Hint 3Part 2Part 3 Hint 1Part 3 Hint 2Part 3 Hint 3Part 3 Hint 4Part 3 Hint 5Part 3 Hint 6Part 3Part 4
•  » » 19 months ago, # ^ |   +8 5000 score bro.
 » 19 months ago, # |   0 Got the correct idea of E but failed to implement it :(
•  » » 19 months ago, # ^ |   0 same
•  » » 19 months ago, # ^ |   0 same, just missing a "break" :(
 » 19 months ago, # |   +10 Problem B got me confused with the constraints during contest. Didn't realise that the obstacle can't be placed on first and last column which led to completely different approach. And rather complex bounds to deal with.
•  » » 19 months ago, # ^ |   0 I wasted an hour with the same misunderstanding of the question.
•  » » 17 months ago, # ^ |   0 Didn't realise that the obstacle can't be placed on first and last column I realized this only after reading your comment. OMG.
 » 19 months ago, # |   +1 I think I have the same logic in 2nd question but the test didn't pass. How can I know which test case made it wrong?
•  » » 19 months ago, # ^ |   0 You can scroll down through your submission to see on which case your o/p differ. But there is limitation to number of test case shown.
 » 19 months ago, # |   -63 .
 » 19 months ago, # |   0 Peko Peko
 » 19 months ago, # |   0 I think C's editorial is kinda overcomplicated although the final idea is the same. You always need to start from the first s_i that is not 1 and perform s_i-1 jumps, then it is just a simulation problem.
•  » » 19 months ago, # ^ |   +2 Can u demonstrate plz more ? I did the following : each number can't be more than 5000 (worst case) because it throws the rabbit out so we add to the answer A_i — 5000 if A-i >5000 then iterate from left for every value that is not 1 run a simple DFS starting from this index until it becomes 1 and simulate the process but that was TLE since it is O(n³) I need to improve it to become O(n²)... thanks in advance.
•  » » » 19 months ago, # ^ |   0 Just maintain an array nxt[i] for the position of next non-1 number after i. Then if a[i] is 1, use nxt[i] instead of simply i++.Since after use nxt[i], you can always land on a non-1 number and decrease it by one. And the initial total height of all a[i], as you said, is at most 5000*5000. Therefore, this solution is O(n^2).
•  » » 19 months ago, # ^ |   +3 Can you please explain the solution to C a bit in detail , I can't get what the editorial is trying to say at all
 » 19 months ago, # |   0 thanks, upsolving time
 » 19 months ago, # |   -8 what about when the obstacles in (0 ,1) and (n-1 , 1e6+1) in problem "B"!!
•  » » 19 months ago, # ^ |   +8 The first and the last column are excluded from having obstacles, see the constraints!
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 I'm miss this point, thank you
•  » » 19 months ago, # ^ |   0 It is written that 1<=a[i]<=1e6
 » 19 months ago, # |   +8 In problem E, I started dfs from 1 and calculated the sizes of all the subtrees and checked whether the size of any subtree is a part of fibonacci sequence, but can anyone please explain why it gave wrong answer on pretest 14, link to my SOLUTION. Thank you :)
•  » » 19 months ago, # ^ |   0 It seems that if a subtree has Fi nodes this does not guarantee that it will be a fib-tree
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 I got WA using the same algorithm, and find the counter example: 8 2 1 3 2 4 3 5 1 6 1 7 1 8 4 
 » 19 months ago, # |   -13 VideoTutorial for (A + B) = https://www.youtube.com/watch?v=AHrgCvgeXo0
 » 19 months ago, # |   +5 Can anyone explain C better that is what is happening in editorialists solution?
•  » » 19 months ago, # ^ | ← Rev. 3 →   +5 Have an array curr which holds all the jumps made on an index.For an index i: if the jumps made so far (curr[i]) were not enough to get it to 1, then add to the solution the remaining Si-1-curr[i] jumps (each of these jumps is a new pass because i is the first non-1 trampoline). after the if is executed, temp is the number of jumps on index i temp — (Si — 1) = the number of jumps on index i — the number of jumps necessary to get to strength 1 = all the jumps that jumped to i + 1. So we add all of these jumps to curr[i + 1] add 1 jump to curr[j] for j in range [i + 2, i + Si]. These jumps are performed in order to get the trampoline i to strength 1
•  » » » 19 months ago, # ^ |   0 emp — (Si — 1) = the number of jumps on index i — the number of jumps necessary to get to strength 1 = all the jumps that jumped to i + 1. So we add all of these jumps to curr[i + 1]can you explain this part a bit ! I just cannot understand how is this true ?
•  » » » » 19 months ago, # ^ |   0 When the for loop gets to index i: curr[i] represents the number of jumps that happened already on trampoline i curr[j] where i < j (all indexes to the right of i) represent the number of jumps on trampoline j that were the second jump of a pass. This is the key point. If a pass started at index 1, jumped from 1 to 3 and from 3 to j, this jump on j is not yet added to curr[j]. Example: Si = 3, curr[i] = 5. The first jump gets us to i + 3 (we add this to curr[i + 3]) The second jump gets us to i + 2 (we add this to curr[i + 2]) Jumps 3,4,5 jump to i + 1 but we don't add +3 to curr[i + 1] in the second for loop, that only does cur[j]++. So when we get to index i, we add these 3 jumps to i + 1. This is done in curr[x+1]+=temp-arr[x]+1;
 » 19 months ago, # |   +1 can someone explain c more clearly?
 » 19 months ago, # |   +3 someone please Explain C ..... the editorial is too complex at least for me
•  » » 19 months ago, # ^ |   0 Same here
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 You have to jump on the first number which is greater than 1, then just add 1 to all the further indexes where current number will jump (for this you can keep an temp array) and for any further number check how many times you came on it already , then jump more if then number is still greater than 1
•  » » 19 months ago, # ^ |   +2 it's clear that for each i from 1 to n you have to jump in the i'th position a[i]-1 time right?ok we will do it lets start from the first position and jump on it until it become 1 but on each jump on this element tell the next positions that you have jump to themhow??ok if n = 10and a[1] = 5in the first jump you will go to the position 1+5 ok just tell the 6'th position that you will go to himknow a[1] = 4 and that next jump will take you at the first step to 1+4 yes tell the 5'th position you will go to himwhen a[1] become 1 you will have told each position that you will jump to himso when you go to i+1, i+2, i+3.... you can know that you jump on the current position some times if this number of jumps grater then a[i]-1 you don't have to make any other jumps in the current position else you will do the remain jumpsbut don't forget you have just calculate one step from each position to another so when you are in some position j you have to till the next positions that you are jumped on themO(n^2)
•  » » » 19 months ago, # ^ |   0 now i know the basic O(N^3) solution with help of some and your comments. can you explain how to reduce it to O(N^2) time complexity?
•  » » » 19 months ago, # ^ |   0 Can you tell how to find how much time I will jumping on each trampoline for a certain starting point ?
•  » » » 19 months ago, # ^ |   0 So basically what I can conceive is that we don't really wanna do the jumps as in a simulation but all we do is store where those jumps are going to be so that when we want to start the procedure at index j we will determine if that index is already has become 1 or it is valid to start another jumping journey from it . If I'm right then your explanation should really be the editorial :D
•  » » 19 months ago, # ^ | ← Rev. 4 →   +29 I finally get how to solve C. Here's how:Problem RecapJump from any trampoline (say index 'i'), land at index (S[i] + i). If index (S[i] + i) is in bounds, then continue jumping in a similar manner until you're out of bounds. At each hop, you're reducing the trampoline's strength by 1. Make all trampolines' strength 1. How many initial jumps does it take?Observations Trampolines can only propel you to the right. Which implies that you need to start from the left and start jumping from the first trampoline that's greater than 1 (Note that you could jump from the leftmost trampoline as well — it has the same effect as starting from the first trampoline with a strength greater than 1). Consider what happens when a trampoline i has a strength of 1 (i.e. S[i] = 1). It simply propels you to the next trampoline to its right (i + 1). Next, consider what happens when a trampoline i has a strength of 4 (i.e. S[i] = 4). On it's first jump, it lands on trampoline i + 4, and S[i] becomes 3. On the next turn from the same trampoline i, it lands on trampoline i + 3, and S[i] becomes 2. Finally, it lands on trampoline i + 2 and S[i] becomes 1. We can now move on to the next trampoline to its right. So, for any trampoline i with a strength of S[i], we jump once to each of indexes i + 2 up to i + S[i]. We need a way to track this. Use prefix sum markers (add 1 to the beginning of the range: pref[i + 2]++, and subtract 1 after the end of the range: pref[i + S[i] + 1]--). Here pref[] is the equivalent of prior incoming hops to those subsequent trampolines. Observe how we're simply marking how many times a jump would go to a future index (and not processing that future index at this time — we will get to it eventually). Also, note the final result only calculates the total number of hops initiated from the current trampoline. Say we now get to the trampoline at index i + 7 and you've landed here 4 times from prior incoming hops (which would mean that pref[i + 7] = 4). Since you've landed here from prior hops, those hops should not count towards the final cost. So the net sum for this trampoline would be S[i] — 1 — pref[i] (since you need S[i] — 1 hops anyway out of which pref[i] are from prior hops). Of course, if this is negative, you discard it. So if S[i + 7] were 6, since you've already come here 4 times from prior hops (you'd be left with a net strength of S[i + 7] = 6 — 4 = 2), and you'd need to initiate just one hop to make S[i + 7] = 1. IMO, a very tricky part of this problem is when prior hops exceed S[i] — 1. In that case, S[i] would've become 1 already at some point, and every additional prior hop (i.e. incoming_hops[i] — S[i] + 1) would land at position i + 1. Using prefix markers, we can increment pref[i + 1] by this additional hop count and decrement pref[i + 2] by the same. Also, another thing that I found confusing was the relationship between incoming hops and current strength. There is no correlation between the two. You would have to jump S[i] — 1 times regardless of whether you came via incoming hops or initiated the jumps from the i'th trampoline. The only difference is the cost (the more the prior hops, the lesser the net cost in terms of jumps initiated from position i). Reference
•  » » » 19 months ago, # ^ |   +4 Thanks for the clean explanation!
•  » » » 19 months ago, # ^ |   0 Thanks a lot. Nice explanation!
•  » » » 19 months ago, # ^ |   0 This is best to be included in official editorial.
•  » » » 19 months ago, # ^ | ← Rev. 47 →   0 Thanks for the explanation. But I am not getting what pref[] array is storing. I got that starting from any non-zero value of s[i] we can increment the range (i+s[i],i+2) by 1 and when we will get there we will decrement that s[j] by 1+pref[j] but how we are maintaining this pref[] array?
•  » » » » 19 months ago, # ^ |   +1 In general, pref[i] stores t[i]-t[i-1], where t[i] is the number of ranges that started at some j<=i and will end at some k>i. Notice that we can always derive t[i] from the pref array, using the formula t[i] = pref[0] + ... + pref[i]. If i is running from 0 to n-1, deriving t[i] per i is O(1), since pref[0]+...+pref[i-1] is pre-computed. The advantage of maintaining pref[] (instead of t[]) is that, updating information for a range is faster: just 2 operations (Observation 3 in sh_maestro's post). Whereas if we maintained t[], that would be linear in the size of the range.
•  » » » » » 19 months ago, # ^ |   +1 Thanks for replying.
•  » » » 19 months ago, # ^ |   0 Thanks for the descriptive explanation.
•  » » » 19 months ago, # ^ |   0 Thanks, very nice explanation, I just to understand point $6$ what is incoming hops, did you mean $pref$can you please elaborate more on point $6$. I have implemented this during contest, but it did not work.
•  » » » » 19 months ago, # ^ |   0 I think incoming_hops[i] is the total number number of jumps from previous positions to position i. We have that incoming_hops[i] = pref[0]+...+pref[i] = incoming_hops[i-1] + pref[i]
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +4 I'll elaborate here (I've also added a little more context to the original explanation)pref[] is the same as incoming hops. When you are at index i, you need a way to designate the indexes that index i will hop to. Say the trampoline at index i has a strength of 5 and hence hops from indexes (i + 2) to index (i + 5). pref[] will add 1 for each element between these 2, inclusive (i.e. pref[i + 2]++, pref[i + 3]++, pref[i + 4]++, pref[i + 5]++). Note that you don't actually need to update each index as that would be an expensive O(N) operation. You can do it in O(1) by simply updating the bounds (one at start, and one right after end) and have a rolling prefix sum to calculate the net result so far (pref is called "here" in the reference code — I should've been more consistent).To elaborate on point 6 (which is now point 7 since I added one), consider this example: Strength: [**4**,4,4,2,3] Pref: [0,0,0,0,0] Answer: 0 At index 1, a strength of 4 means that it will initiate 3 jumps (to indexes 3 through 5). Lets update pref accordingly. Strength: [**1**,4,4,2,3] Pref: [0,0,1,1,1] Answer: 3 Move to the next trampoline to its right. Strength: [1,**4**,4,2,3] Pref: [0,0,1,1,1] Answer: 3 At index 2, initiate 3 more jumps (to indexes 4 and 5 and once out of bounds). Strength: [1,**1**,4,2,3] Pref: [0,0,1,2,2] Answer: 6 Done with this trampoline. Move on to index 3. Strength: [1,1,**4**,2,3] Pref: [0,0,1,2,2] Answer: 6 At index 3, notice that there was 1 prior jump so 2 (i.e. pref[3] == 1) new jumps need to be initiated to bring its strength to 1. Total of 3 jumps (one prior, 2 new) — once to index 5 and twice out of bounds. Strength: [1,1,**1**,2,3] Pref: [0,0,1,2,3] Answer: 8 Done. Lets move to index 4. Strength: [1,1,1,**2**,3] Pref: [0,0,1,2,3] Answer: 8 Now, index 4 is different from the rest. It has had 2 incoming jumps and has a strength of 2. The first hop makes it jump out of bounds, and brings its strength down to 1. The second hop makes it jump to index 5 (i + 1, instead of the i + 2 that we've seen so far). Had there been a third jump, that would've gone to index 5 as well. Note that the answer remains 8 since no new jumps had to be initiated here. Strength: [1,1,1,**1**,3] Pref: [0,0,1,2,4] Answer: 8 Finally we move to the last index Strength: [1,1,1,1,**3**] Pref: [0,0,1,2,4] Answer: 8 Here again, the incoming jumps (pref[5] = 4) exceed strength — 1 (3 — 1 = 2) by 2. So no new jumps need to be initiated and the answer remains 8.
•  » » » » » 19 months ago, # ^ |   +1 Excellent explanation, this is more than what I could hope for! thank you so much for your time.
•  » » » » » 19 months ago, # ^ |   +1 Just want to say thank you! Finally understood the solution.
•  » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 finally understood trying whole day , i think showing an example is better than writing pages worth of editorial
•  » » » 19 months ago, # ^ |   0 Trampolines can only propel you to the right. Which implies that you need to start from the left and start jumping from the first trampoline that's greater than 1 Why we can't start from 1 as we eventually reach first non-one and it did not increase the pass count ?
•  » » » » 19 months ago, # ^ |   0 Good point. You could start from the first trampoline on the left — it has the same effect as starting from the first trampoline with a strength greater than 1. I've updated the text around this.
•  » » » 19 months ago, # ^ |   0 I have 2 questions: 1.) What is "count" doing? 2.) Why decrement one from the position after range? I mean, why here[mx + 1]-- and why not here[mx]--?
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 1) after some pass s[i] will be equal to 1. then pekora will jump from i to i+1 trampoline when it is on i-th trampoline . here count variable counts the number of incoming hops on i after s[i]=1 2) to increment the number of incoming hops from i+2 to i+s[i]. To understand it better you can read this article.
•  » » » » 19 months ago, # ^ | ← Rev. 3 →   0 To your first question:"count" tracks the number of extra hops (i.e. for any index i, it's incoming hops — (strength — 1)). The reason for counting this separately is that these hops will all go to index i + 1.To recap, if incoming_hops is 10, and strength is 4. Then the first 3 hops will go to indexes i + 4, i + 3 and i + 2. At that point the strength becomes 1. But there are still 7 (10 — 3) more incoming hops. Those 7 will all go to index i + 1.To your second question:When you want to add an "amount" to a range [l, r] (both inclusive), the way you do it is to mark pref[l] += amount and pref[r + 1] -= amount. This is because you want pref[l] through pref[r] to all get incremented by that amount, and then decrement by the same as soon as you step beyond r. Then at each index, you accumulate the sum. So pref[l + 1] += pref[l], then in the next iteration pref[l + 2] += pref[l + 1], etc. — this way the sum gets carried over from the current index to the next.The link shared by Saimun_Islam explains it in detail.
 » 19 months ago, # |   -30 A good hint for problem B:just look at the constraints dummy haha!
»
19 months ago, # |
0
###### This is optimal as we can consider the first trampoline that Pekora jumps on for both these passes. It is clear that the series of trampolines jumped on in these 2 jumps does not change.

Please someone explain this in Problem C.

•  » » 19 months ago, # ^ |   0 It basically says that you can freely exchange the order of trampolines you choose to start and the resulting strengths in the end will always be the same. You can play around with some examples to see why this is true.
 » 19 months ago, # | ← Rev. 2 →   0 Can anyone help me to figure out why and where I am getting that one extra (0/1) in the answer in Testcase 2 in Problem A Solution . Thanks in advance for your help.
•  » » 19 months ago, # ^ |   0 There are q queries not n queries. See the input section.
•  » » » 19 months ago, # ^ |   0 Thank You sir, rectified the problem and got AC.
 » 19 months ago, # |   0 My self worth took a big hit during this contest.. The round was really great though! Kudos to the authors..
 » 19 months ago, # | ← Rev. 20 →   +6 The problems had a lot of variety. I appreciate your hard work in setting such a nice contest and for such a quick editorial. Wish more such contests keep happening!
•  » » 19 months ago, # ^ |   +3 Your solution is O(n^3) !!
 » 19 months ago, # |   +3 I've done C with a lazy propagation segment tree (adding a constant on the range), so my solution is O(n log n). Any ideas how to get to O(n)?
•  » » 19 months ago, # ^ |   0 You need to add on range right, so you can just maintain a array and increase $l$ by $1$ and decrease $r$ by $1$. So you are just iterating from left and these range additions are also accounted for.
•  » » » 19 months ago, # ^ |   0 ahh yes, that trick.. Thank u very much
•  » » 19 months ago, # ^ |   0 Can u plz explain your approach ? I'm learning segment tree right now so this would be so helpful
•  » » » 19 months ago, # ^ |   0 U can learn seg tree here https://cp-algorithms.com/data_structures/segment_tree.html My approach was to have a segtree of lenth n, initially set to zero. Then I would traverse the array from left to right and add the value from index i on the appropriate segment
 » 19 months ago, # |   0 Please Help me In Problem C, I have done normal simulation as given in editorial O(N^2) and still am getting TLE on TC 9.My Submission Link https://codeforces.com/contest/1491/submission/108727431Please Codeforces community
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 TLE because O(N^3)The editorial doesn't simulate all the jumps in order. I did, but I skipped all the jumps equal to 1 by using a set of intervals for these trampolines. The code is long and ugly though.
 » 19 months ago, # | ← Rev. 3 →   0 Problem D, any manipulation of U will maintain or reduce the number of 1s in binary. Observe 0011 => 0101 => 1001, 0011 => 0100. There is no way that we can increase the number of 1s. And we can always promote a single 1 to higher bits or squash arbitrary 1s to a single 1.Counting prefix sum of 1s (from lower bits to higher bits) in U and V, and we can not transform U to V if any prefix of U has fewer 1s compared to the prefix of V.
 » 19 months ago, # |   +8 In python solution of 1491C — Pekora and TrampolineWhat is the meaning of line temp+=arr[x]-1-tempdoesn't it just means temp = arr[x] — 1?
•  » » 19 months ago, # ^ |   0 no , it means temp = temp + arr[x] — 1
•  » » » 19 months ago, # ^ |   0 temp += arr[x] — 1 — tempthis is equal to : temp = temp + (arr[x] — 1 — temp)which means temp = arr[x] — 1Am I doing anything wrong here?
 » 19 months ago, # | ← Rev. 2 →   +151 In problem E, my code will have some problems when n is not a fib number, I noticed that after I locked problem. There is a person in my room who make mistakes with data like this, I submitted a hack data (this data also can hack myself), and it returned unexpected verdict.I Failed System Test in E, and my hack has been ignored. But this submission was hacked by me, I didn't get 100 score.Why is it?
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 this is strange!!
 » 19 months ago, # |   +51 雪花飄飄北風嘯嘯 天地一片蒼茫:D
 » 19 months ago, # |   0 In fact, I have some questions about the problem B. In the tutorial, we can find that the answer will be one of the three numbers: 0, min(u, v) and v + min(u, v). But considering the following data:4 3 41 0 1000001 1000000, we can find that we have to move two obstacles to make sure that we can reach (4, 10000001) from (1, 0). And in my opinion, the answer will be 2 * min(u, v).If I'm wrong, I'll highly appreciate if you can tell me which condition I missed. Thanks.
•  » » 19 months ago, # ^ |   0 Read the problem description carefully.
•  » » » 19 months ago, # ^ |   0 Oh, thanks. I find that where I'm wrong. The $a_i$ is not greater than $10^6$, so the situation I considered won't happen.Thanks again.
 » 19 months ago, # |   +5 My ugly O(n^2\log n) solution for C passed...... My solution is simulate the jump, and use a balanced BST to find the next trampoline with S > 1 in O(\log n) time. Number of total jumps is O(n^2)
 » 19 months ago, # |   0 My submission for C got TLE even though i'm sure it's $O(N^2)$, can anyone help me? Probably a problem in the while loop but hard to tell for me. Submission Link
•  » » 19 months ago, # ^ |   0 not exactly sure, but maybe because the upper limit on the value of S[i] is 10^9?
•  » » 19 months ago, # ^ |   +36 Naive simulation is actually $O(N^3)$. It hits that bound on test 5000 4999 4998 ... 2 1.I probably should make editorial more clear about how to simulate in $O(N^2)$.
 » 19 months ago, # |   0 Can anyone explain D to me
•  » » 19 months ago, # ^ |   0 means what is the intuition behind this?
•  » » » 19 months ago, # ^ | ← Rev. 4 →   +2 Let's take a binary string here as example, 1001100101. Notice that if we pick any number which has one set bit(i.e a power of two) whose set bit lines up with a set bit in the given binary string(for example binary string 100), then its bitwise and will be the string itself(1001100101 & 100 =100). Now when we add the two numbers, two cases might occur. If there are no consecutive set bits ahead of the set bit, then the set value shifts by one bit(1001100101+100=1001101001). If there are consecutive set bits ahead of the set bit, then the first set bit in the consecutive set bits shifts by 1 bit, and the other consecutive set bits disappear(1001100101+100000=1010000101). So if we can reach number v from number u by applying these two possible operations, then there is a path between them.
•  » » 19 months ago, # ^ |   0 I manage to pass by counting prefix. If you don't understand the editorial, maybe you can check my explanation.
 » 19 months ago, # |   +13 Can someone tell me what is wrong in my submission for problem E? I am getting WA on Test 14
 » 19 months ago, # | ← Rev. 2 →   0 Can anyone help me out why am i getting WA on test case 8 in E My submission — Your text to link here...
 » 19 months ago, # |   0 The problems had a lot of variety. I appreciate your hard work in setting such a nice contest and for such a quick editorial. Wish more such contests keep happening!
 » 19 months ago, # |   0 Can you explain D bit more ? Why exactly do we want v = 2^k ? And what does this line mean ? This is because we can add each bit from v from u from the highest bit as adding a bit to a number will not affect lower bits. 
 » 19 months ago, # |   0 c giving tle O(n^2) solution. can anyone check it? 108774513
 » 19 months ago, # | ← Rev. 2 →   0 Can anyone explain why my O(N) program is getting a TLE(Pretest 13) in E. I am making an adjacency list and running a dfs to calculate subtree lengths from each vertex. Then linear searching whether the (k-1)th fibonacci is present in the lengths. Link:- https://codeforces.com/contest/1491/submission/108778746
 » 19 months ago, # |   +10 the Python solution in this editorial for problem 1st gets TLE in both Python3 and PyPy 3. So heres my solution which got accepted 108784095
•  » » 19 months ago, # ^ |   0 108805120 it doesnt tle?
•  » » » 19 months ago, # ^ |   +10 No, i am talking about 1419A, Kth largest element problem , the solution given in the editorial Your solution is this [submission:108783813]it gets tle
•  » » » » 19 months ago, # ^ |   +3 alright ill add your solution into editorial :)
•  » » » » » 19 months ago, # ^ |   +3 You are super nice. errorgorn orz
 » 19 months ago, # | ← Rev. 2 →   0 Why this number is so common among testers and random generators :XD This is the 27th testcase of problem C
•  » » 19 months ago, # ^ |   0 You go here.
 » 19 months ago, # | ← Rev. 2 →   0 In the question B, do we have to move the obstacles before starting our movement or can we move the obstacles while we are at some other node(instead of 1,0)? Because then the answer changes for this test case:- 2 100 1 1 2 If we move the obstacle 1 and move it to our current node then we cannot go pass through the obstacle and hence the answer is 2(by moving the second obstacle twice towards right) but if we can move the obstacles during the journey then the answer would be 1. According to the solution the answer should be 1 but according to the problem statement its not possible because then the obstacle is at the starting node.
•  » » 19 months ago, # ^ |   0 Nvm I got it. We can move the second obstacle towards the right.
 » 19 months ago, # | ← Rev. 3 →   0 I have a doubt in B. What if the obstacle in last row is present on 10e6+1 and on all rows before that, its present on 10e6 then v is not a possible answer. Please enlighten me.
•  » » 19 months ago, # ^ |   0 1<=ai<=1e6. So the obstacle will be never on the column 10e6 + 1.
•  » » » 19 months ago, # ^ |   0 Thanks I had missed that
•  » » » » 19 months ago, # ^ |   0 Same bro i also missed the part that 1st and last columns are empty. You should try when there are no such restrictions. I submitted a general code assuming no restrictions in the placement of obstacles in column.
•  » » » » » 19 months ago, # ^ |   0 Your code doesn't even solve the general case and you have a couple of redundant if statements.
•  » » » » » » 19 months ago, # ^ |   0 Tell me the test case. I will think about it.
 » 19 months ago, # | ← Rev. 3 →   0 errorgorn oolimry In C editorial's python code is giving tle.
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 108805120 it doesnt tle?
•  » » » 19 months ago, # ^ |   0
•  » » » 19 months ago, # ^ |   0 It gives tle verdict in python3 but not in pypy.
•  » » » » 19 months ago, # ^ |   0 yea pypy3 is super fast compared to python3. you should select pypy2/3 when using python
 » 19 months ago, # |   0 Can you please tell the DP approach for problem C....I got stuck at it just because I kept thinking that it had to be done using DP
 » 19 months ago, # |   0 Can someone explain C to me?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +1 Because of greedy works, we should reduce S (to 1) from left to right.Use tmp(i) to present the numbers of jumping on the i-th Trampoline from Trampoline 1~i-1.When we come to think about the i-th Trampoline, the first thing we need to do is to add ans with max(0,S(i)-tmp(i)-1), because we can jump tmp(i) times for free.The next thing we should do is state transition, we should add the tmp(i+2,……,i+S(i)) with 1. tmp(i+1) should be specially handled---add it with max(0ll,tmp[i]-(S[i]-1))The more detailful things are in my code
 » 19 months ago, # |   +3 A nice contest.Although it's the first global round I participte in, I perform as good as I expected before the contest.The first four problems are a little harder than the first fours in the Div.2, and I had a difficult time trying to solve D. (I AC D before the contest ended by 5 mins)This shows me I still have a long way to go, so I will continue to work hard and improve myself.Hope everyone can enjoy the contest!
•  » » 19 months ago, # ^ |   -8 And stay cheeki breeki™️
 » 19 months ago, # |   0 [problem:B] In the statement n is "<= 100", but I can't pass. After I set N as 1e7, I get AC. And in the Tutorial, N is 1e6. So I think the data is different with the statement.
•  » » 19 months ago, # ^ |   -11 HereIt always wonders me how can be some experts are so intellectual.
 » 19 months ago, # |   0 Problem F : As all the previous answers are 0, it's easy to prove that the magnet we found is the second one we have selected.Is there anyone who can proof it for me?
 » 19 months ago, # |   0 Problem D is beautiful. Learnt a lot. Thanks!!
 » 19 months ago, # |   0 In problem D, I was not able to prove that if v has smaller or equal no of set bits than u where v>u then we can always reach to v. Can somebody help me in that?
•  » » 19 months ago, # ^ | ← Rev. 3 →   +3 What you are saying is necessary but not sufficient.For example take (in binary) u = 001001001 and v = 010000011 , clearly v>u and number of bits in v is equal to number of bits in u , but you cannot reach v from u.We can reach v only if number of bits occurred till position $i$ in v is less than or equal to number of bits occurred till position $i$ in u and v>=u (sufficient condition).One of the way we can approach the proof is that we can shift the bits of u any distance toward left but above condition must hold because whenever we add the subset it increases the u and shifts it's bits toward left by one and may cause some of bits disappear because of adding (they become carry).00001100011 + 00000000011 = 00001100110 . Here we can see first two bits shifted toward left by distance 1.00001100011 + 00000000001 = 00001100100 , here we can see that second bit shifted toward 3rd position and first bit disappeared .
•  » » » 19 months ago, # ^ |   0 Thanks, it's a saviour
 » 19 months ago, # |   0 Pekora and Trampoline — O(n) Solution
 » 19 months ago, # |   0 Hi there,Could I get some help with TLE for E?108832717It should have the same complexity as what the editorial says. Is it because I use recursion for my findSplit function?Thanks!
 » 19 months ago, # | ← Rev. 2 →   0 .
 » 19 months ago, # |   0 VideoTutorial for (A + B) = https://www.youtube.com/watch?v=AHrgCvgeXo0
 » 19 months ago, # |   0 Is there any proof for problem E that Fib-tree can be partitioned within at most 2 ways.
•  » » 19 months ago, # ^ |   +3 You can notice that parts of size $F_{n - 2}$ must be disjoint (otherwise it would imply $2F_{n-2} \geq F_{n}$, which is false). Therefore number of partitions is bounded by $\lfloor{\dfrac{F_{n}}{F_{n-2}}\rfloor}$.
 » 19 months ago, # | ← Rev. 6 →   +10 I added some pictures to explain the proof of E. For a Fib-tree, there are two cases. In one case(see picture below, that's the case described in editorial), there are two ways to cut the tree, both ways are valid.In another case(see picture below), there is exactly one way to cut the tree: cut "First Edge" first, then cut "Second Edge". In this case, "check $F_{n-1}$ or $F_{n-2}$" also works: if tree root is in left two parts, we will find a subtree consists of $F_{n-2}$ vertices; if tree root is in the right part, we will find a subtree consists of $F_{n-1}$ vertices.
 » 19 months ago, # |   0 "exchange argument" .How it is used in C? please anyone explain the proof. I can't understand.
•  » » 19 months ago, # ^ | ← Rev. 4 →   +8 Exchange argument is a greedy proof technique that is to show that we can turn any optimal solution into one that our greedy algorithm will produce and it will do no worse. Here we want to show that it is optimal that for each pass, the trampoline that Pekora will start at is non-decreasing.In the editorial, we have shown that swapping the sequence of any $2$ consecutive passes does not change the final outcome of the strengths of the trampolines. Therefore, by performing a series of swap, we can sort $P$ (or you can think of it as bubble sort) for any arbitrary optimal solution $P$.For a concrete example, suppose an optimal solution is $P=\{3,1,4,1,5\}$. Using our proof, we can say that $\{3,1,1,4,5\}$,$\{1,3,1,4,5\}$,$\{1,1,3,4,5\}$ are all optimal solutions.
•  » » » 18 months ago, # ^ | ← Rev. 4 →   0 Can you prove the claim 2 of that please? I'm very much frustrated for proving that. As this question seems to have so many transition state that it confuses me to find the Optimal one. I have doubt where we take higher magnitude element and decrement all the elements using this to reduce number of passes rather than wasting this higher magnitude element on some right elements who already have became one. Seems like some invariant is behind the walls at work as I analyze it more!Also how people come up with a solution of questions like these in such short time without actual proof? by intuition ?
 » 19 months ago, # |   +10 With respect to problem C: Pekora and Trampoline, I implemented the $O(N^2)$ solution. However, I still got TLE. In my opinion, an $O(N^2)$ algorithm would amount to elementary operations of the order of $10^8$, which should be executed in under $2$ seconds. I have attached my code below.My codeIf my code is inefficient, please do recommend suggestions. Also, I am aware of the $O(N)$ solution but I would like to first implement the $O(N^2)$ solution as it was explained in the editorial that such a solution should also pass the test cases.Also, please do think before downvoting, and if you still decide to do so consider also informing me what was lacking or offensive in my comment. I have been given a contribution of $-1$ due to a post of mine but I'm still not able to figure out what was wrong. Due to my negative contribution, I have to face a lot of embarrassment. I hope you understand.
•  » » 19 months ago, # ^ |   +20 long s[3000]; long pref[3000]; Why set your array size to $3000$ when $n$ can be up to $5000$?After changing this it got AC.
 » 19 months ago, # |   0 I don't understand in problem D, why do we have to start checking from LSB instead of MSB ?
•  » » 19 months ago, # ^ | ← Rev. 6 →   +13 You can do both, implementation wise checking and matching from LSB is easier. Check out these submissions : LSB's : 109403908MSB's : 109404715
•  » » » 19 months ago, # ^ |   +13 Thanks unusual_wonder !
 » 19 months ago, # |   0 Python code for question C in editorial gives TLE! : ) But why so ?
 » 19 months ago, # |   0 1491G — Switch and FlipCode (C++)//雪花飄飄北風嘯嘯//天地一片蒼茫（a Chinese song named "A Spray of Plum Blossoms"）
 » 18 months ago, # | ← Rev. 3 →   0 .
 » 18 months ago, # |   +3 I wonder how to construct test cases that need $O(n^3)$ moves to solve, in Ruler Of The Zoo.BTW, here are two hacks.This hacks rainboy : 4 2 1 12 11 3 6 7 4 8 9 5 10 and this hacks huzhaoyang: 4 2 1 8 11 3 4 12 5 10 7 6 9 
•  » » 18 months ago, # ^ | ← Rev. 2 →   +10 I guess if if after $n-1$ moves all the reds move anticlockwise once, then you can probably do this for $O(n)$ times before an event occurs. This in total takes $O(n^2)$ time for an event to occur.If we have a lot of REDs, we can make only the last one trigger at the last set of $n-1$ moves, this will take $O(n^2)$ moves to occur. Then, since we insert a new BLUE into the belt, we can use this new BLUE to trigger the 2nd last RED, which will require a total of $O(n^2)$ moves again. Doing this for all $O(n)$ REDs will require $O(n^3)$ moves.
•  » » 18 months ago, # ^ |   0 Thank you for hackTo construct test cases that need $o(n^{3})$,I think we can make even positions RED, and then make them NONRED from right to leftMore specifically,let Ai,Bi and Ci at odd position be large enoughFor even positions,$A_{i}=10i$,$B_{i}=A_{i-2}-1$,$C_{i}=B_{i}+1$（In particular, \$B_{1}
 » 16 months ago, # |   0 Given python code from problem A doesn't fit your time limits.
 » 5 months ago, # |   -10 I'm sorry for posting this late, but I really need help on problem D. I have a solution but it WAs on token 644 My approach is to try to add the powers of 2 in the binary representation of (v — u) to u from left to right If the bit in both u and v — u is 1 then I add that power of 2 to u and then move towards the left to see if a new bit has been set to 1 that wasn't able to be used before If that bit can be used, add the respective power of 2 and keep moving left The second case is if the bit in u is 0 and if the bit in v — u is 1 Then I used a set to store that that index hasn't been used, next time I reach case 1, I'll be able to use that information to see if I need to use a previous bit Here's my submission: https://codeforces.com/contest/1491/submission/154037118Is my logic wrong or do I just suck at implementation?