antonis.white's blog

By antonis.white, history, 3 years ago, In English

Problems were authored and prepared by:

A: KAN, dimatimoshin23, kirill.grachoff, antonis.white

B: kirill.grachoff

C: napstablook

D: antonis.white

E: antonis.white

F: Denisson

G: antonis.white

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • -186
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Problem E can be solved head-on with a treap or pb_ds

Appeal to antonis.white: Congratulations, you were able to come up with a problem for your super data structure!

»
3 years ago, # |
Rev. 2   Vote: I like it +40 Vote: I do not like it

Questions about problem D:

1. What is an even permutation?

2. How to check whether a permutation is even?

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Tutorial for F got missed, I guess. Could you please update it?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +41 Vote: I do not like it
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh demn. The exact same question! Thanks though!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      This problem can be solved in O(n * log(A)) using implicit segment tree 138937301, lets dp[i][j] = good array that ends in position i with a[i] = j, dp[i][j] = sum of all dp[i — 1][k], where k != j. dp[i][j] = sum(dp[i — 1]) — dp[i — 1][j]. So our dp changes linear, and sum changes linear so we can use seg tree

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What does implicit segment tree do?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How do you subtract $$$dp[i-1][j]$$$ in this approach?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          My tree contain layer of dp(dp[i] and dp[i-1] the same tree) i want apply dp[i] = f(dp[i]) on range, where f(x) = kx + b, for i in [0, a[i]], b = sum(previous dp layer), k = -1, and for i in (a[i], 1e9], k = 0, b = 0

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hi, do you know of any educational material that explains exactly how you can apply a function (not necessary linear) to a segment tree? I've heard it is possible using multiple segment trees somehow.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          With lazy propagation, and k1(kx + b) + b1 = (k1*k)x + (k1*b + b1), so we can apply one linear function to another

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Really enjoyed solving problem C.

»
3 years ago, # |
  Vote: I like it +78 Vote: I do not like it

For E it is necessary to explain how to come up with an idea of the solution.

Just spitting out some implementation details is not an editorial. Who did not solve the problem does not understand that.

On the other hand, the goal of an editorial should be to explain the problem to participants not having solved it.

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Another way of approaching problem D:

If all elements of the array are distinct, find how many swaps it is away from being sorted. If number of required swaps are even, the answer is YES, else, it is NO.

This can be done by making a copy of the array, sorting it, and comparing the initial array and the sorted array to find out total swaps.

Code: https://codeforces.net/contest/1591/submission/138907414

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there any proof of why this works or just intuition.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      An even permutation is that which can be decomposed into even number of transpositions. A transposition means a two cycle or in simpler terms a swap between two terms.

      eg. (1 2 4 3) is an odd permutation and can be written as (3 4) (it mean 3rd term maps to 4th term and vice versa, also rest terms map into themselves and hence are not written).

      A sorted permutation is an even permutation (all the terms map into themselves and identity is even) and so the given permutation has to be even because then only it can be converted into sorted permutation using three cycles (or 2 transpositions as (1 2 3) can be written as (3 1) (1 2) read from right to left). Therefore even number of swaps imply that the given permutation is composed of even number of transpositions, therefore the permutation is even.

      Note:-(1 2 3) means 1 maps to 2, 2 maps to 3 and 3 maps to 1. (3 1) (1 2) mean 1 maps to 2, 2 maps to 1 which maps to 3 and 3 maps to 1 and hence both (1 2 3) and (3 1) (1 2) are same. Think it as composition of functions!!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, this article will give a help in case someone wants to calculate minimum swaps. Article

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you guys recommend any article about problem D? Or can somebody come up with a simpler explanation without diving into too much technical language? I can't understand it with my current knowledge.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Observe that when you choose three indices , such that all 3 elements at these indices are distinct , the parity of their inversion count doesn't change ( Parity means even or odd no. ) . When two elements are equal , inversion count can decrease by 1. So leading yess for all cases with duplicate value.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can u please give an example for the above explanation. I did not understand the statement "the parity of their inversion count doesn't change".

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Parity of the inversion count doesn't change means that , if the no. Of inversion in current permutation was x , and after applying the operation it is y , then x%2=y%2

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          How about permutation 3 2 1? Its parity of inversion count is 2 % 2 = 0. After apply operation, it becomes 1 3 2 and parity is 1 % 2 = 1.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            The inversion count for 3 2 1 is 3, and the inversion count for 1 3 2 is 1.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how does a rotation doesn't change the parity of inversions?? Lets say we select 3 indices i, j, and k (i<j<k) and rotate them ...i...j...k... -> ...k...i...j then order of all the elements from i to k — 1 wrt k changes..same argument can be made for i and j

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Not to disrespect but I think giving only the Code for E would have been better than this quality of Editorial .

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Am I the only one who had the idea of C right, but insisted on looping from origin? 138917782, I kept trying to handle this case instead of simply looping from the farthest point:

Test

After the contest, i saw the idea of solution in comments so i reversed the loop and it was so much easier 138926142, I learned a good lesson though :D

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a question about D. If we have n = 5, k = 4 and the sequence (1, 2, 3, 4, 5) best ans is 11 (we go to 2, 3, 4, 5 then go to 0 then go to 1), but when i follow gaven solution i get 13 (1, 2, 3, 4 then 0 then 5). Can anybody explain me, where i am wrong?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you misunderstood the editorial. The best answer is 7. You would add the highest number of each group of 4 starting from the highest. So first, we would look at the 4 highest (5,4,3,2), add add the highest number from that group which is 5. THen we look at next 4 highest (only 1 left) which is just 1. So we get 6. We multiply it by 2 because we must also go back, which is 12. Then, we subtract the highest value (5) because we don't have to go back for the last time we leave 0. So the answer is 12-5=7. for that example with n=5,k=4.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Question about D. The tutorial says that problem D can be solved in some methods with O(n) complexity. So how to calculate the parity of a permutation in O(n) complexity. The BIT and CDQ are both in O(n log n) complexity. Or is there any other method to solve D without calculating the parity of a permutation.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can use DSU

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Also, you can solve this using DFS.

    Suppose we have a permutation

    -> 2 3 1 5 4

    -> 1 2 3 4 5 (index)

    If you create a graph you'll find some cycles. Here we have 2 cycles.

    2-> 1 -> 3 -> 2 and 5 -> 4 -> 5

    Here the first cycle has length 3 and the second cycle has length 2.

    We can always sort any cycles having odd lengths using the operation described in the problem. So the number of cycles having odd lengths doesn't matter. On the other hand, If the number of cycles having even length is even then we can sort them otherwise we can't.

    So if we have an even number of even length cycles then the answer is yes otherwise no.

    You can find the length of a cycle using dfs.

    Code

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did you come up with this approach? Is this a well known concept? Where can I learn more about this?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +6 Vote: I do not like it

        Basically, here I'm checking whether a permutation is even or not?

        Firstly, you need to know about The Number of Transpositions in a Permutation and Even and Odd Permutations and their theorems.

        In the second link, you'll find a theorem.

        Theorem

        From the first link, you'll know that number of transpositions from a cycle = length of the cycle – 1.

        So if a cycle's length is odd means the number of transpositions from it is even. Similarly, if a cycle's length is even means the number of transpositions from it is odd.

        Now, in order to be an even permutation, a permutation must have the odd number transpositions cycle even number of times. (as mentioned in the theorem)

        So, a permutation is even if it has odd number transpositions cycle even number of times means the even length cycles must be present even number of times.

        (I hope I didn't make it complicated.)

        I don't think it's a very well-known concept. I learned it yesterday. A large number of participants solved it using inversion count.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, I can't figure out why these groups generate all the even permutations of A. How could it lead to all? Stunned.

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +9 Vote: I do not like it

    Even permutaion can be represented as composition of even number of transposotion. We will divide this representation on pairs and change their by on this rules:

    ($$$i$$$ $$$j$$$)($$$i$$$ $$$j$$$) = "can be removed at all"

    ($$$i$$$ $$$j$$$)($$$i$$$ $$$k$$$) = ($$$i$$$ $$$k$$$ $$$j$$$)

    ($$$i$$$ $$$j$$$)($$$k$$$ $$$t$$$) = ($$$i$$$ $$$j$$$ $$$k$$$)($$$j$$$ $$$k$$$ $$$t$$$)

    This way we got a representation of each even permutation as composition of $$$3$$$-cycles.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Got it. So I can always use 3-cycle to decrease the number of reverse pairs by 2! thank u :)

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have another solution for problem D.

First, consider the "reverse pairs" which means a pair $$$(a_i, a_j)$$$ where $$$1 \leq i < j \leq n$$$ and $$$a_i > a_j$$$. For any sorted arrays, the number of reverse pairs is zero.

It's easy to find that if the n elements in the array are distinct, then in each operation we can cancel 2 pairs. So we can calculate the number of reverse pairs. If the number is even then the answer is Yes; on the contrary, the answer is No.

But if some elements in the array are the same, we can move the same elements so in an operation. So in this case, for each operation, we can cancel 1 or 2 pairs. So the answer will be always Yes.

To calculate the number of reverse pairs, we can use the merge sort algorithm in $$$\mathcal{O}(n \log n)$$$ complexity.

Code here. https://codeforces.net/contest/1591/submission/138947313

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great solution bro. Btw I found the reverse pairs using ordered set

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

could someone please give the solution to problem c for the above approach

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my solution

    hope it's useful :)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      btw mx is the last depot we go so we don't need to turn back to origin 0. so we should maximize mx to have the minimum anwer.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It was necessary to try to make all three qualifying rounds of the technocup as terrible as this one

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Damn I thought C was about dp, but the next day I realised it could be solved greedily. I thought about test cases like $$$[1,2,3, 1000, 1001]$$$ and $$$k = 2$$$ and basically whenever I stayed there's only two options: return back to $$$0$$$ coordinate to retrieve resources or continue to supply the depots. Nevertheless, I was wrong and these two options could be proccessed without any recursion. I guess, I will try to solve this problem after the contest.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What if in Problem D the question had 4(or x) cycles instead of 3. Would it have similar logic?

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I my self struggled to understand the logic behind problem D but after some thinking i tried to prove the logic of this code.

So i am sharing my some notes which might me helpful to understand the solution.

PROBLEM D EXPLAINATION
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

где разбор задачи f?

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why my solution for problem E is giving MLE?

Edit: NVM, it's because of the deque. C++ Deque is taking a huge amount of space, don't know why.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1591/submission/138958298

https://codeforces.net/contest/1591/submission/138922744

Same submission after removing #pragma passes.

Is there a guide on when to not use pragmas and when to use them ?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone link something (like a complete guide or something) to understand problem D. Some comments said this is a well-known problem/theorem?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    You can look for definitions here.

    That's why $$$3$$$-cycles generates group of even permutations: link

    That's how to find parity of permutation in O(n): link

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone solved poachers ?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by antonis.white (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Great set of problems, very glad that I've participated in this round. I find solution in D pretty cool, at least it's better what I've submitted:)

»
3 years ago, # |
  Vote: I like it +104 Vote: I do not like it

Attention!

Your problem 1591F. Non-equal Neighbours significantly coincides with problem arc115e — LEQ and NEQ. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your problem). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.ml/blog/entry/8790. Such violation of the rules may be the reason for downvoting your article or other penalties. In case of repeated violations, your contribution may be low.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone provide a more noob-friendly editorial for D? Thank you.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please explain the solution for problem D. As in what is the method and why should it work for every possible case?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by antonis.white (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

1591E - Frequency Queries

O(n+q) 139128594

O((n+q)log(n)) 139132580

Second solution actually got smaller run time xD

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    would you explain both the solution because I am not able to understand the editorial.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Consider sorted array of frequencies :

      frequencies:               0 0 0 0 1 1 1
      number that has frequency: 1 5 2 4 3 7 6
      

      (this is example)

      Now to increase frequency of x= 5 you want to do following:

      ***

      0 0 0 0 1 1 1

      1 4 2 5 3 7 6

      (you swap 5 with last number that has frequency same as 5 (in this case 0), this is also position before the first position of some number with frequency of x+1 (in this case 1)) And then:

      0 0 0 1 1 1 1

      1 2 4 5 3 7 6

      You increase the frequency of 5 and now array stays sorted while you used only 2 swaps.

      This is main idea, now to make it work you need:

      lb[i] — same as in editorial, you can use this to find position before first position in array that has frequency >= than some i

      p[i] — actual array that we are storing (in first example the array 1 5 2 4 3 7 6), you need this in order to answer queries in O(1) as you can just find required value at some index in array, also you need this to know which element is at some position so we can swap it

      p^-1[i] or i call it pos[i] — this stores where is i located in above array (p) (it's position)

      example: if array p = 4 2 1 3, pos[4] = 1, pos[3] = 4, pos[2] = 2, pos[1] = 3

      you need this because you should find where is X located in array so you know which positions you should swap when doing step "***"

      So with these values you can answer queries fast, and also recalculation of these values are pretty easy and fast (O(1))

      The logN solution is same as this, only without the lb[i] array because I wasn't sure if I would come up with that idea, so I used different method that I am more familiar with:

      Keep track of first[x], last[x] (first and last position so that position has frequency x), set ok which stores which frequencies we actually have, this is used when answering queries to find first position with frequency >= L

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone please explain the n^2 idea for 1585F in more simpler terms? I couldn't understand what will be the answer after computing dp[N][0] and dp[N][1].

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    +) |A|, |B|, |C| here alternate mean the number of ways to build array such that a[1] = a[2], a[2] = a[3], a[3] = a[4].

    +) S mean the total of ways to build the array ( I don't now call it in set stuff lol )

    I believe this picture will help you if you already know basic inclusive-exclusive.

    Notice that it will be opposite when n is odd.

    Update: Sorry for who saw the picture before this edit, I was misspeltt intersection and union signs

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And how do we get S ?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        It's already count in dp[n][0] if n is even, or in dp[n][1] if n is odd.

        S is one of the ways to separate the array to have odd (or even depend on n) equal segments.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for explaining with a diagram. dp[i][0]+=dp[j−1][1]⋅f(j,i)

      dp[i][0] means ending at i with even number of segments right? and we are calculating it as selecting some j and saying j->i forms one segment and till j-1 form odd number of segments.

      But how are we making sure whatever number we are putting in j-> i is not in the last segment formed till j-1?

      We are saying till j-1 we need odd segments but the last segment can contain any number which may collide with our choice of j->i making count as odd for dp[i][0]?

      or am I missing something here?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        No bro, between segments didn't have to be different, we just separated the array into segments, that it.

        A is the number of ways such that a[1] = [a2], but it doesn't mean that A will not contain values such that satisfied B or C, that's why we have to use Inclusive-Exclusive bro.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks a lot bro! Finally able to understand it

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, that's a great explanation!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    With the help from cqtshadow, Finally I understood the application of inclusion-exclusion principle here. Adding few more details here to help someone new to inclusion-exclusion principle.

    Let the given numbers be A1, A2, ..... An.

    We can calculate the answer as Total ways(T) - invalid ways(I) where T = A1 * A2...*An and I = number of sequences with atleast one index i with Ai == Ai+1

    Inclusion Exclusion comes into picture to calculate I.

    Denote Ei is event where Ai=Ai+1 i.e there are n-1 events and I = E1 U E2 .... U En-1

    $$$ I = \cup_{i=1}^{n-1}E_{i} = \sum_{i=1}^{n-1}E_i - \sum_{i=1}^{n-1}\sum_{j=i+1}^{n-1}E_i \cap E_{j} + \sum_{i=1}^{n-1}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n-1}E_i \cap E_{j} \cap E_{k} ....$$$

    $$$ ans = A1*A2*..*An - \sum_{i=1}^{n-1}E_i + \sum_{i=1}^{n-1}\sum_{j=i+1}^{n-1}E_i \cap E_{j} - \sum_{i=1}^{n-1}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n-1}E_i \cap E_{j} \cap E_{k} ....$$$

    Here notice the lengths of all positive terms and negative terms. If n is odd, all positive terms are odd length and negative terms are even length(viceversa if n is even). Hence we can group them and get 2d dp.

    Wrote a n^2 solution (although TLE) to check my understanding https://codeforces.net/contest/1585/submission/139689924

    (Do check the figures from cqtshadow to come up with the base cases)

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I was not clever enough to realize the even cycles argument. There's an easier way, though (or at least, I think it's easier).

The first idea is the same as the editorial's: if we ever have a repeat element (i.e. an element which appears >= 2 times in the array), then we can always sort it.

Now, some elements are out of place. For example, if we take the array [2, 3, 1, 4, 6, 5, 7], then five elements are out of place (those out of place are bolded). We can ignore elements that are in their proper places, since they won't affect the answer. At least, it would make sense if we start by cyclically shifting the elements that aren't out of place.

With this in mind, we know that we want the first element to be 1. Since the first element is actually 2 in the aforementioned example, we should cyclically shift the 1,2, and any other arbitrary element (it doesn't matter which one). This will put 1 in its proper position. Since 1 is in its proper position, we can ignore it from here on out. Depending on the arbitrary third element of our choice, our new array could be [1, 3, 7, 4, 6, 5, 2]. So now, the 2nd element is out of place, so we should swap the 2, the 3, and some arbitrary third element. And so forth (I think you get the idea).

The solution is surprisingly straightforward to implement if you keep track of the index of occurrence of all elements in the vector.

Code is here: 139441826

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

    Thank you so much for the explanation!

    I was trying to solve the problem using a really similar logic (ie. trying to sort the array in a "greedy" way, fixing the first position, then the second, then the third... until the (n-2)th position. But I was missing the "if we ever have a repeat element then we can always sort it." part. Reading your comment made me realise that.

    Following this same logic, I'm still trying to figure out the reason we can always sort the sequence if there are any duplicates. One of the reasons I could think of was that by the end of the operations we end up with the last elements being something like "x y x" in which x < y. So in this case, even if the first x is in its correct position, we still need to apply a shift, to get "x x y". That being said, this reason is not sufficient, as can be seen in this commit (see line 91).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sorry for necro-commenting but there is a problem G in Technocup 2022 — Elimination Round 3. there seems to be no editorial nor any mention of it among the comments.. would the editorial for it be added?

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    Sorry, I forgot to translate editorial as there wasn't any rush to post english editorial for this problem.

    I will do it right now.

    UPD: Done.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by antonis.white (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I only know the solution of F using segment tree and it's very complex