How to efficiently pick points from a given array so the distance between the two closest points are maximized.

[BBrandon]

Hello. So I've been trying to solve this problem from my coding camp that has stumped me for hours. I've got a solution, but with the higher test scenarios, it just can't run fast enough. I've tried everything I could think of, but it still isn't quick enough. Can anyone help me further optimize my program or does anyone have a better solution?

Here's my code so far...

#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <vector>
using namespace std;

// Function to check if it is possible
// to place C magnets assuming mid as
// maximum possible distance
bool isPossible(int arr[], int n, int C, int mid)
{
  // Variable magnet will store count of magnets
  // that got placed and currPosition will store
  // the position of last placed magnet
  int magnet = 1, currPosition = arr[0];

  for (int i = 1; i < n; i++) {

    // If difference between current index and
    // last placed index is greater than or equal to mid
    // it will allow placing magnet to this index
    if (arr[i] - currPosition >= mid) {
      magnet++;
      // Now this index will become
      // last placed index
        currPosition = arr[i];

      // If count of magnets placed becomes C
      if (magnet == C)
      return true;
      }
    }
    // If count of placed magnet is
    // less than C then return false
    return false;
}

// Function for modified binary search
int binarySearch(int n, int C, int arr[])
{
    int lo, hi, mid, ans;

    // Sort the indices in ascending order
    sort(arr, arr + n);

    // Minimum possible distance
    lo = 0;

    // Maximum possible distance
    hi = arr[n - 1];

    ans = 0;
    // Run the loop until lo becomes
    // greater than hi
    while (lo <= hi) {
        mid = (lo + hi) / 2;

        // If not possible, decrease value of hi
        if (!isPossible(arr, n, C, mid))
            hi = mid - 1;
        else {
            // Update the answer
            ans = max(ans, mid);
            lo = mid + 1;
        }
    }
    // Return maximum possible distance
    return ans;
}

int gen() {
  static int i = 0;
  return ++i;
}

// Driver code
int main() {
  cout << "zoomer" << endl;
  ifstream fin ("socdist.in");
  ofstream fout ("socdist.out");
  int N = 0;
  int M = 0;
  int length = 0;
  fin >> N >> M;
  vector<int> line(0);
  for (int counter1 = 0; counter1 < M; ++counter1) {
    int grass[2];
    fin >> grass[0];
    fin >> grass[1];
    length = length + (grass[1]-grass[0]) + 1;
    vector<int> temparea(0);
    for (int counter2 = grass[0]; counter2 <= grass[1]; ++counter2) {
        temparea.insert(temparea.begin() + (counter2-grass[0]), counter2);
    }
    line.insert(line.end(), temparea.begin(), temparea.end());
  }
  int arr[length];
  copy(line.begin(), line.end(), arr);
  fout << binarySearch(length, N, arr) << endl;
  return 0;
}

And in case anyone wants to see the problem. Here it is...

Farmer John is worried for the health of his cows after an outbreak of the highly contagious bovine disease COWVID-19.
In order to limit transmission of the disease, Farmer John's N cows (2≤N≤105) have decided to practice "social distancing" and spread themselves out across the farm. The farm is shaped like a 1D number line, with M mutually-disjoint intervals (1≤M≤105) in which there is grass for grazing. The cows want to locate themselves at distinct integer points, each covered in grass, so as to maximize the value of D, where D represents the distance between the closest pair of cows. Please help the cows determine the largest possible value of D.

INPUT FORMAT (file socdist.in):
The first line of input contains N and M. The next M lines each describe an interval in terms of two integers a and b, where 0≤a≤b≤1018. No two intervals overlap or touch at their endpoints. A cow standing on the endpoint of an interval counts as standing on grass.
OUTPUT FORMAT (file socdist.out):
Print the largest possible value of D such that all pairs of cows are D units apart. A solution with D>0 is guaranteed to exist.
SAMPLE INPUT:
5 3
0 2
4 7
9 9
SAMPLE OUTPUT:
2
One way to achieve D=2 is to have cows at positions 0, 2, 4, 6 and 9.

SCORING:
Test cases 2-3 satisfy b≤105.
Test cases 4-10 satisfy no additional constraints.

[salem c]

The thing to remember about these kinds of problems is you don't solve them by writing code.

Your success or failure is determined by what you do on paper before you even reach for the keyboard and start typing "int main..."

All these problems have two solutions.

The simple and obvious solution (which you may have written) which works well enough for small numbers, but I'm guessing you lost some formatting and 1≤M≤105 and 0≤a≤b≤1018 are really 1≤M≤10⁵ and 0≤a≤b≤10¹⁸

Aside from the fact that 10¹⁸ would need a 64-bit int (try long long int in your code), you're never going to win ("it just can't run fast enough") just by trying multiple combinations of such large quantities.

So no, no amount of tinkering with your current solution is going to make it run quick enough.

Then there is the smart answer you get by doing some solid analysis of the problem on paper to extract the essence of the problem. It's only when you FULLY understand the problem that you can hope to write efficient code.

[BBrandon]

Do you have any ideas of that other solution? I've tried calculating the time it would require for my solution and it seems that the limit 10^5 would allow my method to be feasible, so I am a bit confused on why my program still exceeds the runtime. Do you have any idea why this is?

[salem c]

Well since the question talks about cows, and your first comment is all about magnets, I'm wondering whether your code has anything at all to do with the problem.

> int arr[length];
> copy(line.begin(), line.end(), arr);
As well as being illegal in C++, it's also a complete waste of time.
std::sort is perfectly capable of sorting a vector as it is an array.

> vector<int> temparea(0);
You already know what the length is going to be, so set it.

vector.insert seems expensive when what you seem to be doing all the time is appending.

[dutch]

Your method is totally infeasible!

You have up to 10^5 cows and 10^5 intervals,
but the intervals endpoints range up to 10^18 !!!
You are creating an array that is the sum of the lengths of all of the intervals!
That's a problem.

Also, you should be using long long (or int64_t) instead of int since int is not guaranteed to be 64 bits and so cannot necesarily handle an interval endpoint.

Additionally, your use of binary search is totally incorrect.
I can't really figure out what you are thinking there.
It's basically just generating a decreasing interval.

So I suspect your solution is incorrect, too.

[BBrandon]

What other ideas would you guys have for this problem then? And the magnets part is from I code that I wrote earlier for a different problem, but with similar ideology. The "binary search" function is just looking for the maximal distance that the two closest cows can be, when given all available spots on the number line. But the problem only gives me the intervals of the grass spots, so I'm using the main function to convert that into an array with all of the actually integer spots with grass, and then taking that array and using the "binary search" function to find the answer. I really can't think of a better way, so what are your ideas on this?

[dutch]

Well, firstly you need to think of a way of getting rid of that insanely gigantic vector.
You need to just store the start and end points of the intervals and work with those.

[BBrandon]

Do you have some code for that? I really don't know how I could convert it to just use the endpoints of intervals instead of using the entire interval.

[dutch]

It's not for me to solve the puzzle for you.
You're the one who presumably wants to do this.
So do it.

Forget the code.
Get some paper.
Create some smallish examples.
Work them out.
Notice the patterns.
Finally, almost as an afterthought, write the program (which should be the easiest part).

If you can't figure it out, don't worry about it.
Try an easier puzzle.