GCDOPS - Editorial

PROBLEM LINK:

Division 1
Division 2
Practice

Author: Anton Trygub
Tester: Alexander Morozov
Editorialist: Colin Galen

(My) video
Official video

DIFFICULTY:

Simple

PREREQUISITES:

Math, Number Theory, Observations

PROBLEM:

You have a sequence a_1, a_2, \dots, a_n of integers, where a_i = i. You’re also given a sequence of n integers b_1, b_2, \dots, b_n, where b_i \leq a_i for all i. You may perform some number (possibly zero) of the following operation: choose two indices i, j, and set both a_i and a_j to \gcd(a_i, a_j). Find out if it’s possible to make all a_i = b_i.

QUICK EXPLANATION:

Main solution

It’s only possible if for all i, a_i is divisible by b_i, otherwise impossible.

EXPLANATION:

Main solution

What’s the scope of values we can set a_i to using the operation? If we want to set a_i to some x, and a_i isn’t divisible by x, then it’s impossible for the GCD of any other number and a_i to be x, as x isn’t even a divisor of a_i. So our first condition is that for all i, a_i must be divisible by b_i, otherwise it’s immediately impossible.

It turns out this is the only condition. The next step in piecing together this solution is the observation that if you select some i, j where a_i is directly divisible by a_j, their GCD is a_j by definition. So after the operation, a_j is unchanged. This is cool because all of the numbers 1 \dots n are present in the array. So if we process a_i before we process any of its divisors, since b_i is assumed to be a divisor of a_i, we can make a_i correct without affecting any other value in the array by just selecting b_i as the other index.

We can “process a_i before we process any of its divisors” simply by going backwards through a, since all divisors of a number are less than or equal to it. So as long as b_i divides a_i for all i, a solution exists.

TIME COMPLEXITY:

Main solution

O(n) for reading in the input and checking if all b_i are divisible by a_i.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
void solve()
{
    int n;
    cin>>n;
    vector<int> b(n);
    for (int i = 0; i<n; i++) cin>>b[i];
    for (int i = 0; i<n; i++) if ((i+1)%b[i]) {cout<<"NO"<<endl; return;}
    cout<<"YES"<<endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
 
    int t; cin>>t;
    while (t--) solve();
}
Tester's Solution
#include <bits/stdc++.h>
 
using namespace std;
using nagai = long long;
 
int main() {
	 cin.tie(0);
	 ios::sync_with_stdio(false);
	 int t;
	 cin >> t;
	 while(t--) {
		  int n;
			cin >> n;
			vector<int>b(n);
			for(auto&x : b) cin >> x;
			bool ok=true;
			for(int i=0;i<n;++i)
				ok &= (i + 1) % b[i] == 0;
			cout << (ok ? "YES" : "NO") << '\n';
	 }
	 return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
 
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
typedef long long ll;
 
void solve(int tc = 0) {
	ll n, x;
	cin >> n;
	
	bool pos = 1;
	for (ll i = 0; i < n; i++) {
		cin >> x;
		pos &= ((i + 1) % x == 0);
	}
	
	cout << (pos ? "YES\n" : "NO\n");
}
 
int main() {
	send help
	
	int tc = 1;
	cin >> tc;
	for (int t = 0; t < tc; t++) solve(t);
}   

Video Editorial(s)

My video: https://youtu.be/TB_krkk_U9A?t=260
Official video: https://www.youtube.com/watch?v=YlSDSgrEUVk

10 Likes

Nice questions

BTW if anyone need Hindi Editorial Video- Link

2 Likes

Can someone please tell me why this is wrong?

I assume that the answer is yes, then if I find i such that i % bi != 0, the answer is no

Wait, what? Are you thinking of LCM? That example doesn’t work because a constraint is b_i \leq a_i.

1 Like

Your problem is that you may break the loop in the middle of reading the input for the test case. That means you’ll think the remaining data for the current test is the start of the next one.

1 Like

oooh. Thanks a lot that was driving me crazy

You can’t quantify the amount of frustration that type of bug has caused me to feel :frowning:

2 Likes

Can someone explain what is wrong in this [solution] (https://www.codechef.com/viewsolution/38241095)?
I think my logic was same and i tried this same thing for almost an hour…but my solution wasn’t accepted…could sm1 explain pls?

I think you’re printing N0 instead of NO (difference: zero vs. O)

1 Like

Oh Goooooooddddddddd. Ok i never felt this dumb b4. I mean i wasted over 1.5 hrs on this, submitted same logic so many times and then this was the mistake. God. Thanks for pointing it out. I really had an headache when it didnt work. Thank you

2 Likes

https://www.codechef.com/viewsolution/38234419

Can anyone tell whats wrong with this approach
sorry got it…no need to reply

1 Like

Definitely i am dumb i couldnt even solve this easy questions.

1 Like

GCD operations | CodeChef September Lunchtime 2020 Division 2 | CODECHEF

hints to understand problem in easy

00

think in reverse manner i.e., bn,bn-1,…,b2,b1

01

bn = gcd (an,ai)

10

there exist some ai , such that bn = ai (i<=n)
(coz bn is gcd of an and ai ; an>=ai ; array a is series 1 2 3 4 … till an)

11

so ai remains unchanged when we replace ai and an with gcd(ai,an)…

binary overflow

now same argument goes for bn-1,bn-2,… b2,b1
here argue in reverse manner
bn
bn-1
.
.
b1
we made array b from array a
using that gcd operation (in reverse manner)