thenymphsofdelphi's blog

By thenymphsofdelphi, 18 months ago, In English

1828A - Divisible Array

Idea: thenymphsofdelphi
Preparation: Mike4235

Hint 1
Hint 2
Solution
Implementation 1
Implementation 2

1828B - Permutation Swap

Idea: thenymphsofdelphi
Preparation: Mike4235

Hint 1
Solution
Implementation

1827A - Counting Orders

Idea: Mike4235
Preparation: thenymphsofdelphi

Hint 1
Solution
Implementation

1827B2 - Range Sorting (Hard Version)

Idea: lanhf
Preparation: Mike4235

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Implementation 1
Implementation 2
Bonus

1827C - Palindrome Partition

Idea: lanhf
Preparation: lanhf

Hint1
Hint2
Solution
Implementation
Bonus

1827D - Two Centroids

Idea: Mike4235
Preparation: lanhf

Hint1
Hint2
Solution
Implementation
flowerletter :pensive:

1827E - Bus Routes

Idea: Mike4235
Preparation: thenymphsofdelphi

Hint 1
Hint 2
Solution
Implementation 1
Implementation 2
sorry gamegame

1827F - Copium Permutation

Idea: lanhf
Preparation: lanhf

Solution
Implementation
  • Vote: I like it
  • +183
  • Vote: I do not like it

| Write comment?
»
18 months ago, # |
  Vote: I like it -13 Vote: I do not like it

fast editorial!

»
18 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I was waiting for it

»
18 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Lots of solutions for Problem A. You can also observe that sum(1..N) % N is 0 if N is odd, and N/2 if N is even, so you can construct A=1..N if N is odd, and when N is even it's the same except you change A[N/2] = N.

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

    Here's another one, similar to yours but without odd/even check: [n - (sum(2..n)%n), 2, ..., n]

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

Hi, relatively new here, probably have a dumb question. Coding in python like a real noob. Can anyone explain to me a detail from problem 3, Counting orders. This part of the code specifically.

for i in range(n):; while j < n and a[i] > b[j]:; j += 1; ans = (ans * (j — i)) % int(1e9 + 7); print(ans)

why can't we just write print(ans % int(1e9 + 7) in the last line without having to calculate ans = (ans * (j — i)) % int(1e9 + 7) each iteration? im guessing because ans probably gets too large, right?

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

    Well integer have no limits in python, but when they become big (in this case too big), they will slow down the calculation (calculation with numbers that take less space in memory is faster), which is way you should always apply the mod after each step.

»
18 months ago, # |
  Vote: I like it +50 Vote: I do not like it

I solved D1B1 using DSU, if we fix the start of the subarray we can keep adding an element and find its position in the new sorted array with DSU.

submission link: https://mirror.codeforces.com/contest/1828/submission/205880043

Is it possible to optimize this idea to pass B2

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

    Can you please explain the idea or give any similar problem which uses the same idea?

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

      We divide the current array into non-overlapping subarrays as the editorial, but we also visualise them as connected components (cost of a component is the size-1, minimum time is the sum of costs of all components).

      If we know the connected components of a subarray [L,R-1] then we can find the subarray [L,R] by finding the leftmost component k such that it has a value > a[R], and then connecting R with k and every component after it so after sorting that component R will be in its correct position.

      • »
        »
        »
        »
        18 months ago, # ^ |
        Rev. 4   Vote: I like it +6 Vote: I do not like it

        Can you please tell me what these lines of code are doing?

        Code

        Thanks
        Upd: Got it. Thanks

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        leftmost component i such that it has a value > a[R] 
        leftmost component j such that it has a value < a[R]
        and shouldn't we take leftmost of i and j and merge components between them ?
        
        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          We assume that the subarray [L,R-1] is already sorted, then we just need to add R by shifting the elements greater than a[R] after it, so they have to be in the same connected component as R.

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

    Can u explain the time complexity for the inner while loop(amortised ananlysis) ? Worst case O(n)?

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

      The while loop must stop when there is only one component left (j - sz[get(j)] >= i is true when there are more than one component), and every iteration the number of components decreases by $$$1$$$. So for each $$$i$$$, the total number of iterations is at most $$$n - i$$$.

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

        Thanks with a upvote

»
18 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Typo in Range sorting

We can see that a triplet (l,k,r) with x<l≤k and i≤r<y will match our condition.

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

Div2.C and Div2.D have the same points.But why is D much more difficult than C?

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

    Maybe it's because there are two versions of this problem.

»
18 months ago, # |
  Vote: I like it +28 Vote: I do not like it

For the C bonus:

The only part in the editorial solution that is $$$O(n \log(n))$$$ is the sparse table for finding the minimum length prefix palindrome. This step can be done in $$$O(n)$$$ total instead. Going right to left, we can add the even palindromes with centre at $$$i$$$ to a stack. Now the potentially smallest palindrome is at the top of the stack. So the stack can be popped from, while the palindrome at the top of the stack does not reach far enough. Then the topmost palindrome on the stack must be the minimum prefix palindrome. This is $$$O(n)$$$ amortized.

My submission: 205927403 (I thought instead of removing suffix palindromes, but the logic is equivalent, only reversed)

»
18 months ago, # |
  Vote: I like it +56 Vote: I do not like it

I think we can use 2 stacks for B2, which is $$$O(n)$$$. https://mirror.codeforces.com/contest/1828/submission/205931557

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

    Hey, can you explain your intuition and what your code does it would be very helpful

    • »
      »
      »
      18 months ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it

      It is the same as in editorial. I just optimize the process finding $$$x,k,y$$$. The first stack is to record $$$k$$$ and the second is to record $$$x$$$.

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

    Nice solution!

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

    I couldn't come up with this approach in contest. Thanks for a clever solution!

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

I kinda fucked up D. I knew how to find moving centroids, but for some reason I came up with wrong methods to find maximum size subtree there. So I just gave up and used Top tree to find maximum size subtree of given node. Code

In retrospect either I should not be dumb or I should try to cheese with top trees in the first place

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

Cannot pass Div2 D1 with BIT+Seg unless replacing seg with vector :( .

»
18 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Div2.D1 was equally hard as normal D, then why there is no separate editorial for it ? I want to know how to do it in O ( N ^ 2 ).

If you made two separate problems, then please write two separate editorials for both the problems ( or at least explain something ) .

downvoting for not explaining D1 clearly.

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

    Wow man really just saw the headings, and didnt even bother to read. Look prperly.

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

      I have read it, including the bonus problem where beauty is ( square of min cost ) . not that I can solve that xD

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

        Then why are you complaining? If you read it, you qould see the editorial has nearly same sols for easy and hard version. Why would they make 2 separate editorials when they do not explain anything new.

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

    But in the last paragraph the author has mentioned about the solution of D1.

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

      that's true. they have mentioned, but I am not able to understand last 2-3 para's of editorial. I made a mistake by not reading last para clearly. but even after reading it , I am not able to understand clearly.

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

        it is D1' solution as well. According to the editoral the only difference between D1 and D2 is the last paragraph.

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

    If you don't use sparse table or something like that,you will do it in O(N^2)

»
18 months ago, # |
  Vote: I like it -16 Vote: I do not like it

I have a puzzle question, for example 4 and 2, 1, 4, 3, why is the answer 6

  • »
    »
    18 months ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it
    [2] [1] [4] [3] cost=0+0+0+0=0`
    [2 1] [1 4] [4 3] cost=1+0+1=2
    [2 1 4] [1 4 3] cost=1+1=2
    [2 1 4 3] cost=2
    so the sum is 2+2+2=6
    
»
18 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

can someone explain why (k-x) * (y-i) is added to answer in Div2D1 ?

1

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

    Till para 5, it says that for each [ l ... r ] ( 1 <= l < n , l < r <= n ) , we will find number of 'k's such that each max(a[l...k]) < min(a[k+1...r).

    So, based on this assumption, we would think that

    for(int l = 0 ; l < n-1 ; l++) {
       for(int r = l+1 ; r < n ; r++) {
          // some logic here, which will count number of 'k's which are satisfying (*) in the editorial
          // but suddenly logic changes
       }
    }
    
    

    After this, logic changes on para 6, for each 'i', lets find first left index, which is less that a[i] , lets call that

    index 'k'. ( a[k] < a[i] )

    Now, find first index on the left side of 'k' which is greater than a[i], lets call this index 'x' , ( a[x] > a[i] )

    Now, find first index on the right side of 'i' which is less than a[i], lets call this index 'y' , (a[y] < a[i] )

    so, putting this in code,

    for(int i = 0 ; i < n ; i++) {
    
       // first go on leftside, and find 'k' and 'x' , 
       int k , x;
       k = 0 , x = 0;
       for(int j = i-1 ; j >= 0 ; j--) { // first find 'k'
            if(a[j] < a[i]) {
                k = j;
                break;
            }
       }
       for(int j = k-1 ; j >= 0 ; j--) { // now find 'x' on left of 'k'
            if(a[j] > a[i]) {
                x = j ; break;
            }
       }
       int y = n-1;
       for(int j = i+1 ; j < n ; j++) { // now find 'y' on right of 'i'
            if(a[j] < a[i]) {
               y = j ; 
               break;
            }
       }
       ans = ans + (k-x) * (y-i) // but why are we adding this ??? how does this count 
    }
    

    But why are we adding this (k-x) * (y-i) , how does that count number of triplets (l , k , r) minus 'k' which was proposed in the first 5 paras ?

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

      Why are we adding this (k-x) * (y-i) ?

      2

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

        You need to understand that for a position i, k has only one. max{a[l],...,a[k]}<a[i],where (k-x) is the number of feasible l and (y-i) is the number of feasible r.

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

          I think I understood that part. basically, all the subarrays which are not including x and y, and which are including k and i (both) .

          but how does that help in counting answer ?

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

            The contribution of the subarray a [l, r] to the answer is (r-l)-num, which means we can find num subscripts j, so that max{a[l],...,a[j]}<min{a[j+1],...,a[r]}. The method provided by the problem solution is to calculate the value of num by enumerating a[i]=min{a[j+1],...,a[r]}.

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

            Actually, it is substracted from the answer. For a subarray a[l..r], the beauty is the r - l - count(triplet(l, k, r)).

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

              understood, from total subarray lengths, we are subtracting the triplets which create partitions in subarrays. thanks. got it.

»
18 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Hello, here is a video tutorial/editorial with solutions to these problems: D2B, D2C/D1A, D2D1/D1B1, D2D2/D1B2, D2E/D1C:

https://youtube.com/watch?v=VwY7QzStMk4

»
18 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
D2: i think one can hack this solution as its O(n^2)
https://mirror.codeforces.com/contest/1828/submission/205990252
I just mistakenly submitted without commenting O(n^2) part and suprisingly it got passed.
And i thought using segment tree is overkill for 1 sec and n<3e5 during contest
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there is a typo in D2B solution: Complexity should be: O(n.log n).

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

    The correct complexity is $$$\mathcal O(n + \log n)$$$ — see discussion here and here.

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

      Technically it should be $$$\mathcal{O}(n + \log m)$$$ where $$$m$$$ is the maximum value in the input.

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

        But the input is always a permutation, meaning that $$$m = n$$$ always holds and the complexity is $$$O(n + \log n)$$$.

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

          Good point! You're right. I had already forgotten about that.

          Though it does mean the complexity becomes just $$$\mathcal{O}(n)$$$ because $$$n$$$ dominates $$$\log n$$$ when $$$n$$$ goes to infinity.

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

      Thanks for correcting me.. I was not aware of this amortized analysis.

      So.. Can I say that in our problem: O(n+log M) = O(n+log n) = O(n)

      where M is the maximum element of the array?

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

Great editorial! Really explains the concepts really well! The hints in Div 2 D allowed me to solve the problem without even reading the tutorial, the various ways to frame the problem makes it really interesting.

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

Can anyone explain the solution of problem B? I mean is there any proof that in order to move pi to position i ,|pi-i| has to be divisible by k?(Apologies for not using subscript)

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

    Since any swap between two elements will change their position by exactly $$$k$$$, the distance between the initial position and the final position of each element will be divisible by $$$k$$$ as well.

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

really nice contest

unfortunately i couldn't enter it so I entered virtual

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

the first graph in the 1827C solution should have l before r-l

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

    and i think the second case statement should say t[0...2l-r] instead of t[0...2r-l]

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

first 3 problems were very easy, but i couldn't write this round:(

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

I think ,There is huge difference in difficulty of d than c.

»
18 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Hello, I am new here, I could not solve Div.2 D, but I have a feeling that the number of inversions in the array and the size of the array together can be mapped to the required answer using some equation. for example,

Inversion = 0, we have Answer = 0.

And for max inversion we have,

Answer = summation of (i*(n-i)) from i=1 to n-1.

And the answers for the rest of the values will stay in that range.

While I could not find the function which satisfies this, am I right in thinking this way?

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

lct solution for 1D 206402736

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

Does someone know of a solution for B1 simpler than the one for B2? (probably in O(n^2)).

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

    Obviously we need to beat the answer of $$$\sum_{l=1}^{n} \sum_{r=l+1}^{n} r-l$$$. How do we save time? Well, sorting $$$[L1,R1]$$$ and $$$[L2,R2]$$$ instead of $$$[L1,R2]$$$ saves $$$L2-R1$$$ seconds. We can only split the sort up like this if $$$max(L1...R1)<min(L2...R2)$$$, otherwise some elements will be in the wrong position. So, for each index $$$k$$$, we need to count the number of pairs $$$(l, r)$$$ s.t. $$$max(l...k)<min(k+1...r)$$$. Essentially we are counting the number of subarrays that use index $$$k$$$ as a "boundary point": point where we can save time by dividing the big sort into two smaller sorts. A "boundary range" that we all don't need to sort we can think of as many "boundary points." The final answer is naive answer time — # of boundary points.

    Time complexity: $$$O(n^2)$$$ or $$$O(n^2 lgn)$$$

»
17 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

F without any data structures: 207285734. Took me just 10 hours to solve this problem.

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

    I find that you use divide and conquer. Can you explain your solution?

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

      I used divide and conquer not to solve the problem, but to find some helper array. I wanted to know for every index $$$i$$$ what is the number of segments of the initial array with their right bound at $$$i$$$ that are copiums. I actually have no idea what is the easiest way to solve such a subproblem, and the easiest way I found was d&c.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow magic, how can i train myself to write all these implementations

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ladies and gentlemen, E solution that's $$$O(N+M\log N)$$$ instead of $$$O(N\log N)$$$. As you can see, I'm focusing on the important things. 207457936

At this point, I'm pretty sure $$$O(N+M)$$$ can't be done, but you're welcome to prove me wrong. At least it's $$$O(N+M)$$$ in practice, with the only bad cases being handcrafted to make as many paths as possible get used in multiple depths of recursion. A bit over 1/2 of real runtime is taken up by reading the input and running an initial DFS, so there's not much left to optimise that'd be at least a little bit specific to this problem.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D2 can be solved using simple sorting instead of a sparse table. But the time complexity remains O(nlogn). Here is the solution https://mirror.codeforces.com/contest/1828/submission/211818091

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

Div1-C can also be solved in $$$O(n\log^2{n})$$$ using dsu.

This solution doesn't require the lemma of the editorial, and is based on the fact that if the prefix of any even palindrome is an even palindrome, then the suffix can always be divided into disjoint even palindromes.

(note to self: write complete explanation later)

Implementation: link

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

Cam somebody explain the intuition behind 1828B? I am not able to understand how calculating GCD is the answer. Part about how to find the right pos is obvious but I am not able to understand GCD part.

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

    Since any swap between two elements will change their position by exactly $$$k$$$, the distance between the initial position and the final position of each element will be divisible by $$$k$$$ as well.

    So, a valid value of $$$k$$$ must be a divisor of the difference between all the initial position ($$$i$$$) and the final position ($$$p_i$$$) of each element, which is $$$|i - p_i|$$$. The largest value of $$$k$$$ is thus the greatest common divisor (GCD!) of $$$|1 - p_1|, |2 - p_2|, \dots, |n - p_n|$$$.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi in the 1827A — Counting Orders

why the output for following given test case is 1?

1 2 1

here a=[2] and b=[1] so aren't they already ordered? so it should be zero right?

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

    Sorry for the confusion caused, the original array $$$a$$$ does count towards the answer

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

      Sorry I didn't get. Does that mean the answer should be zero for this test case? input is

      1

      2

      1

      a=[2], b=[1]

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

Can anyone please explain how this 208545125 works for problem div2d1/div1b1 ?