ALEXNUMB - Editorial

Problem:
You are given an array of N numbers. You are to find the number of pairs of numbers in the array s.t a[i] < a[j].

Solution:
First you find the set of all distinct elements in the array {x(1), …, x(M)} with x(i) < x(i+1) and their corresponding counts {c(1),…,c(M). Now it is easy to see that the required number of such pairs is
Sum_{i} (c(i) * (c(1)+…c(i-1))
This is simply
Sum_{i} (c(i) * c_cumulative(i-1))
where c_cumulative(k) is the cumulative sum of c() that can be computed in O(M) time. Thus, the total counts of such pairs can be computed in O(N).

The problem describes that all integers are distinct. Therefore any two integers, say (ai, aj), will satisfy the property ai < aj or aj < ai. Two integers can be picked up in NC2 ways. So the answer is simply N*(N-1)/2.

14 Likes

import java.util.;
class Sol
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-- > 0)
{
int n=sc.nextInt();
long x=0;
for(int i=0;i<n;i++)
x=sc.nextLong();
System.out.println((n
(n-1)/2));

}

}
}

//What is wrong in this??

This is a very straightforward and easy problem. As it is provided that all the values in the array are distinct then all the possible pairings in the sorted array are valid which by applying a little mathematics is n*(n - 1)/2.

1 Like

Mind the size of the resulting number :wink:

1 Like

@chauhan_1111 Be careful that Integer.MAX_VALUE < 100000 * 99999. Just change this:

int n=sc.nextInt() --> long n=sc.nextLong()

Thanks,I learned the fact that some times we should think in a simple way.

Why didn’t this work?
https://www.codechef.com/viewsolution/29817047

the respective indexes for example 3 1 2 are :
numbers 3 1 2
indexes 0 1 2

so how is (3,1) a solution? Index of 1 is higher than index of 3

Am I missing something?

man, completely missed that distinct part :sweat_smile: :sweat_smile: