Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Question about a binary search problem
Difference between en1 and en2, changed 13 character(s)
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;↵
}↵
```

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)