PROBLEM LINK:
Division 1
Division 2
Practice
Author: Anton Trygub
Tester: Alexander Morozov
Editorialist: Colin Galen
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: CodeChef September Lunchtime 2020 - All Solutions (Div. 1 + Div. 2) - YouTube
Official video: - YouTube
