Divide and Conquer algorithm in C++

Question

There is this one problem in some online judge that I have no clue on how to get accepted.

The problem goes like this first line contained two number

N (0 < N < 2^18) 
M (0 < M < 2^20)

The second line contained N numbers

ai (0 < ai < 2^40)

The question is how many X are there that satisfied:

M = floor(X/a1) + floor(X/a2) + ... + floor(X/an)

My naive solution:

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

long long n,m,i,j,haha,sum;
int main()
{
    cin >> n >> m;
    haha = 0;
    long long ar[n+5];
    for(i = 0; i < n; i++) cin >> ar[i];
    sort(ar,ar+n);
    for(i = ar[0]+1; i < m*ar[0]; i++){
        sum = 0;
        for (j = 0; j < n; j++) sum += i/ar[j];
        if (sum == m) haha += 1;
        else if (sum >= m) break;
    }
    cout << haha << endl;
}

Update1: My binary search solution (still didn't pass the time limit):

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

long long n,m,i,l,r,mid,ans,tmp,cnt,haha;
long long ar[2621440];
long long func(long long x){
    haha = 0;
    for (i = 0; i < n; i++) haha += x/ar[i];
    return haha;
}

int main()
{
    cin >> n >> m;
    for(i = 0; i < n; i++) cin >> ar[i];
    sort(ar,ar+n);
    l = ar[0];
    r = ar[0]*m;
    mid = (l+r)/2;
    tmp = func(mid);
    while (tmp != m){
        mid = (l+r)/2;
        tmp = func(mid);
        if (l == r) break;
        if (tmp < m) l = mid+1;
        else if (tmp > m) r = mid-1;
        else break;
    }
    ans = 0;
    if (tmp == m) ans += 1;
    cnt = mid;
    while (func(cnt-1) == m){
        ans += 1;
        cnt -= 1;
    }
    cnt = mid;
    while (func(cnt+1) == m){
        ans += 1;
        cnt += 1;
    }
    cout << ans << endl;
}

Answer 1

Got accepted (finally) using two binary search (each for lower bound, and upper bound) with this code:

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

long long n,m,i,l,r,mid1,mid2,ans,tmp,cnt,haha,k;
long long ar[26214400];
long long func(long long x){
    haha = 0;
    for (k = 0; k < n; k++) haha += x/ar[k];
    return haha;
}

int main()
{
    cin >> n >> m;
    for(i = 0; i < n; i++) cin >> ar[i];
    sort(ar,ar+n);
    l = ar[0];
    r = ar[0]*m;
    mid1 = (l+r)/2;
    tmp = func(mid1);
    while (l < r){
        mid1 = (l+r)/2;
        tmp = func(mid1);
        if (tmp < m) l = mid1+1;
        else if (tmp > m) r = mid1-1;
        else r = mid1-1;
    }
    mid1 = l; //lower bound
    l = ar[0];
    r = ar[0]*m;
    mid2 = (l+r)/2;
    tmp = func(mid2);
    while (l < r){
        mid2 = (l+r)/2;
        tmp = func(mid2);
        if (tmp < m) l = mid2+1;
        else if (tmp > m) r = mid2-1;
        else l = mid2+1;
    }
    mid2 = r; //upper bound
    while (mid1 <= mid2 and func(mid1) != m) mid1 += 1;
    while (mid2 >= mid1 and func(mid2) != m) mid2 -= 1;
    ans = mid2-mid1+1;
    cout << ans << endl;
}

Answer 2

Update

Going with the binary search approach, here is my new code:

// compute X/ai sum
long long summarize(long long ar[], long long n, long long X)
{
    long long sum = 0;
    for (long long i = 0; i < n; i++)
    {
        sum += X/ar[i];
    }
    return sum;
}

bool get_range(long long ar[], int n, int m, pair<long long, long long>& range)
{
    long long sum = 0;
    long long x;
    // reduce range
    while (range.first < range.second)
    {
        x = (range.first + range.second) / 2;

        sum = summarize(ar, n, x);
        if (sum < m)
        {
            range.first = x + 1;
        }
        else if (sum > m)
        {
            range.second = x;
        }
        else if (x == range.first)
        {
            return true; // single element
        }
        else
        {
            break;
        }
    }

    if (sum != m)
    {
        return false;
    }

    // check surroundings for lower / upper bound.
    sum = summarize(ar, n, range.first);
    if (sum != m)
    {
        auto r1 = make_pair(range.first + 1, x);
        if (get_range(ar, n, m, r1))
        {
            range.first = r1.first;
        }
        else
        {
            range.first = x;
        }
    }
    sum = summarize(ar, n, range.second - 1);
    if (sum != m)
    {
        auto r2 = make_pair(x + 1, range.second - 1);
        if (get_range(ar, n, m, r2))
        {
            range.second = r2.second;
        }
        else
        {
            range.second = x + 1;
        }
    }

    return true;
}


int main()
{
    int n, m;
    cin >> n >> m;
    long long *ar = new long long[n];
    long long ar_min = LLONG_MAX;
    for(long long i = 0; i < n; i++)
    {
        cin >> ar[i];
        ar_min = min(ar[i], ar_min);
    }
    // initial range of possible X values
    auto range = make_pair(m / (ar_min * n), m * ar_min);
    if (get_range(ar, n, m, range))
    {
        cout << (range.second - range.first) << endl;
    }
    else
    {
        cout << 0 << endl;
    }
}

Core functionality is the get_range function, which takes a possible range ([range.first, range.second), so second is not part of the range) and reduces the range so all elements in range satisfy the condition. It is first iteratively adjusting range bounds until the middle of the range is part of the result or until it's clear that there is no result in range. Then, if there is any result, it is recursively checking the sub-ranges below and above the found result in order to retrieve the bounds of the whole result range.

Version 1

You are only dealing with positive numbers greater than zero.

M = floor(X/a1) + floor(X/a2) + ... + floor(X/an)

For every sub-term floor(X/a1), there is floor(X1/ai) <= floor(X2/ai) if X1 < X2. So the only possible X values resulting in M are those, where floor(X1/ai) == floor(X2/ai) for all i (or all ai).

For each ai this is exactly the Range of X1=k*ai until X2=k*ai+(ai-1) for some k.

This means, if any solution exists, the range of X values will be between k*min(ai) and (k+1)*min(ai) for some 0 < k <= m.

So it might be worth to first get the range of possible results and then check the individual values only within the range.

Resulting algorithm:

// compute X/ai sum
long long summarize(long long ar[], long long n, long long X)
{
    long long sum = 0;
    for (long long i = 0; i < n; i++)
    {
        sum += X/ar[i];
    }
    return sum;
}

int main()
{
    int n, m;
    cin >> n >> m;
    long long *ar = new long long[n];
    long long ar_min = LLONG_MAX;
    for(long long i = 0; i < n; i++)
    {
        cin >> ar[i];
        ar_min = min(ar[i], ar_min);
    }

    // lowest possible k
    long long k = m / (ar_min * n);
    // get the value k for a possible range of X values
    for (; k <= m; k++)
    {
        auto x = ar_min * (k + 1);
        long long sum = summarize(ar, n, x);
        if (sum > m)
        {
            break;
        }
    }
    long long X_min = k * ar_min, X_max = (k + 1) * ar_min;
    long long result = 0;
    // count possible X values
    for (long long x = X_min; x < X_max; x++)
    {
        long long sum = summarize(ar, n, x);
        if (sum == m)
        {
            ++result;
        }
        else if (sum > m)
        {
            break;
        }
    }

    cout << result << endl;
}

It got a bit more complicated than I first expected. I hope it's still some sort of improvement.

Answer 3

I believe that the expected solution for this is binary search.

Define f(x) = sum_i f(x/a_i). Without loss of generality, assume that a_i are given in inceasing order.

Clearly,

• f(0) = 0 < M
• f(M*a_1) ≥ M
• f(x) ≥ f(y) if x≥y

Thus you can do binary search to find the lowest value of x such that f(x) = M, with start = 0 and end = M*a_1 as the initial limits for the binary search.

To find the upper limit for x, do another binary search or just loop through all values in the array to find the smallest y such that floor(y/ai) > floor(x/ai) for some i.