BLUmOOn's blog

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

kindly help in problem 1677A - Tokitsukaze and Strange Inequality,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
  • -3
  • Vote: I do not like it

»
4 hours 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
»
101 minute(s) 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
  • »
    »
    73 minutes 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
    • »
      »
      »
      59 minutes 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