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