DECREM - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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 readString(int l,int r,char endd){
	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){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
int sum_n=0;
void solve() {
	int l=readIntSp(1,1000000),r=readIntLn(l,1000000);
	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;
	t=readIntLn(1,100000);
	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 (Hindi):

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

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 ?
Hope you got your mistake.

ohh…got it …very silly mistake. :sweat:

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

This is my new blog so please encourage me with your comments! :grinning:

1 Like

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