TCS_Bhediya's blog

HELP needed ordered set *1400 problem
By TCS_Bhediya, history, 2 hours ago, In English

I'm trying to solve this problem Problem link using ordered_set, but not getting AC. My logic is, since we have to find number of pairs (i, j) such that i < j and a[i] + a[j] > b[i] + b[j], we can rearrange it with finding number of pairs (i, j)such that i < j and a[i] - b[i] > b[j] - a[j]. Submission : 290047609

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
94 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

you don't need ordered set
let $$$x[i] = a[i] - b[i]$$$
then the equations transforms to $$$x[i] + x[j] > 0$$$
now in array $$$x$$$ you just have to no. of pairs having $$$sum > 0$$$
to do this you can sort the array and use two pointer to find for each $$$i \ max \ j$$$ such that $$$j >= i$$$ and $$$x[i] + x[j] <= 0$$$ contribution of $$$i$$$'th index is $$$n - j - 1$$$
290052928

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

    Yes, it's another way to do so, but I want to know why this solution is not working.

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

    Also, i don't think the order of index matters here, because x[I] + x[j] > 0 is same as x[j] + x[I] > 0.

    → Reply
»
79 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Your solution is true but you're missing that ordered_set (as can be understood from the name) is deleting multiple same values. In this solution you need multiple same values so you need to use multiset.You can transform ordered_set to ordered_multiset with just changing "less" part to "less_equal" and now you can use all the funtions that you just used in ordered_set.

Your submission with ordered_multiset : 290053589

And you can learn more about policy based data structures from the following blog :

(https://mirror.codeforces.com/blog/entry/11080)

Spoiler
→ Reply
  • »
    »
    71 minute(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much, bro. I am so dumb to remember that the set only stores distinct values.

    → Reply