RRSUM - editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Roman Rubanenko
Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa

DIFFICULTY:

Medium

PREREQUISITES:

Simple Math.

PROBLEM:

Given N.
Let A = {1, 2, , N} and B = {N + 1, , 2 * N}.
Let C contains elements representing sum of pairs of A and B. Note that C is a multiset.
You will be given queries in which you are asked to find cnt of q in C.

Explanation

Note that entries in C will be between N + 2 to 3N.

Given a q, how to find cnt of q in C?

Let us say that number selected from A is x and from B is y.
So x + y = q.
Rewrite as x = q - y.

We see that y should satisfy following inequalities.
N + 1 <= y <= 2N i.e. 1 <= q - y <= N.

You can see that count of valid y will be answer of our problem.

Can you get value of count of valid y from the above inequalities?

Yes, Rewrite both the inequalities as follows.
1 <= q - y <= N will become q - N <= y <= q - 1.
N + 1 <= y <= 2N

So we notice that y should be at least max(q - N, N + 1) and at most min(q - 1, 2N).

Now, can you find count of valid y’s?

Yes, if y lies in the range [L, R], then answer will be R - L + 1.
Note that if L > R, then there is no solution.

Pseudo Code


	long L = max(q - N, N + 1);
	long R = min(q - 1, 2N);
	long long ans = 0;
	if (L > R)
		ans = 0;
	else 
		ans = R - L + 1;

Few Small Points

  • Note that q can overflow from long data type because q can go upto 3 * 10^9. You should use long long data type.

Complexity:
For each query, we are just doing a constant number of operations. So for each test case, if there are queries, our time complexity
will be O(m) per test case.

AUTHOR’S and TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

6 Likes
2

hey… here Clicking on the practice link… it redirects to RRCOPY problem instead of RRSUM. u should correctly redirect to RRSUM problem only

3

please swap the PROBLEM LINK with that of “RRCOPY - editorial”

4

From the editorial,

We see that x should satisfy following inequalities.
1 <= y <= N i.e. 1 <= q - x <= N.
N + 1 <= x <= 2N

Looks like there is some typo here.
x is from set A and should satisfy the criteria 1 <= x <= N
y is from set B and should satisfy the criteria N+1 <= y <= 2N

Editorialist, can you please confirm?

1 Like
5

corrected, Actually if validity of x implied validity of y and vice versa. This is why the analysis will be go exactly the same.

6

Loved the problem and editorial.
It would be great if you can point me to more such inequality based problems!

Thanks

LonoCoder

7

I fail to understand how come the number of count equals to be R-L+1?

1 Like
8

Yes, Rewrite both the inequalities as follows.

1 <= q - y <= N will become q - N <= y <= q - 1.

N + 1 <= y <= 2N

So we notice that y should be at least max(q - N, N + 1) and at most min(q - 1, 2N).

I don’t understand the 2nd line. How does left becomes right? Could you explain more precise?

And how can “So we notice that y should be at least max(q - N, N + 1) and at most min(q - 1, 2N)” be correct?
I don’t notice anything. I notice only that why can’t L be q-N or N+1 why must it be max of the two value.

Here’s my code, it came from observation look longer but I also like your methodology. But I don’t understand your way of thinking yet. It looks useful though.

if (q < 1+n+1 || q > n+n*2) ans = 0; // all formulas came from taking examples on paper

else if (n+1 <= q-n && q-n <= n2) ans = n2 - (q-n) + 1;

else ans = q-(n+1);

9

My solution to this problem. Tell me how is it.
#include<bits/stdc++.h>
#include
using namespace std;

int main()
{
long long int n,m;
scanf("%lld%lld",&n,&m);
long long int ans=0,median;

median=1+(2*n);
while(m--)
{
    long long int x;
    scanf("%lld",&x);
    ans=n-abs(median-x);
    if(ans<0)
    {
        ans=0;
    }
    printf("%lld\n",ans);
}
return 0;

}

10

Really nice problem - I can’t vote yet so expressing my gratitude over the comments. Thank You!

11

I took a little different approach,

long long int answer = min( q-n-2, 3*n-q ) + 1;

This can easily seen once you observe that the frequency first increases and then decreases again.

12

Here’s how I did it:

n, queries = map(int, input().split(' '))

for _ in range(queries):
    query = int(input())

    if query < (n + 1) + 1:
        print(0)

    elif query > n + 2*n:
        print(0)

    else:
        print(n - abs((n + (n + 1)) - query))