SOPC003C Editorial

PROBLEM LINK:

Practice
Contest

Author: Shriram Chandran
Editorialist: Shriram Chandran

DIFFICULTY:

Medium

PREREQUISITES:

Two pointers, binary search.

PROBLEM:

Given an array, find the number of pairs of numbers such that each of them is within the range of half to twice of the other number.

EXPLANATION:

In the hard version, there is not enough time to perform an O(n^2) search over the entire array, and find out for each pair if the number of possible teams. This will give a timeout. Thus, we will need an O(nlogn) solution.

One solution is to sort the array, and for a given i, find a suitable j by performing a binary search over the array, to find a j for which a_j > 2a_i.

I will explain a solution based on the two pointers method here.

First, sort the given sequence.

Let us define two pointers, s = 0 and e = 1 for start and end. Now as I loop through the array, I will increment #e# till I reach a point where a_e > 2a_s. At this point, I will stop incrementing #e#. Now, we make an observation: I can pair a_s with all persons till before a_e. Thus, I add e - s to my answer. Repeat this method now after incrementing s.

Note that since s and e go through the entire array once each, the complexity of this process is O(n) and the complexity of the entire solution is O(sort+n) which is expected to be O(nlogn).

SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;

void solve()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    ll ans=0;
    ll tans=0;
    int s=0,e=0;
    sort(a,a+n);
    while(s<n)
    {
        if(tans>0)
            tans--;
        if(e<s+1)
            e=s+1;
        while(e<n&&a[e]<=2*a[s])
            e++,tans++;
        ans+=tans;
        s++;
    }
    cout<<ans<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

It can be done by binary search only too.
Steps:

  1. Sort the array.
  2. Iterate through the whole array. For each iteration, we do binary search which returns the minimum position of the element satisfying the condition.
  3. We update our answer.

can you look at my solution which i uesd binary search but got TLE
but after replacing binary search with lower_bound got AC .
can tell the reasonsolution

https://www.codechef.com/viewsolution/28397007. This is my solution, and I have done by binary search only.

I solved it using fenwick trees :wink: WHAT AN OVERKILL!!!

1 Like

Oh God!! :laughing::laughing:

1 Like

Zyaada padhne ke bure side effect hai ye :frowning: Basics hi bhul gya mai toh, ab toh I 2 numbers ko multiply karne ke liye mai fft use kar leta hu :frowning:

English Translation :- I use fft to multiply two numbers these days…

1 Like

You can check my simple solution here :slight_smile:

1 Like

dude can u post your submission

1 Like

fft means? and from where do you read about new data structure.Kindly suggest.

Fast fourier Stuff. I’ll add stuff soon.

Thanks.Please suggest a list of all the advance or simple concept/algorithm to ace the competitive programming and learning data structure.

Kind regards,
Chandra