Binary searching the turning point of a function

Question

The problem

You are given a list of \$ n \$ positive integers. Your task is to split the list into \$ k \$ subarrays so that the largest subarray sum is minimized.

The input

On the first line you have two integers n and k; the size of the list and the number of subarrays. On the second line you have n numbers: x1, x2, ..., xN.

The limits

\$ 1 \leq n \leq 10^5 \$

\$ 1 \leq k \leq n \$

\$ 1 \leq x \leq 10^9 \$

An example

Input

5 3

2 4 7 3 5

Output:

8 (the subarrays are [2,4], [7], [3,5])

My solution

Let's define a function isPossible, that returns true if it is possible to divide the list into \$ k \$ subarrays so that the maximum sum is the parameter sum. The function loops through the user-inputted array and pushes elements into a vector as long as the elements do not exceed the parameter sum. When the vector can't take the next element without exceeding sum, a new vector is created. All these created vectors are pushed into a vector and if the size of the vector holding all the vectors is less than or equal to \$ k \$, return true. Else return false.

The method vectorsum is a shortcut to getting the sum of the elements inside a vector.

After that I handle the input in main() and binary search the turning point of isPossible.

What went wrong?

I can handle the small test cases easily, but with larger numbers I get a "time limit exceeded"-error. However the time limit is 1 second and I don't think the test even took so long, so I suspect there might be something off with my data types. Any other improvements are accepted, too!

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <numeric>
#include <math.h>
using namespace std;

int arraysize;
int numberofsubarrays;
long long usernumber;
vector<long long> userArray; //Used in main()

vector<vector<long long>> subarrays; //Used in isPossible()



int vectorsum(vector<long long> userVector) {
    int ans = accumulate(userVector.begin(), userVector.end(), 0);
    return ans;
}

bool isPossible(long long n) {
    subarrays = {};
    subarrays.push_back({});
    for (auto u : userArray) {
        subarrays.back().push_back(u);
        if (vectorsum(subarrays.back()) <= n) {
            continue;
        }
        else {
            subarrays.back().pop_back();
            subarrays.push_back({ u });
        }
    }
    if ((long long)subarrays.size() > numberofsubarrays) {
        return false;
    }
    else {
        return true;
    }
}

int main()
{
    cin >> arraysize >> numberofsubarrays; //Input handling
    for (int u = 0; u < arraysize; u++) {
        cin >> usernumber;
        userArray.push_back(usernumber);
    }

    long long left = 1;
    long long middle;
    long long right = pow(10, 10);

    while (left + 1 != right) { //Binary search
        middle = ceil((left + right) / 2);
        /*cout << left << "  " << middle << "  " << right << endl;*/
        if (isPossible(middle)) {
            right = middle;
        }
        else {
            left = middle;
        }
    }
    cout << left + 1 << endl;
    return 0;
}

Answer 1

Don't use using namespace std; Writing std:: a few times isn't that bad, and it helps keep the std lib types identifiable in your code.

---

Don't use globals so much. It is much better to limit the scope of variables to where they are needed and pass them around (possibly by reference) when needed. Usernumber for example is only used when filling the array, So something like this is much better:

for (int u = 0; u < arraysize; u++) {
    long long number;
    std::cin >> number;
    userArray.push_back(number);
}

---

vectorsum has a vector passed by value, this will copy the entire vector. instead you'll want to pass by const ref:

int vectorsum(const std::vector<long long>& userVector) {
    int ans = std::accumulate(userVector.begin(), userVector.end(), 0);
    return ans;
}

You don't really need this function at all though, you can keep a running total instead and save yourself the loop.

---

You keep rebuilding the vectors over and over again, you don't even need to do that. Instead you only need to keep track of the sum of the current subarray you are testing and how many subarrays you have built already.

You can also keep track of the largest subarray sum and pass it back as new upperbound. This will reduce the iteration time once the options have been narrowed down somewhat because then you will never try 2 numbers that will create the same partition.

long long isPossible(const std::vector<long long> &user_array, long long max_sum, int max_number_subarrays) {

    long long running_sum = 0;
    long long largest_sum = 0;
    int subarray_count = 0;
    for (auto current : userArray) {
        if (running_sum + current <= max_sum) {
            running_sum += current;
        } else {
            if(running_sum > largest_sum) 
                 largest_sum = running_sum;

            running_sum = current;

            subarray_count++;
            if(subarray_count > max_number_subarrays) 
                return -1; //early out

        }
    }

    return largest_sum;
}

and in the while loop.

while (left + 1 != right) { //Binary search
    middle = ceil((left + right) / 2);
    long long result = isPossible(userArray, middle, numberofsubarrays)
    if (result >= 0) {
        right = result;
    }
    else {
        left = middle;
    }
}
std::cout << right << endl;

---

You can initialize left with the largest number in the input Because if it was less than at least one sub array sum will be larger than it.

right can be initialized with the sum of the array where every element is in a single subarray.

int left = 0;
int right = 0;

for (int u = 0; u < arraysize; u++) {
    long long number;
    std::cin >> number;
    userArray.push_back(number);

    if(left < number) 
        left = number;
    right+= number;
}