RRSUM - editorial

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

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

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

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

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

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

Thanks

LonoCoder

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

1 Like

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);

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;

}

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

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.

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))
//