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. $$$n * (n + 1) / 2$$$, we can deduce that the if the following is true:

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;
}