CDSUMS - Editorial

PROBLEM LINK:

Practice
Contest

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. :smile:

8 Likes

Couldn’t counter long long overflow so used bigint library lol

1 Like

Well, I used ternary search to find the minimum value of r_x-l_{x+1} (and the corresponding x), then used two binary searchs to find the two roots. This would be O(\log R).But implementation is kinda daunting.

1 Like

@psychik or any one else , can you please provide formal proof of the last part (which proves that complexity will be sqrt(L)).

Lemma: if a^2 \ge b and b \ge 0, a-\sqrt{a^2-b} \le \sqrt{b}

Proof: a-\sqrt{a^2-b}=a-\sqrt{a^2-(\sqrt{b})^2}=a-\sqrt{(a-\sqrt{b})(a+\sqrt{b})} \le a-\sqrt{(a-\sqrt{b})(a-\sqrt{b})}=a-(a-\sqrt{b})=\sqrt{b}

Just apply this lemma to the formula of \alpha and \beta mentioned in the editorial :smiley:

4 Likes

Really like the model solution! I wish I would have done something similar, but I still forced an AC (in 0.00s) by reducing it to pattern finding :wink:

Let r-l+1= len. Now, we obviously now the answer when l=1. The thing to observe is that as l increases for a certain len, the values will form a pattern. More specifically, let jmp = len-2. There will be jmp jumps of value jmp, then jmp reduces by 2. This process will keep repeating till jmp <= 0, and then the value stabilises.

For example, let the len = 6. We’ll find answers for all (l, r):

(1, 6) -> 21
(2, 7) -> 25 (21+4)
(3, 8) -> 29 (25+4)
(4, 9) -> 33 (29+4)
(5, 10) -> 37 (33+4)
(6, 11) -> 39 (37+2)
(7, 12) -> 41 (39+2)
(8, 13) -> 41 (41+0)
(9, 14) -> 41 (41+0)

There are 4 jumps of value 4, then 2 jumps of value 2, and then the value stabilises.

We can easily simulate these jumps (processing an entire jmp value at once, and when we reach an l value greater than one required, then we simply take a few steps back in constant time).

3 Likes

That’s really awesome.

I was also trying to dig up any pattern but failed to do so :slightly_frowning_face:

How did you came around that pattern ?

I wrote a brute force solution, then generated a large test case with a constant length. interestingly, the value stabilised very quickly, and that motivated to look deeper into the pattern.

2 Likes

I think it’s a typo over here. It should have been r_{x}​ < l_{x+1} ?

4 Likes

I was wondering the same, but shouldn’t it be r_{x-1}<l_{x} because we are discussing the condition for [l_{x}:r_{x}] and [l_{x-1}, r_{x-1}] to not overlap, as mentioned here:

And the quadratic equation x^2+ (L-R)*x+L>0 can only be derived if r_x<l_{x+1}, which is much simpler than what we’ll get if we tried to simplify r_{x-1}<l_{x}. @psychik please fix that inequality in editorial. Thanks.