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

PROBLEM LINK: Contest Page | CodeChef

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

PREREQUISITES:

Nill

PROBLEM:

There are N cyclists in a town (in the shape of a matrix) having M cycles. Among these N cyclists, only K cyclists can be accommodated in the Grand Cycle Race. You have to start this race as soon as possible. You can ask any cyclist to move towards any cycle in the town. If you want to minimise the time taken to start the race, you need to ask the cyclists to occupy each of the first M cycles in the minimum time.
Each cyclist can move with unit speed and one cycle can be occupied by only one cyclist. A cyclist can move in any direction in the town.
Make sure that you use the Euclidean formula in order to find the distance between a cyclist and a cycle.
You need to find out the square of the time required to start the Grand Cycle Race as soon as possible.

QUICK EXPLANATION:

Find out the maximum value of the number of cyclists that will be able to get a cycle in a given time by making use of a bipartite graph. Now check if in a given time, K cyclists can get to a cycle or not. Make use of binary search to find out the required value of time.

EXPLANATION:

There are 2 subproblems here.
First try to solve this problem - Given M cyclists, N cycles and time T, how many cyclists (at max) will get a cycle while maintaining the rule that each cyclist can have only one cycle and one cycle can be accommodated by only one cyclist. For this subproblem, make a bipartite graph having M nodes in one partite and having N nodes in other partite and connect a node X from first partite to a node Y of second partite if cycle Y is reachable from cyclist X in given amount of time T. Value of maximum bipartite matching is the solution of this subproblem. Now using this subproblem, we can check whether in a given amount of time, K cyclists can get a cycle or not. Now define a function f in the given manner.
f(T) = true if K cyclists can get on a cycle in square_root(T) time,
else false,
as it is very obvious that if f(T) = true then f(T1) = true for all T1>=T and f(0) = false and f(10^16) = true as all coordinates X,Y <= 10^7. Use classical binary search to get the exact value of T.
long long int low = 0;
long long int high = 10000000000000000;

while(low < high)
{
long long int mid = (low + high) / 2;
if( f( mid ) )
{
high = mid;
}
else
{
low = mid+1 ;
}

}

This search will give the precise value of the square of time required in this problem.

SOLUTIONS:

Setter's Solution

#include
#include
#include
#include
#include
#include

using namespace std;

typedef long long ll;

const ll MAXN = 510;

ll n,m,k;
ll a[MAXN][2],b[MAXN][2];

struct node
{
ll u,v;
ll dis;
bool operator<(const node& r)const
{
return dis<r.dis;
}
}data[MAXN*MAXN];

ll uN,vN;
ll g[MAXN][MAXN];
ll linker[MAXN];
bool used[MAXN];

bool dfs(ll u)
{
ll v;
for(v=0;v<vN;v++)
if(g[u][v]&&!used[v])
{
used[v]=true;
if(linker[v]==-1||dfs(linker[v]))
{
linker[v]=u;
return true;
}
}
return false;
}

ll hungary()
{
ll res=0;
ll u;
memset(linker,-1,sizeof(linker));
for(u=0;u<uN;u++)
{
memset(used,0,sizeof(used));
if(dfs(u)) res++;
}
return res;
}

ll calc(ll x)
{
memset(g,0,sizeof(g));
for(ll i=0;i<=x;i++)
{
ll x = data[i].u;
ll y = data[i].v;
g[x][y] = 1;
}
return hungary();
}

ll solve()
{
ll cnt = 0;
uN = n;
vN = m;
for(ll i=0;i<n;i++)
{
for(ll j=0;j<m;j++)
{
data[cnt].u=i;
data[cnt].v=j;
data[cnt].dis = (a[i][0]-b[j][0])(a[i][0]-b[j][0])+(a[i][1]-b[j][1])(a[i][1]-b[j][1]);
cnt++;
}
}
sort(data,data+cnt);
ll lb=-1,ub=cnt;
while(ub-lb>1)
{
ll mid = (ub+lb)/2;
if(calc(mid)>=k)
{
ub = mid;
}
else
{
lb = mid;
}
}
return data[ub].dis;
}

int main()
{
ios::sync_with_stdio(0);
cin>>n>>m>>k;
for(ll i=0;i<n;i++)cin>>a[i][0]>>a[i][1];
for(ll i=0;i<m;i++)cin>>b[i][0]>>b[i][1];
ll ans = solve();
cout<<ans<<endl;
return 0;
}

Tester's Solution

Same Person

Editorialist's Solution

Same Person