A — Constructive Problems

Author: valeriu

B — Begginer's Zelda

Author: valeriu

C — Largest Subsequence

Author: tibinyte

D — Cyclic MEX

Author: tibinyte

E — One-X

Author: tibinyte

F — Field Should Not Be Empty

Author: tibinyte

• 4 days ago, # ^ | the same with problem A

• 35 hours ago, # ^ | In problem C my method has utilised O(n) complexity and yet it is giving tle at last test(9). please look upon this..237829405

  • 24 hours ago, # ^ | v.insert(...) runs in O(n) time. I can offer deeper feedback if you rewrite your code in a more readable style

    • 20 hours ago, # ^ | yah,i realised that btw thanks...my codes are horrible lol

• • 3 days ago, # ^ | omg gray comment...

    • 3 days ago, # ^ | people when there is no alts

• 3 days ago, # ^ | ratism?

• 4 days ago, # ^ | If the largest subsequence is zzzba for example, the number of operations would be 2. Total length is 5 and the largest prefix of equal values would be zzz This is because after two operations, the largest subsequence will be zzz and further operations will be no-op.

• 3 days ago, # ^ | Used the same idea, except the only candidates for subtree sizes are and . So this actually gives per test case (assuming you merge in constant time).

  • 3 days ago, # ^ | ← Rev. 2 →   -16

    • 3 days ago, # ^ | What I've written was , and you can't simplify the way you did. Maybe I should've written in the first place, but nevertheless.

      • 3 days ago, # ^ | ← Rev. 3 →   +14 oh, I see. but isn't number of different subtrees actually ?

        • 3 days ago, # ^ | ← Rev. 2 →   +9 According to ToniB that is true, but I don't have the proof yet, so I'm not too keen on believing this. Actually, I might've found counterexamples, but I'm not too sure. UPD. Tried to test out different values of , and found that it is, indeed, true, and my counterexamples were wrong.

  • 3 days ago, # ^ | Actually, if it really is the bound, then my solution also checks at most different subtrees per test case. However, I don't really know how to formally prove that it is really the case. Can you share your proof?

    • 3 days ago, # ^ | ← Rev. 4 →   +11 for any : , , and have at most 2 unique values, and they are also some and so for every depth of the tree we have at most 2 unique ranges. so max number of different subtrees is

    • 3 days ago, # ^ | ← Rev. 2 →   +19 For any you can see . Now you prove by induction. Suppose where is a subtree size on -th layer from the top. Using the inequality above, you get which simplifies to Since these are the only possible sizes of subtrees in the next layer, the next step will also hold. Base case is trivial. UPD: or just what ibrm said, looks simpler.

• 3 days ago, # ^ | Can you explain more clearly how to construct this formula: f(v) = kv + b Thank you!

  • 3 days ago, # ^ | ← Rev. 3 →   +13 Well, firstly, suppose we have some subtree of size , and by induction for trees of size smaller than we already know their linear functions. Then what is the answer for this subtree (LCA is some vertex of this subtree)? LCA(S) = only in subsets, for which there is at least 1 leaf from the left son, at least 1 leaf from the right son, and there are no leafs besides this subtree (or LCA would be some ancestor of v). For a tree of size left son has the size , and right son has the size . Then there are subsets for which LCA is . Now we need to calculate the answer for the case when LCA is equal to some vertex in the left or the right son. Because by induction we already know what formula of the answer for the left and right son is, we have , . Then the answer for the left son is , and for the right son. Composition of linear functions is also a linear function (given we have ) Combining everything together, the answer for the subtree is UPD: base for this induction is linear function for subtree of size 1:

• 3 days ago, # ^ | In the last for loop, you have to iterate over lar.size() not n.

  • 3 days ago, # ^ | sweet. i so fking dumb. cant even see shit. thanks

• 3 days ago, # ^ | SegmentTree W

• 3 days ago, # ^ | ← Rev. 2 →   +42 I might have had a different intuition than the Editorial, but i can try. For simplicity, let denote , that is the mex of a prefix of of length . Lets assume . What's the answer? . Because every mex of a prefix will be equal to except the prefix containing the entire permutation. Now, what happens when ? If you try a few cases you will see that the answer in this case is . If then the answer must be . Because for all , and because is excluded from , . as usual. We can see that the mex is until we "hit" the index (where sits). When that happens, mex will become equal to , because that is the only remaining number that is excluded. Using this information, we can build a solution where we consider the positions of where can be in decreasing order. In other words we consider the cyclic shifts in this order (i assume WLOG that ): And so on. The nice thing about doing it this way is that we know that the mex is for all indices before the index of the number as explained above. This way we can think of the operation not as a cyclic shift, but as appending numbers to the end of our list. So our operations really look like this: When appending a new number, we need to consider how it can change our answer. It can be helpful to think about some cases. If we ever append to the end, we know that all mexes will be except the last one, which will be (assuming our simplified view of 'appending to list'). If we ever append a after this, we know we won't change any of mexes before the index of , but between the index of and the index of the mex will be . If you try this for some different cases on paper, it shouldn't be impossible to see that what we need to do when appending a new number, say , is that we must find the index of the last number that is smaller than . I.e. we must find the largest in our list so far such that . Because we will not affect any mexes up to . All mexes between and will then be equal to our new value , because by construction, is smaller than all numbers in this range. Thus, we will update our answer with . Our final answer will be the maximum of all of the answers from each 'shift'.

  • 3 days ago, # ^ | ← Rev. 2 →   0 How do you find the last element smaller than ? Edit: Oh, that's why VectorViking has a monotonic stack. We read the array of from left to right, and at every , we pop all elements bigger than before pushing . Thank you very much!

    • 24 hours ago, # ^ | and anyway in general if you wanna keep track of nextLarger, nextSmaller or prevLarger, prevSmaller you use monotonic stack

  • 3 days ago, # ^ | It's actually the same as the editorial's solution, just changes the order to calculate ans. But your way is more easy to understand, and then we can clearly see that each number would push on and pop out in the stack for at most once, thus the time complexity is O(n).

  • 3 days ago, # ^ | Your maths skill are very good in my case I don't even know why 2 is greater then 1

  • 3 days ago, # ^ | I guess there are some typos after the sentence will then be equal to our new value Those here should be

  • 2 days ago, # ^ | ← Rev. 2 →   0 I tried implementing this solution but idk where is my error. I get the following verdict: 45478th numbers differ — expected: '31', found: '0' even though at the end of my code I output something like , where is always . Here is my code

    • 41 hour(s) ago, # ^ | When n=1 you don't read the whole input

  • 2 days ago, # ^ | ← Rev. 3 →   0 pretty good explanation and the code was clean and easy to understand , got the idea clearly Thanks bro!!

• 3 days ago, # ^ | ← Rev. 2 →   +3 Let's solve the following example: 2 3 6 7 0 1 4 5 We first place 0 at the end: 1 4 5 2 3 6 7 0 What's the cost? It's 8 ( =n ), because everything before 0 adds +0, and at the end there is always +n (we used all numbers from 0 to n-1). Now we rotate the sequence to the left. 1st iteration: 4 5 2 3 6 7 0 1 (cost is 1 + 8) 2nd iteration: 5 2 3 6 7 0 1 4 (cost is 1 + 4 + 8) 3rd iteration: 2 3 6 7 0 1 4 5 (cost is 1 + 4 + 5 + 8) 4th iteration: 3 6 7 0 1 4 5 2 (cost is 1 + 3 * 2 + 8) Why is that? Because now 2 is at the end and we can use it for places where we used 4 and 5 (they are bigger). It's enough to maintain a monotonic stack while iterating, so the solution is linear. You can see my solution at: 237547878. Hope this helps!

  • 3 days ago, # ^ | Why is the cost of the 4th iteration not ?

    • 3 days ago, # ^ | Because the cost is computed as the sum of mex, for each iteration: 0th: 0 0 0 0 0 0 0 8 1st: 0 0 0 0 0 0 1 8 2nd: 0 0 0 0 0 1 4 8 3rd: 0 0 0 0 1 4 5 8 4th: 0 0 0 1 2 2 2 8 As you can see, when we "rotated" 2 from the start of the sequence to the end, it became the new smallest non-negative integer ( mex ) instead of 4 and 5. The third 2 comes from the rotation itself.

      • 2 days ago, # ^ | Thank you!

• 3 days ago, # ^ | ← Rev. 3 →   +12 These were my ideas during the contest. I hope it helps! Idea 1 Idea 2 Idea 3 Idea 4 Source code: https://codeforces.com/contest/1905/submission/237526381

  • 3 days ago, # ^ | can you explain why you do a[i]++ in your code ? Thanks a lot.

• 3 days ago, # ^ | does it matter?

• 3 days ago, # ^ | I've written about floor((X+1)/2), which is practically ceil(X/2) :)

  • 3 days ago, # ^ | If you want to write the floor function properly, you can use (\left\lfloor\frac{K+1}{2}\right\rfloor) instead of .

• 3 days ago, # ^ | ← Rev. 2 →   0 Type cast d.size()-1 to (int)d.size()-1, now u are getting wrong answer

  • 3 days ago, # ^ | It worked, thanks, but can you tell what exactly is causing the problem?

    • 3 days ago, # ^ | Bcoz size() returns an unsigned int, so if used in the loop condition might cause undefined behaviour

      • 3 days ago, # ^ | Ohh alright thanks!

• 3 days ago, # ^ | I think the following line is causing an issue Spoiler

• 3 days ago, # ^ | Found a test case that your solution will fail Test case

  • 3 days ago, # ^ | ← Rev. 2 →   0 thanks a lot.. It got an AC :)

• 3 days ago, # ^ | just to for from 1 to n if you dont have that its from 0

  • 3 days ago, # ^ | thanks

• 41 hour(s) ago, # ^ | https://codeforces.com/contest/1905/submission/237719024 this solution is O(N). I've used hashmap to store the pair of swaps, so that should be O(N) too.

• 2 days ago, # ^ | can you please explain how did you do it?

  • 2 days ago, # ^ | Just replace your segment tree with Treap)))

    • 2 days ago, # ^ | Thank you! I think it was a nice idea. It's much more easier than author's solution!

      • 2 days ago, # ^ | What is author's solution?

        • 2 days ago, # ^ | He used deque.

          • 2 days ago, # ^ | What is deque?

            • 2 days ago, # ^ | It's a treap but you can use only first and last element.

              • 2 days ago, # ^ | ← Rev. 2 →   0 thank you, petarda

              • 2 days ago, # ^ | ← Rev. 2 →   0 you are welcome, traktor.

• 2 days ago, # ^ | ← Rev. 2 →   0 This is so weird. I rewrite your code in Python3 and it passed. 237667769 Update: Found the issue

  • 2 days ago, # ^ | Thanks a lot