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

Question about a binary search problem

Revision en2, by oneturkm3n, 2019-08-11 21:08:23

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

Revisions Rev. Lang. By When Δ Comment
en2 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 oneturkm3n 2019-08-11 21:01:43 1468 Initial revision (published)