Hi everyone! And Happy Eid Mubarak!↵
↵
I am trying to understand the solution to [this problem](https://codeforces.com/contest/287/problem/B). 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$}{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:↵
↵
```c++↵
#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;↵
}↵
```
↵
I am trying to understand the solution to [this problem](https://codeforces.com/contest/287/problem/B). 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)
↵
$$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:↵
↵
```c++↵
#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;↵
}↵
```
