Question about a binary search problem

Revision en2, by oneturkm3n, 2019-08-11 21:08:23

Hi everyone! And Happy Eid Mubarak!

I am trying to understand the solution to this problem. It uses binary search approach to figure out the amount of unnecessary splitters (?) for supplying water to all $$$n$$$ pipes.

In the code snippet below, we calculate the total amount of pipes coming from $$$k$$$ used splitters, which is a sum from 2 to $$$k$$$. Working with the summation formula of consecutive numbers (i.e. $$$\frac{n * (n + 1)}{2}$$$), we can deduce that the if the following is true:

$$$k * \frac{(k - 1)}{2} < n - 1$$$

then we cannot supply all pipes and return $$$-1$$$.

Otherwise, we proceed with the binary search. What I don't get is why are we checking $$$a - mid * \frac{(mid + 1)}{2} < n$$$ with each iteration?

Solution:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
int main() {
    ll n, k;
    cin >> n >> k;
 
    if (k * (k - 1) / 2 < n - 1) {
        printf("-1\n");
    }
    else {
        ll start = 0;
        ll end = k;
        ll a = k * (k - 1) / 2 + 1;
        
        ll mid;
 
        while (start < end) {
            mid = start + (end - start) / 2;
 
            if (a - mid * (mid + 1) / 2 < n) {
                end = mid;
            }
            else {
                start = mid + 1;
            }
        }

        printf("%lld\n", k - start);
    }
    
    return 0;
}
Tags #binary search, round176

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English oneturkm3n 2019-08-11 21:08:23 13 Tiny change: 'i.e. $n * (n + 1) / 2$, we can d' -> 'i.e. $n * \frac{n + 1}[2}$), we can d'
en1 English oneturkm3n 2019-08-11 21:01:43 1468 Initial revision (published)