### oneturkm3n's blog

By oneturkm3n, history, 14 months ago,

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