https://www.codechef.com/MACE2021/problems/MCODE08

editorial
, , ,
1

PROBLEM LINK: CodeChef: Practical coding for everyone

Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY : HARD

PREREQUISITES:

Binary Search

PROBLEM:

Given 2 sets of points on a straight line(x axis) ,A and B. Using the points in B as centers you are supposed to draw circles. You are tasked to find the minimum possible radius for these circles if all circles drawn are of the same area and each point in A falls within at-least 1 circle. Note: It is not necessary that you need to use all points in B as centers.

#QUICK EXPLANATION:

Binary Search is the key.

#EXPLANATION:

First of all sort both the arrays in non-descending order. We can then binary search the answer within the given range constraints that the radius can be as per the question. For a particular radius obtained we can check if that radius is a possible answer in linear time by running a check on the given arrays and check if the conditions are satisfied. If not we can search on the upper half of the range otherwise check the lower half and repeat the above procedure.

SOLUTIONS:

Setter's Solution

#include
#include
#include
#define pb push_back
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
typedef std::vector VI;
typedef std::vector VL;
using namespace std;
void solve()
{
ll n,m;
cin>>n>>m;
VL a(n),b(m);

for(auto &i : a) cin>>i;
for(auto &i : b) cin>>i;

sort(all(a));
sort(all(b));

ll l = 0,r = 1e12;
while(l < r)
{
    ll m = l + (r - l) / 2;
    ll p1 = 0,p2 = 0;
    while(p1 < a.size() && p2 < b.size())
    {
        ll mini = b[p2] - m,maxi = b[p2] + m;
        while(p1 < a.size() && mini <= a[p1] && maxi >= a[p1]) ++p1;
        ++p2;
    }
    if(p1 == a.size()) r = m;
    else l = m + 1;
}
cout<<l<<"\n";

}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
t = 1;
while(t–)
{
solve();
}

return 0;

}

Tester's Solution

Same Person

Editorialist's Solution

Same Person