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;
}
This seems a bit late, but your question is very well-written (I found it from this comment praising you), so even if you've figured this out already and this comment is pointless, it's all good :)
As mentioned, the maximum amount of pipes we can obtain is $$$k * \frac{k - 1}{2} + 1$$$ because a splitter with $$$x$$$ output slots adds $$$x - 1$$$ output pipes in total, and we start with one. We want to use as few splitters as possible, so it seems intuitive that we would generally want to use the splitters that contribute the most (let's denote them as the 'largest' splitters).
Assume the answer exists, because you can easily find if it doesn't. Let's try a simple greedy strategy. In each step, add the largest splitter that you can until you either get exactly $$$n$$$, or the next splitter you'll add is too big and your answer will exceed $$$n$$$. In the second case, without loss of generality, say you have $$$x$$$ pipes left to obtain. Furthermore, denote the size of the largest splitter you haven't included yet as $$$y$$$.
There must be a splitter that you haven't taken with its value equal to $$$x$$$, because if $$$x \geq y$$$, you would have already taken the splitter of size $$$y$$$, and since you've only taken the splitters of size greater than $$$y$$$, you'll still have the splitter of size $$$x$$$ and you can use it. Therefore, we add $$$1$$$ to our answer
We always take the largest splitter possible, and there are no 'traps' to fall into, so this greedy algorithm will always produce the correct result. The problem is, $$$k \leq 10^{9}$$$, so it could (or at least, was intended to) be too slow for us to run. The binary search simulates this strategy, but reduces it to $$$O(logk)$$$ complexity instead of $$$O(k)$$$. Following the greedy approach, we're going to find the most amount of elements (starting with $$$k - 1$$$, and descending) we can include without exceeding $$$n$$$. If we can't do this exactly, by the logic of $$$x$$$ and $$$y$$$ above, we only have to include one more element. This is what they mean by binary searching on a suffix of $$$1 ... k - 1$$$ in the editorial, as we're going to use the splitters with contributions from $$$y + 1$$$ to $$$k - 1$$$.
I'm almost done here, I swear. To do this binary search, we need an efficient way to check the sum of the values we're including. To do this, because we're operating on a suffix of $$$mid + 1$$$ to $$$k - 1$$$, we just take the sum of the whole ($$$a = k * \frac{k - 1}{2} + 1$$$), and subtract the prefix of $$$1$$$ to $$$mid$$$ ($$$mid * \frac{mid - 1}{2}$$$) from it, leaving us the desired sum of the suffix. This is where $$$a - mid * \frac{mid - 1}{2}$$$ comes from. When we finally find our desired value, we can check if we need an extra one (as in above, $$$x \neq 0$$$), and print the answer.
There's another way to think about the binary search involving the complement of our set and our sum that would describe the logic of the binary search slightly better, but this comment is too long already :P
If this doesn't make sense, feel free to ask about something.
Thank you very much!
And yes, you are right on time. I had gotten no comment on that (and no other explanation on the Internet), so I left it out. But now it makes sense! Thank you for the detailed explanation!
Cheers.