PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Souradeep
Tester : Riley Borgard
Editorialist: Aman Dwivedi
DIFFICULTY:
Simple
PREREQUISITES:
Observation
PROBLEM:
Given a sequence A_1, A_2, \ldots, A_N. An ordered pair of indices (i,j) in this sequence is called a beautiful pair if i \neq j and \frac{A_i - A_j}{A_i} \lt \frac{A_i - A_j}{A_j}. (Here division represents real division)
Find the number of beautiful pairs present in the given sequence.
EXPLANATION:
Subtask 1:
As the value of N is quite small which allows us to consider every ordered pair of indices (i, j) of the given sequence.
Therefore we can easily find the number of pairs that are beautiful.
Time Complexity
O(N^2) per test case
Solution
// Subtask 1
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
double a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int ans = 0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j)
continue;
int temp = a[i]-a[j];
if(temp/a[i]<temp/a[j])
ans++;
}
}
cout<<ans<<"\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
Subtask 2:
Since the value of N is large enough to not allow us to check all the ordered pairs. We can optimize with some basic observations and calculations.
Let’s say we have an ordered pair of indices (i, j) whose values are A_i and A_j. Now according to the values of A_i and A_j, there are three cases possible:
Case 1
A_i \gt A_j
When A_i \gt A_j, then the value of A_i - A_j will be positive. Let’s call this value X. We have,
Multiplying X on both sides we get:
Finally substituting the values of X, we get:
That means all such pairs where A_i \gt A_j are beautiful pairs.
Case 2
A_i \lt A_j
When A_i \lt A_j, then the value of A_i - A_j will be negative. Let’s call this value X. We have,
Multiplying X on both sides we get:
Finally substituting the values of X, we get:
That means all such pairs where A_i \lt A_j are also beautiful pairs.
Case 3
A_i = A_j
When A_i = A_j, then the value of A_i - A_j will be zero. Hence
Therefore the condition of \frac{A_i-A_j}{A_i} \lt \frac{A_i-A_j}{A_j} doesn’t hold. Hence we say that such pairs where A_i = A_j , those pairs are not beautiful.
From the above cases, we can say that the pair is not beautiful when A_i = A_j. Therefore we can maintain a frequency array that stores the count of each element in the given array, Finally, when we are at index i we can simply add (N-freq[A_i]) in our answer, where freq[A_i] tells the occurrences of A_i in an array.
TIME COMPLEXITY:
O(N) per test case.
SOLUTIONS:
Author
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
// BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int t=1;
t=sc.nextInt();
//int t=Integer.parseInt(br.readLine());
while(--t>=0){
int n=sc.nextInt();
int a[]=new int[n];
int pre[]=new int[1000001];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
pre[a[i]]++;
}
long sum=0;
for(int i=0;i<n;i++){
sum=sum+(n-pre[a[i]]);
}
System.out.println(sum);
}
}
}
Tester
#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
void solve() {
int n;
cin >> n;
map<ll, int> ma;
rep(i, 0, n) {
ll a;
cin >> a;
ma[a]++;
}
ll ans = 1LL * n * (n - 1);
for(auto &pa : ma) {
ans -= 1LL * pa.second * (pa.second - 1);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
while(te--) solve();
}
Editorialist
// Subtask 2
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int ans = 0;
map <int,int> m1;
for(int i=0;i<n;i++)
m1[a[i]]++;
for(int i=0;i<n;i++)
ans+=(n-m1[a[i]]);
cout<<ans<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
cin>>t;
while(t--)
solve();
return 0;
}