ALEXNUMB - Editorial

editorial
, , ,
1

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).

1 Like
2

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.

19 Likes
3

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??

1 Like
4

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.

3 Likes
5

Mind the size of the resulting number :wink:

1 Like
6

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

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

7

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

8

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

9

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?

10

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

11

In Simple words, the question says for an i, find all the elements that are larger than ar[i] in the given array ar. the index is not a constraint in this question.

12

why this is showing wrong answer

#include
using namespace std;
int main(){

int testcases;
cin>>testcases;
while (testcases--){
int s;
cin>>s;

long long int arr[s];

for(int i=0;i<s;i++){cin>>arr[i];}
cout<<s*(s-1)/2<<endl;


}

}

13

Awesome solution