Vector Iteration C++11

[theconqueror]

I have a vector of pair<int, int>. vector<pair<int, int> > A . I have sorted this vector by the first element of the pair. Now I need to compare i and i+1 elements (like A[i] & A[i+1]) i.e. comparing it->first and it2->first where it points to A.begin() and it2 is it+1
Code:

            auto it= A.begin();
            auto it2= it+1;

          for ( ; it != A.end()-1; it++ )
          {
             if((((it)->first) > ((it2)->first) ) && (((it->second) < ((it2)->second)    ) ))
              {
                  cout<<"HI"<<endl;

              }
              it2++;
          }

I tried to debug but it2 and it both iterators point to the same element and both are equal and both are incremented simulatenously.

[Lachlan Easton]

Are you sure? Running this they both point to different elements https://ideone.com/cipTcH

[theconqueror]

http://postimg.org/image/qh7xz9fhh/
Here is the complete code for the SPOJ Problem - Inversion Count http://www.spoj.com/problems/INVCNT/.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
using namespace std;


bool myfunction (pair<long long int, long long int> i,pair<long long int, long long int> j)
{

return ( ( (i.first > j.first) && (i.second > j.second) ));
}


int main()
{



     int t;
    scanf("%d", &t);
    while(t--)
    {
        long long int n; int iz; vector< pair<long long int, long long int> > A;
        cin>>n; set<pair<long long int, long long int>  > s;
        for(long long int i = 0; i < n; i++)
            {
                long long int temp;
                    cin>>temp;
                    A.push_back(make_pair(temp, i));
            }
            sort(A.begin(), A.end(), myfunction);


long long int counter=0;
            auto it= A.begin();
            auto it2= it+1;

          for ( ; it != A.end()-1; it++ )
          {
              cout<<it->first<<" ";
              cout<<it2->first<<endl;

             if( (((it->second) < ((it)->second)    ) ))
              {
                  cout<<"HI"<<endl; counter++;

              }
             if((((it)->first) > ((it2)->first) ) && (((it->second) < ((it2)->second)    ) ))
              {
                  cout<<"HI"<<endl; counter++;

              }
              it2++;
          }
          cout<<counter;




            //sort(A, A+n);
        //scanf("%d", &iz);

    }
return 0;
}

UPDATE: It turns out it works but doesn't solve my problem. I tried to sort in descending order, how can I solve this?

Problem Statement: Let A[0...n - 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.

Input

The first line contains t, the number of testcases followed by a blank space. Each of the t tests start with a number n (n <= 200000). Then n + 1 lines follow. In the ith line a number A[i - 1] is given (A[i - 1] <= 10^7). The (n + 1)th line is a blank space.

Output

For every test output one line giving the number of inversions of A.

[keskiverto]

Could you explain your algorithm?

[theconqueror]

Yes sure.

1. Vector A has all the inputs in the form of a pair where the first element of the pair has the actual value and the second element of the pair has it's location index (which is to be preserved)
2. I sort the Vector A in descending order w.r.t. the first element of the pair. The corresponding second elements still have their indexes intact
3. In the problem we are asked to find the number of inversions of A. An Inversion is defined as if(i < j && A[i] > A[j]) then the pair (i,j) is an inversion of A.
I simply increment a counter each time this condition turns true.
4. Now, i, and j being the array indices, we have already preserved the corresponding indexes of the pair while sorting, so index i will be iter->second where iteris the iterator. And A[i] will be iter->first.

5. I've used the same logic in the "if" condition of my code.
Earlier I had used arrays without sorting but the nested loop results in O(N^2) running time which is not allowed

[keskiverto]

How does that help?

Lets take {3,2,1}. Three inversions: 3-2, 3-1, 2-1.
They happen to be in descending order.
Your "test consecutive elements" sees the 3-2 and the 2-1, so the count will be 2.

Websearch naturally finds an explanation: the difference of the position of an element in the original and sorted array knows the inversions for that element. That is not what your code does.

An another approach counts inversions while sorting, not after.