BLUmOOn's blog

doubt in problem 1677A-Tokitsukaze and Strange Inequality and unable to understand from editorial
By BLUmOOn, history, 2 months ago, In English

kindly help in problem 1677A - Tokitsukaze и странное неравенство,i dont want to use data structure like fenwick tree.I tried to understand it from editorial but am unable to.

  • Vote: I like it
  • -7
  • Vote: I do not like it

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

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

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

Fix indices a and c such that $$$p_a<p_c$$$ as given in the condition. Then count the number of inversions in the range [a+1,n]. This can be precomputed for all values of a in $$$O(N^2)$$$ or can also be calculated individually for each a as you traverse using an ordered_set or segment tree in $$$O(NlogN)$$$ for each a, resulting in a total of $$$O(N^2logN)$$$. Even though, I doubt that the second approach will pass the given constraints or might just barely manage to escape TLE.

Let the number of inversions in range [i,j] be denoted by $$$Inv(i,j)$$$. Even without precomputation Inv(i,j) can be calculated in $$$O(NlogN)$$$ as mentioned above.

Now, for each index a, the Inv(a+1,n) will contain pair such that both b and d lie in range [a+1,c] or both lie in range [c,n]. Since we want to avoid those cases as it violates the condition $$$a<b<c<d$$$, we subtract $$$Inv(a+1,c)$$$ and $$$Inv(c,n)$$$ from $$$Inv(a+1,n)$$$.

Hence the final answer will be

$$$ \displaystyle \sum_{a=1}^{n-3}\sum_{c=a+2}^{n-1} Inv(a+1,n)-Inv(a+1,c)-Inv(c,n) [p_a<p_c]$$$
→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for the reply,what are u defining inv(i,j) to be?Won't subtracting inv(a+1,c) mean we are subtracting some pairs of (b,d) that would instead should have been counted.

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

      No, if we count pairs of inversions in the range [a+1,c] that would just mean we are counting all those pairs of {b,d} which satisfy $$$b<d$$$ and $$$p_b>p_d$$$ and lie in range [a+1,c]. But this means that, $$$a<b<d<=c$$$, which violates the condition on indices.

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

        what is inv(i,j),please define it

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

          inv[i,j] = count of all pairs x, y in the range i, j st x < y and a[x] > a[y].

          we are fixing one of the conditions iteratively (a and c) now we only need to handle b, d. we actually need inversions in st one the element of the pair lies inside the range of a and c and the other one lies beyond c. We can calc it as he clearly explained the his first commen. You only need to precompute the inversions in range. As for the preconputation you can follow a strategy of picking an inverted pair i, j and using a 2d difference array to update all the subarrays where both of these indices come. You initialise the difference array such that the prefix sum of it will add 1 to the region where its row <= i and column >= j. At the end prefix sum the entire difference array to obtain your precalculation of inversions in n^2

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

            can u please elaborate on how u calculated inv(x,y),rest all i have understood.how can i precompute no. of pairs {x,y} in range[i,j] st x<y and a[x]>a[y]

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

              I have explained exactly that in my comment above, anyway here 280160949 is an implementation of the problem, study the part where I use difference arrays to calculate the inversions in range.

              You might wanna familiarise yourself with 2D prefix sums.

              → Reply