Competitive Programming Problem

[aceadams]

Angry Cows
==========

Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows". The premise, which she believes is completely original, is that the player shoots cows with a slingshot into a one-dimensional scene consisting of a set of hay bales located at various points on a number line. Each cow lands with sufficient force to detonate the hay bales in close proximity to her landing site. The goal is to use a set of cows to detonate all the hay bales.

There are N hay bales located at distinct integer positions x1,x2,…,xN on the number line. If a cow is launched with power R landing at position x, this will causes a blast of "radius R", destroying all hay bales within the range x−R…x+R


A total of K cows are available to shoot, each with the same power R. Please determine the minimum integer value of R such that it is possible to use the K cows to detonate every single hay bale in the scene.

INPUT FORMAT :
The first line of input contains N
(1≤N≤50,000) and K (1≤K≤10). The remaining N lines all contain integers x1…xN (each in the range 0…1,000,000,000).

OUTPUT FORMAT :
Please output the minimum power R
with which each cow must be launched in order to detonate all the hay bales.

SAMPLE INPUT:

7 2
20
25
18
8
10
3
1

SAMPLE OUTPUT:

5

For this problem, I'm basically doing a binary search on the answer, my code seems correct, but is not outputting the correct answer. Through debugging, my guess is that the "count" variable is not being modified, but I cannot see why. My code is below.

#include <algorithm>
#include <iostream>
using namespace std;
int main () {
    int n;
    int k;
    cin>>n;
    cin>>k;
    int position [n];
    for (int i=0; i<n; i++) {
        cin>>position[i];
    }
    sort(position, position+n);
    int count;
    int min = position [0];
    int max = position [n-1];
    while (min!=max) {
    count=0;
    int mid = (min+max)/2;
    int last, curr =0;
    curr = last +1;
    while (curr<n&&position[curr]-position[last]<=2*mid) {
        last=last+2;
        curr=last+1;
        count++;
    }
    if (count>k)
        min=mid+1;
    if (count<=k)
        max=mid;
    }
    cout<<min;
}

[Albatross]

EDIT: OP realized their code block mistake and fixed it.

Is this coding competition okay with language extensions? If not, then you should be aware that int position[n]; is not legal in standard C++.

I'll leave it up to the others on this forum to answer your question. Do note that some people here have reservations about helping with competition questions.

-Albatross

[ne555]

1)

21 warning: variable 'last' is uninitialized when used here [-Wuninitialized]
curr = last +1;

a)

    int min = position [0];
    int max = position [n-1];
    while (min!=max) {

the initial value of `min' is incorrect

\alpha)

    while (curr<n&&position[curr]-position[last]<=2*mid) {
        last=last+2;
        curr=last+1;
        count++;
    }

makes no sense
the increments are wrong, the condition is wrong, out of bounds access...
do a dry run

by the way, nobody banned functions.


> I'm basically doing a binary search on the answer
good idea, ¿what's the expected order?

[aceadams]

Dang, thanks for the quick response! Why is the value of min incorrect, and why are the increments and conditions wrong? And what do you mean by expected order? Also yes! I'll use a function instead!

[ne555]

> Why is the value of min incorrect
you limit the radius R to the range [x_min; x_max], but x_min may be arbitrary big
for example x_min = 1000; x_max = 1100, that can be solve with R=500 with just one shot, but you'll never consider any less than 1000
R should be limit to [0; (x_max-xmin)/2] (but the upper limit is not too important, as long as it is big enough)

> why are the increments and conditions wrong?
let's reverse that, explain what that loop does and how it does it.
position[curr]-position[last]<=2*mid
suppose that `mid' is quite small, the loop will break in few iterations which is the opposite of what you want


> And what do you mean by expected order?
the time complexity of your algorithm, how does it scale with `n' and `k'