PRPR5 - Editorial

editorial
, , ,
1

#PROBLEM LINK:

Practice

Contest

Author: Suthirth V

Tester: Suthirth V

Editorialist: Suthirth V

#DIFFICULTY:

Simple

#PREREQUISITES:

Binary search - Top Coder Binary Search Tutorial

#PROBLEM:

Batman worried about his imminent battle with Superman tries to find as many shards of kryptonite as possible. He scoured the world and found “S” shards of kryptonite. In the BatCave , there is only one row of lead lined compartments( There are N compartments) which Superman’s X-Ray vision cannot penetrate. Some of these compartments are already occupied leaving only “N” free compartments. Even in this single row, Batman resolves to keep each of the shards as far away from each other as possible. Your task is to help Batman place the shards in such a way that the smallest distance between any two shards is the maximum possible. Find and output the same

Input :

First Line - N - number of free compartments

Second Line - S - number of shards

Third Line - N values, the coordinates of each of these free compartments separated by a space

Output

The maximum minimum distance between two shards

Sample Input

5

3

1 4 2 9 8

Sample Output

3

Explanation - He can keep the shards at 1, 4 and (8 or 9) giving the maximum minimum distance as 3.

#QUICK EXPLANATION:

The distance between two shards is what we would like to find out. This would range from 0 to the maximum being N. A Binary search within this range solves your problem

#EXPLANATION:

Let’s start with sample testcase,shall we? testcase is

Sample Input

5

3

1 4 2 9 8

Sample Output

3

So,we can keep the shards at 1,2,8,4 and 9th position. Now we’ve to find the largest minimum distance between 2 shards. It’s clear that minimum distance can be 0 (all shards in same compartment) or a[n-1] (2 shards at 1st and last position).

So binary search starts with l=0 and r=a[n-1] and we’ve to find the maximum distance. For that we’ll just create e function(fnc) which returns 1 if that is the desired distance else 0. So what do we write in this function? Let’s see.

int fnc(int x)

{

int i,temp;
temp=1;
lld prev;
prev=ar[0];
fu(i,1,N)
{
    if(ar[i]-prev >= x)
    {
        temp++;
        if(temp==S)
            return 1;
        prev=ar[i];
    }
}
return 0;

}

So what it’ll do? It’ll just check whether the difference between current compartment and previous compartment is at least x or not and if yes it’ll increase the temp(No of shards). If temp==c,it means we can store all the shards with the difference x(mid). So we return 1,else 0.

We’ll be doing the binary search for finding the best possible maximum difference.

#ALTERNATIVE SOLUTION:

The other approach would be to brute force it

#AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here

#RELATED PROBLEMS:

Aggressive Cows

1 Like