# DECREM - Editorial

Setter: Shahjalal Shohag
Tester: Rahul Dugar
Editorialist: Ishmeet Singh Saggu

Easy

# PREREQUISITES:

Basic Maths and The Pigeonhole Principle

# PROBLEM:

You are given two integers L and R. Find the smallest non-negative integer N such that it satisfies the following condition :

• N % L >N % (L+1)>>N % (R−1)> N % R.

or print -1 if no such integer exists.

# QUICK EXPLANATION:

• If R \geq 2*L then the answer is not possible (using pigeonhole principle).
• We have to represent R-L+1 different values starting from 0 to R-L for minimum N.
• If R < 2*L, then answer will be R.

# EXPLANATION:

To approach the problem easily, let’s refer expression N % L as 1^{st} equation, N % (L+1) as 2^{nd} equation and so on.

Let’s observe the 1^{st} equation of the condition provided, i.e. N % L, and as we know N % L < L. So this equation limits the number of distinct values we can get to L i.e. from 0 to L-1, and as values from, 2^{nd} equation, 3^{rd} equation and soon, should be a non-negative value and less than the value from 1^{st} equation. Also, the values from each equation should be pair-wise distinct. So this means we can represent at max L distinct values. So if (R-L+1 > L) or (R \geq 2*L) then the answer is not possible (using pigeonhole principle).

Now if R < 2*L, then we have to represent R-L+1 different values. Note that If we choose N = R, it satisfies the condition. For the last equation (N % R) we will get 0, for second last equation 1 … for first equation we will get value R-L.

Now we surely know that N can’t have value from the range [0, L) as for each equation it will have same value. Now let’s see why N can’t lie in the range [L, R). If we take N from the range [L, R) then

• N % L = N-L
• N % (L+1) = N-L-1
.
.
.
• N % N = 0 `(as N lies in the range [L, R) )`
• N % (N+1) = N `(this equation doesn't satisfy the condition as previous equation has value 0 which is less than N).`

So there is no value in the range [L, R) which satisfies the condition. So the smallest possible value of N which satisfies the condition is R.

So the final answer is R, if R < 2*L else the answer is not possible.

# TIME COMPLEXITY:

• Time complexity per test case is O(1).

# SOLUTIONS:

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
assert(1 <= t && t <= 100000);
while (t--) {
int l, r; cin >> l >> r;
assert(1 <= l && l < r && r <= 1000000);
if (r >= 2 * l) {
cout << -1 << '\n';
}
else {
cout << r << '\n';
}
}
return 0;
}
``````
Tester's Solution
``````#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}

int sum_n=0;
void solve() {
if(2*l<=r) {
cout<<-1<<endl;
} else
cout<<r<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(8);
int t=1;
//	cin>>t;
fr(i,1,t) {
solve();
}
assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
return 0;
}

``````
Editorialist's Solution
``````#include <bits/stdc++.h>
using namespace std;

void Solve() {
int L, R;
cin >> L >> R;
if(R >= 2*L) cout << -1 << '\n';
else cout << R << '\n';
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int test_case = 1;
cin >> test_case;
for(int i = 1; i <= test_case; i ++) {
Solve();
}

return 0;
}
``````

# VIDEO EDITORIAL (English):

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.

1 Like

Nice problem set

If anyone needs Hindi Explanation - Link

if

Hello @Setter but the minimum and can be the first prime if not N which is closest to R where L!=1.
Shouldn’t this be correct as … in example when input - 10 20
23 satisfies the condition instead of ans=-1.

No , it does not .

23 mod 10 = 3 = a

23 mod 11 = 1 = b

23 mod 12 = 11 = c

and so on…
do you think,
a>b>c .... ? in this case ?

ohh…got it …very silly mistake.

so When N = 23, 23%10 = 3, 23%11 = 1, 23%12 = 9, Here the condition is violated as 9 > 1. Please refer to the condition given in question carefully.

@setter Can anyone explain why this test case should give -1?

Input:
L=3
R=6

Output:
N=7

You Can find the Python3 editorial here:
https://cpblogs-witharyan.blogspot.com/2020/10/decreasing-srrnmieeda-codechef-october.html

b/w 3 and 6 there are 4 numbers.
6 - 3 + 1 = 4
but for any number(n)
n%3 = {0,1,2}
as you can see even if n%3 takes 2.
the ans after modulo will be
2
1
0
there is 1 missing number for last modululo, so it will be a repeat of {0,1,2}

@knight_vertrag it is right. You can find the explanation below
For l = 5 and r = 11
if you are saying 11 is the answer its actually not:
11%5 = 1
11%6 = 5 which itself is greater than 1 so 11 cannot be the answer!
I think you are taking only N mod L and N mod R But the question it says that N%L then N%L+1 … N%R-1 then N%R
Hope you understood!!

1 Like