PROBLEM LINK:
Setter: Mohammed Ehab
Tester: Ramazan Rakhmatullin
Editorialist: Ishmeet Singh Saggu
DIFFICULTY:
Medium
PREREQUISITES:
Maths
PROBLEM:
You have R-L+1 spaghetti/lines, where you have exactly one line with each length between L and R. You have to find how many different lengths you can form by using one or more lines.
EXPLANATION:
I am referring to spaghetti as line.
For the first subtask, you have N lines with lengths 1 to N, then the maximum length line you can make is by connecting all the lines, i.e. 1+2+3+...+N = \frac{(N*(N+1))}{2}, and it is equal to the number of distinct lengths you can make. (try to construct it by taking only 1 element, then only 2 elements, then 3 and so on).
construction
Take 1 element, start from 1 to N. So you will get N different sums.
Take 2 elements, where 1 element will be N and the other element will be iterate from 1 to N-1, giving sum from N+1 to N+N-1. So you will get N-1 different new sums.
Take 3 elements, where 2 elements will be N-1 and N and third element will iterate from 1 to N-2, giving sum from 1+N-1+N to N+N-1+N-2.
and soon.
Now we have lines from length L to R, now let us try to make different possible sums.
- Taking 1 element :
Possible sums will form a continuous range starting from L and end at R. - Taking 2 elements :
Possible sums will form a continuous range starting from (L+L+1) and end at (R-1+R).
.
.
.
- Taking R-L+1 elements :
Possible sum will form a continous range starting and ending at (L + (L+1) + (L+2) +... + R)
How they form continuous ranges of sum? let us consider x pointers(when we are computing different sums when we select x elements) 1^{st} at L, 2^{nd} at L+1 and soon, shift the last pointer one place to the right to get a different possible sum increasing by 1 till it reaches the end, then move the second last pointer to the right till it reaches the 2^{nd} last place and soon.
Now let us refer to the sum range by selecting x elements as [l_x, r_x](Note you can compute l_x and r_x using arithmetic progression). So to compute the answer all we have to do is take the union of all these ranges(where some ranges might or might not intersect with other ranges) and from the final range/ranges we can compute the count of distinct values of sum we can get adding the lengths of final ranges and we will get our answer. This is fast enough to solve the second subtask.
Note for any x, (l_{x-1} < l_x) and (r_{x-1} < r_x). where l_x = \frac{x*(2*L + x-1)}{2} and r_x = \frac{x*(2*R -x+1)}{2}
So let’s see what we can do to speed up the process. So, what is the condition for a range which we got by selecting x elements to not overlap with the range of sum which we got by selecting x-1 elements, for it, the following condition should be true :
-
r_{x} > l_{x+1}, which is equivalent to
x^2+(L-R)*x+L > 0, which is a quadratic equation. - Now there are 2 possible cases
- If it has imaginary roots, then (L-R)^2 < 4*L, so (R-L+1) is of order O(\sqrt{L}), so we can iterate from 1 to R-L+1 finding l_x and r_x for each x and simply adding them togethor to compute the answer.
- If it has real roots, let it be \alpha and \beta. Now you will note that the positive part which satisfies the equation above i.e. from 1 to \alpha-1 and from \beta+1 to R-L+1 we can iterate through them for x as the length of both these is of order O(\sqrt{L})(and simply adding the r_x-l_x+1 to the answer as they are non-intersecting). Now for the x from \alpha to \beta their ranges will intersect with each other so when we do their union we will get a single range so we can find its length by finding l_{\alpha} and r_{\beta} and adding value r_{\beta} - l_{\alpha} + 1 to the answer.
Note! both \alpha and \beta are around \frac{R-L- \sqrt{(R-L)^2 - 4*L}}{2} and as (R-L)^2>4*L, hence it’s intuitive, and could be proven that they’re of order O(\sqrt{L}).
TIME COMPLEXITY:
- Time complexity per test case is O(\sqrt{L}).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
long long l,r;
long long f(long long x)
{
return x*x+(l-r)*x+l-1;
}
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
scanf("%lld%lld",&l,&r);
long long ans=r*(r+1)/2-l*(l-1)/2,pre=0,suf=r-l;
while (pre<=suf && f(pre)>0)
ans-=f(pre++);
while (suf>pre && f(suf)>0)
ans-=f(suf--);
printf("%lld\n",ans);
}
}
VIDEO EDITORIAL:
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. 
