Code Niche Wifi Installation Problem CN03 http://www.codechef.com/CONI2015/problems/CN03

Please make me understand how to approach the problem. Well I can sort then??

I got accepted using the following approach.

Now, there are N locations, and we have to install C systems. So that means there can be N-C locations where we do not install any system. Let this number be K.

After sorting the array, for every position, we can choose not to install systems in the next K elements.
So we store the distance from this position to all the other K positions.

We only do this in the forward OR the backward direction since doing so in both the directions would add the same distance twice.

Now we need the minimum, so we sort this array, let the array be arr[]. But we can leave at K positions without installing systems. So our answer will be arr[K].

Here is my solution: http://ideone.com/3l3fZx

1 Like