**Inversions Revisited

Inversions Revisited

---

 

• Algorithms
• BIT
• Hard

Most of us know how to count the number of inversions in an array. An inversion in an array is a pair of indices(i,j) such that a[i]>a[j] and i < j.

In this problem you are given 2 arrays A and B and you have to return number of such pairs such that a[i]>b[j] and i < j.

Input Format:

First line contains n denoting the total number of elements.The next line contains n space separated integers of array A.This line is again followed by n space separated integers of array B.

Output Format:

Print the total number of pairs satisfying the above condition.

Constraints:

1<=n<=200000

1<=A[i]<=10^6

1<=B[i]<=10^6

---

Sample Input

(Plaintext Link)

3
5 6 7
1 2 3

Sample Output

(Plaintext Link)

3

Explanation

3 pairs are (5,2) , (5,3) and (6,3).

***************************EDITORIAL***********************************************************

IN THIS PROBLEM WE NEED TO DO  INVERSION COUNT IN A BIT  CHANGED WAY

SINCE A[I] CAN FORM INVERSION WITH B[J] WHERE J>I ANS A[I]>B[J] .. SOO PART IN WHICH WE DO CALCULATION OF INVERSION COUNT ,  LEFT PART WE USE A[] AND FOR RIGHT PART WE USE B[] . 

AFTER IC CALCULATION INDIVIDUALLY COMPARE AND SORT BOTH ARRAY ..

*****************************************************************************************************

#include<iostream>
using namespace std;
 typedef long long int lli;
 #include<bits/stdc++.h>
 lli ic=0;
    lli temp[1000000];
    lli arr[1000000+10];
      lli brr[1000000+10];
lli merge (lli arr[],lli brr[],lli start,lli mid,lli end)
   {
   
     lli i=start, 
j=mid+1;
     lli p=start;
   
      lli lc=0;
       while(i<=mid && j<=end)
        {
       
        if(arr[i]>brr[j])// calculation inversion in arr[] and brr[]
        {
        lc+=mid-i+1;
       
        j++;
}
else
{

i++;
}
       
}


//sorting arr
i=start, 
j=mid+1;
         p=start;

while(i<=mid && j<=end)
        {
       
        if(arr[i]>arr[j])
        {
       
        temp[p++]=arr[j];
        j++;
}
else
{
temp[p++]=arr[i++];
 
}
       
}

while(i<=mid) temp[p++]=arr[i++];
while(j<=end) temp[p++]=arr[j++];
for(int i=start;i<p;i++) arr[i]=temp[i];


//sorting brr
i=start, 
j=mid+1;
         p=start;

while(i<=mid && j<=end)
        {
       
        if(brr[i]>brr[j])
        {
       
        temp[p++]=brr[j];
        j++;
}
else
{
temp[p++]=brr[i++];
 
}
       
}

while(i<=mid) temp[p++]=brr[i++];
while(j<=end) temp[p++]=brr[j++];
for(int i=start;i<p;i++) brr[i]=temp[i];
return lc;
   }
  
 void  divide(lli arr[],lli brr[],lli start,lli end)
  {
   
  if(start<end)
  {
   
  lli mid=(start+end)/2;
   
  divide(arr,brr,start,mid);
  divide(arr,brr,mid+1,end);
  ic+=merge(arr,brr,start,mid,end);
  }
   

  }
  
 int  main()
  {
  
    ic=0;
    lli n;
    cin>>n;
      
    for(int i=0;i<n;i++)
     {
       cin>>arr[i];
        
 }
  for(int i=0;i<n;i++)
           {
           cin>>brr[i];
        
     }
 divide(arr,brr,0,n-1);
  cout<<ic<<endl;

return 0;
  }

Chef and Reunion

PROBLEM:

There are N males and N females (N<=10^5). Each male and female have indexes (unique for all males and unique for all females). All males are arranged in one line (standing at equal distances) according to increasing value of indexes. Similarily for females in another line.
Now pairings are done(between males and females) and line is drawn between each pair. We have to find how many pair of lines intersect each other.

OR

Today is the reunion of all chefs in the world. Our Chef wants to make this moment more happier. He arranged a mass wedding in this reunion. For this, he made a strange stage and drew two horizontal parallel lines on the stage. There are N unmarried male chefs in the reunion and he gave each male chef i an unique number M_i. Then all male chefs will stand in the first line drawn by Chef. But they will stand in increasing order of their number. That means chef with the lowest number will stand at the leftmost position of the line, then right to him would be the chef with the second lowest number and so on. Similarly, there are N female chefs in the reunion and Chef also gave each female chef j an unique number F_j (sequences F_j and M_i can have equal numbers). Then all female chefs will stand in the other line following the same rule(will stand in increasing order of the numbers) as the male chef.

Now chef will choose all the marriage pairs himself. He will select a female chef and a male chef (both of them have not selected before) and will draw a straight line between them. He calls this line a marriage line. He will do this for the rest of the chefs.

You will be given the N marriage lines; you have to find how many marriage line pairs intersect with each other.

Input

First line contains a single integer N. The i-th line of the next N lines contain two space separated integers M_i and F_i, means there is a marriage line between male chef M_i and female chef F_i. No marriage line will be mentioned twice.

Output

Output the number of marriage line pairs that intersect with each other on a single line.

Constraints

• 1 ≤ N ≤ 100000 (10⁵)
• 0 ≤ M_i, F_i ≤ 1000000000 (10⁹)

Example

Input:
3
2 3
3 6
5 4

Output:
1

Input:
4
5 12
10 11
11 9
30 1

Output:
6

Explanation

Example case 1. Only marriage lines (3, 6) and (5, 4) intersect with each other.

Example case 2. All the marriage lines intersect with each other.

*******************************************editorial*************************************************************************************

we need to calculate inversion count

we consider male value as index and females value = value at that index 

since male's value is value so wee need to sort  given pairs according to male (sice index must be increasing )

now just count no of inversion  in females value (after sorting according to  male )..

*************************************************code******************************************************************************

 #include<iostream>

using namespace std;

 typedef long long int lli;

 #include<bits/stdc++.h>

 lli ic=0;

lli merge (lli arr[],lli start,lli mid,lli end)

   {

   

     lli i=start, j=mid+1;

     lli p=start;

      lli temp[100000];

      lli lc=0;

       while(i<=mid && j<=end)

        {

       

        if(arr[i]>arr[j])

        {

        lc+=mid-i+1;

        temp[p++]=arr[j];

        j++;

}

else

{

temp[p++]=arr[i++];

}

       

}

while(i<=mid) temp[p++]=arr[i++];

while(j<=end) temp[p++]=arr[j++];

for(int i=start;i<p;i++) arr[i]=temp[i];

return lc;

   }

  

 void  divide(lli arr[],lli start,lli end)

  {

   

  if(start<end)

  {

   

  lli mid=(start+end)/2;

   

  divide(arr,start,mid);

  divide(arr,mid+1,end);

  ic+=merge(arr,start,mid,end);

  }

   

  }

  

 int  main()

  {

 

   

    ic=0;

    lli n;

    cin>>n;

   lli arr[n+10];

   vector<pair<lli,lli> > v;

    for(int i=0;i<n;i++)

     {

        lli a,b;

         cin>>a>>b;

         v.push_back(make_pair(a,b));

        

 }

 sort(v.begin(),v.end());

  for(int i=0;i<n;i++)

   arr[i]=v[i].second;

 divide(arr,0,n-1);

  cout<<ic<<endl;

return 0;

  }

The Warehouse

PROBLEM

Given a string consisting only of r, g and b, we have to find the shortest number of adjacent swaps to group all the similar characters together.

https://www.codechef.com/problems/WPROB/

OR

Olya works as a warehouse keeper for a T-Shirt factory. Now the factory is facing hard times, so currently they produce only the T-shirts of three kinds: red, green and blue T-Shirts. All the T-shirts are stored in the containers, each of the containers contain the T-Shirts of a single colour.

Now there are N containers at the warehouse, lined up in a line. Let's enumerate the containers by the positive integers from 1 to N, starting from the leftmost and ending at the rightmost one. Their order is described with a string S. Each symbol of this string is either "r", "g" or "b" and denotes the colour of the respective T-shirts, stored in the container.

Olya likes orderliness. She is not satisfied with the fact that different kinds of containers are messed up. So she wants to rearrange the containers in such a way that the number of pairs of adjacent containers that contain the T-shirts of different colors is as minimal as possible.

For doing that, she has a special crane. The crane is capable of doing the following things:

• Take a container with the number X and put it in front of all the containers. This operation takes(X-1) seconds. Note that we are considering the 1-dimensional model of the warehouse, so "in front of all the containers" means to the left of all the containers. The warehouse is so large, so you shouldn't worry about its' size and this operation is always performable.
• Take a container with the number X and take some container to the left of it (say, the container number Y). Remove the container number X from its' position and insert it right after the container with the number Y. This operation will take X-Y-1 seconds.
• Take a container with the number X and take some container to the right of it (say, the container number Y). Remove the container number X from its' position and insert it right after the container with the number Y. This operation will take Y-X seconds.

Note that after the operation, we will re-enumerate the containers from left to right by the positive integers from 1 to N.

Though Olya is keen on orderliness, she doesn't way to stay at the warehouse for long on Sunday. So she asks you to help her and to calculate the minimal possible number of seconds that is necessary to rearrange the containers in the desired way.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of Ttest cases follows.

The first (and only) line of each test case contains a string S, consisting of N symbols denoting the color string corresponding to the containers.

Output

For each test case, output a single line containing the answer to the problem's question for the corresponding test case.

Constraints

• 1 ≤ T ≤ 10
• The string S consists only of the lower-case Latin letters from the set {r, g, b}.
• (Subtask 1): 1 ≤ N = |S| ≤ 7 - 33 points.
• (Subtask 2): 1 ≤ N = |S| ≤ 1000 - 33 points.
• (Subtask 3): 1 ≤ N = |S| ≤ 10⁵ - 34 points.

Example

Input:
4
rgr
rrr
rgb
rgbr
Output:
1
0
0
2

Explanation

Example case 1.We can move the second container to the beginning of the line. This will take one second.

Example case 2.Containers are already in desired way.

Example case 3.Here also, containers are already in desired way.

Example case 4.You can put first r to the just right of b. It will take 2 seconds to do so.

**************************************************EDITORIAL********************************************************************

QUICK EXPLANATION

First, observe that all the moves really reduce down to swapping adjacent elements. Try all the 3! = 6 possible ordering of r, g and b. Now since the order is fixed, rearranging the string to a particular order is the same as sorting using the current order. The number of swaps required to sort an array is the same as the number of inversions.

EXPLANATION

Observe that each of the 3 types of moves reduce to swapping adjacent elements in 1 moment of time.

Assume for the moment that we know in which order the final rearrangement should be in. i.e. suppose the ordering is "rgb", then all the r's must come first followed by all the g's and then all the b's. What is the minimum number of moves required to do this?

Now say s[i] = 'r'. We know that r comes first, so if there is a 'b' or 'g' to the left of it, they must be swapped at some time. So, we can count the number of times b or g occur to the left of i and add them to the current answer. Similarly if s[i] = 'g' and there is a b to the right of i, then they must be swapped. So we count the number of times g occurs before i and add it to the current answer.

TO generalize, if we know the order o=o1o2o3 ( a permutation of r, g and b), we can find the minimum number of swaps to rearrenge the string in that order by looping through the string and keeping a count of the characters of each type we have seen so far. Suppose c1, c2 and c3 are the count of the o1, o2 and o3 seen so far.

We can get the minimum number of swaps as follows:

For i = 0 to len(s) - 1:

1. if s[i] == o1 cur_ans += c2 + c3
2. if s[i] == o2 cur_ans += c3

But how do we know which order is optimal? Let us see how many orders are possible. Since there are only 3 possible characters, there are only 3! = 6 possible orderings. So, we can try all possible orders, calculate the minimum number of swaps to achieve that order and take the minimum over all the orders to get the optimal answer.

---

What we are calculating is the number of inversions in the string given an order. What is an inversion? Intuitively, it is the number of pairs of numbers which are out of order in the array. More formally, the number of inversions of an array a is the number of pairs i < j such that a[i] > a[j]. We will prove that the number of adjacent swaps required to sort an array is equal to the number of inversions in the array.

Claim:
Minimum number of adjacent swap required to sort an array is exactly equal to number of inversions.

Proof:
By making one adjacent swap, we can not kill more than one inversion. So the number of swaps required will be at least equal to the number of inversions. So number of inversions will be a lower bound to number of swaps. We can indeed achieve that lower bound as follows.

Process:

1. Pick the minimum element (if there are many, pick the leftmost). All the elements which are on the left side of it should be moved to right side of it. For that you can pick the left adjacent element (if it exists) and swap it with minimum element. Keep repeating this step until minimum element is at the leftmost end. Total number of swaps taken are number of position i's such that A[i]>A[minPos] and i<minPos where minPos denotes location where minimum element was found. This is nothing but the number of inversions with minPos as one of the index.
2. Now remove the minimum element and repeat step 1.

You can notice that this process will sort the array and minimum number of swaps are exactly equal to number of inversions.

Complexity

There is only one loop and that is run a constant (6) number of times. So the complexity is O(n).

*******************************************************CODE (NLOGN)***************************************************

#include<iostream>

using namespace std;

 typedef int lli;

 typedef  int llli;

    lli temp[10000000];

   

 #include<bits/stdc++.h>

long long  ic=0;

lli merge (lli arr[],llli start,llli mid,llli end)

   {

   

     llli i=start, j=mid+1;

     llli p=start;

   

      long long   lc=0;

       while(i<=mid && j<=end)

        {

       

        if(arr[i]>arr[j])

        {

        lc+=mid-i+1;

        temp[p++]=arr[j];

        j++;

}

else

{

temp[p++]=arr[i++];

}

       

}

while(i<=mid) temp[p++]=arr[i++];

while(j<=end) temp[p++]=arr[j++];

for(int i=start;i<p;i++) arr[i]=temp[i];

return lc;

   }

  

 void  divide(lli arr[],llli start,llli end)

  {

   

  if(start<end)

  {

   

  int  mid=(start+end)/2;

   

  divide(arr,start,mid);

  divide(arr,mid+1,end);

  ic+=merge(arr,start,mid,end);

  }

   

  }

  

 int  main()

  {

  int t;

  cin>>t;

  while(t--)

   {

     ic=0;

     long long ans=1000000000000000LL;

      char arr[1000000];

       cin>>arr;

       

       llli len=strlen(arr);

        lli a[len+10];

  // rgb

   

    for(int i=0;i<len;i++)

     {

       if(arr[i]=='r') a[i]=1;

       else if(arr[i]=='g')a[i]=2;

       else if(arr[i]=='b')a[i]=3;

        

 }

 divide(a,0,len-1);

 

 if(ic<ans) ans=ic;

 ic=0;

 

 // rbg

   

    for(int i=0;i<len;i++)

     {

       if(arr[i]=='r') a[i]=1;

       else if(arr[i]=='b')a[i]=2;

       else if(arr[i]=='g')a[i]=3;

        

 }

 divide(a,0,len-1);

 

 if(ic<ans) ans=ic;

 ic=0;

 // brg

  for(int i=0;i<len;i++)

        {

       if(arr[i]=='b') a[i]=1;

       else if(arr[i]=='r')a[i]=2;

       else if(arr[i]=='g')a[i]=3;

        

 }

 divide(a,0,len-1);

 

 if(ic<ans) ans=ic;

 ic=0;

 

 // bgr

  for(int i=0;i<len;i++)

        {

       if(arr[i]=='b') a[i]=1;

       else if(arr[i]=='g')a[i]=2;

       else if(arr[i]=='r')a[i]=3;

        

 }

 divide(a,0,len-1);

 

 if(ic<ans) ans=ic;

 ic=0;

 

 //grb

  for(int i=0;i<len;i++)

        {

       if(arr[i]=='g') a[i]=1;

       else if(arr[i]=='r')a[i]=2;

       else if(arr[i]=='b')a[i]=3;

        

 }

 divide(a,0,len-1);

 

 if(ic<ans) ans=ic;

 ic=0;

 

 //gbr

  for(int i=0;i<len;i++)

        {

       if(arr[i]=='g') a[i]=1;

       else if(arr[i]=='b')a[i]=2;

       else if(arr[i]=='r')a[i]=3;

        

 }

 divide(a,0,len-1);

 

 if(ic<ans) ans=ic;

 ic=0;

  cout<<ans<<endl;

}

return 0;

  }

**********************************************************CODE O(6*N)********************************************************

//Coder: Balajiganapathi
#ifndef ONLINE_JUDGE
#   define DEBUG
#   define TRACE
#else
//#   define NDEBUG
#endif

#include <algorithm>


const int mx = 100005;
const long long oo = 1000000000000000000ll;

char col[mx];
char o[] = "rgb";
int n;


int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", col);
        n = strlen(col);

        long long ans = oo;
        sort(o, o + 3);
        do {
            long long cur = 0;

            int c0 = 0, c1 = 0, c2 = 0;
            for(int i = 0; i < n; ++i) {
                if(col[i] == o[0]) {
                    ++c0;
                    cur += c1 + c2;
                } else if(col[i] == o[1]) {
                    ++c1;
                    cur += c2;
                } else if(col[i] == o[2]) {
                    ++c2;
                }
            }

            ans = min(ans, cur);
        } while(next_permutation(o, o + 3));
        printf("%lld\n", ans);
    }
    
 return 0;
}