PROBLEM LINK:
Division 1
Division 2
Practice
Author: Anton Trygub
Tester: Alexander Morozov
Editorialist: Colin Galen
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Math, Number Theory
PROBLEM:
You’re given a circular array a of length n - elements a_n and a_1 are adjacent. You’re also given an array b of length n. In one operation, you can select a value i and a circular subarray of length i, then either add or subtract b_i from all elements in that subarray. Find out if it’s possible to make all elements equal to 0.
QUICK EXPLANATION:
Subtask 1
All operations using i should affect the whole array equally. The minimum effect we can have for a given b_i is f_i = \dfrac{b_i \cdot i}{\gcd(i, n)}. If the array element (say, a_1), is divisible by \gcd(f_1, f_2, \dots, f_n), then it’s possible, otherwise impossible.
Main solution
We can show that these three conditions are necessary and sufficient for having an answer:
- Let’s break all b_i into prime factors. Then, for all prime powers p^k that divide some b_i: let g be the GCD of all i where b_i isn’t divisible by p^k. Then let d = \gcd(g, n). Now, all sums that start at an element \leq d and end at the end of the array (of the form c_1 + c_{d + 1} + c_{2d + 1} + \dots (up to n), c_2 + c_{d + 2} + c_{2d + 2} + \dots (up to n), \dots, c_d + c_{2d} + c_{3d} + \dots (up to n)), must be divisible by p^k.
- Let g be the GCD of all i where b_i > 0. Then let d = \gcd(g, n). Similarly to the previous condition, all sums that start at an element \leq d and end at the end of the array (of the form c_1 + c_{d + 1} + c_{2d + 1} + \dots (up to n), c_2 + c_{d + 2} + c_{2d + 2} + \dots (up to n), \dots, c_d + c_{2d} + c_{3d} + \dots (up to n)), must be equal to 0 (different from first).
- Similar to subtask 1, let d be the GCD of all \dfrac{b_i \cdot i}{\gcd(i, n)}. Now, for every prime divisor p of d: if n is divisible by p^t for some maximal t and d divisible by p^k, then all sums a_1 + a_{p^t + 1} + \dots (up to n), a_2 + a_{p^t + 2} + \dots (up to n), \dots, a_d + a_{p^t + d} + \dots (up to n), must be divisible by p^k.
and the proof for that is in the main explanation.
EXPLANATION:
A lot of this explanation was given by the author himself, to give credit where it’s due (although I modified it some to make it more presentable).
Subtask 1
For any value of i, we can assume all operations done with i will affect all elements in the array equally. We want to add numbers with the lowest divisors possible, as that gives us the most freedom in the end. Say we only use operation i, and change the sum by ki where k is some integer. ki must be divisible by n, so we want the smallest (positive) k that accomplishes this, which is akin to, k times, setting a number x = 0, then setting x := (x + i) \mod n until x becomes 0 again. This is well-known to be \dfrac{n}{\gcd(i, n)}.
We want the quantity \dfrac{ki}{n} as this is the actual sum that will be added to each element, so we can substitute in our value of k to get \dfrac{ni}{n\gcd(i, n)} = \dfrac{i}{gcd(i, n)}. So, to the whole array, we can add \dfrac{b_i \cdot i}{\gcd(i, n)}. Let this quantity be f_i for all i. Then, to the whole array, we can add/subtract all values of f_i to the whole array, and similar to our process of finding k above, we can use these values to add/subtract \gcd(f_1, f_2, \dots, f_n) as well. We can’t do better because every element is divisible by \gcd(f_1, f_2, \dots, f_n), so we can’t change a_1 \mod \gcd(f_1, f_2, \dots, f_n).
That means, if a_1 (and by extension, all the other array elements) is divisible by \gcd(f_1, f_2, \dots, f_n), then we can make the whole array 0, otherwise we can’t change a_1 \mod \gcd(f_1, f_2, \dots, f_n), so it’s impossible.
Main solution (mostly by Anton)
This is more of a formal proof of the solution than anything. Sorry for not being able to build up to the solution as I’ve tried to do for the other problems, but much of this is beyond my ability to come up with.
If all b_i are 0, then we can’t do anything to the array, so it’s only possible if all a_i are also 0. Otherwise, let’s assume at least one of b_i > 0. For notation, let c_i = a_{i + 1} - a_{i}, where we use a_1 for a_{n + 1} (because of the circle).
Now, for a solution to be possible, these conditions must be true:
- Let’s break all b_i into prime factors. Then, for all prime powers p^k that divide some b_i: let g be the GCD of all i where b_i isn’t divisible by p^k. Then let d = \gcd(g, n). Now, all sums that start at an element \leq d and end at the end of the array (of the form c_1 + c_{d + 1} + c_{2d + 1} + \dots (up to n), c_2 + c_{d + 2} + c_{2d + 2} + \dots (up to n), \dots, c_d + c_{2d} + c_{3d} + \dots (up to n)), must be divisible by p^k.
- Let g be the GCD of all i where b_i > 0. Then let d = \gcd(g, n). Similarly to the previous condition, all sums that start at an element \leq d and end at the end of the array (of the form c_1 + c_{d + 1} + c_{2d + 1} + \dots (up to n), c_2 + c_{d + 2} + c_{2d + 2} + \dots (up to n), \dots, c_d + c_{2d} + c_{3d} + \dots (up to n)), must be equal to 0 (different from first).
- Similar to subtask 1, let d be the GCD of all \dfrac{b_i \cdot i}{\gcd(i, n)}. Now, for every prime divisor p of d: if n is divisible by p^t for some maximal t and d divisible by p^k, then all sums a_1 + a_{p^t + 1} + \dots (up to n), a_2 + a_{p^t + 2} + \dots (up to n), \dots, a_d + a_{p^t + d} + \dots (up to n), must be divisible by p^k.
We can show that these conditions are relevant by showing two things: that they’re automatically satisfied in the final state of the array (all 0's), and that doing operations on the array doesn’t change these conditions. If all elements are 0, 0 is both equal to 0 and divisible by p^k, so the conditions are indeed automatically satisfied for the final array.
Now, if we use some sequence of operations from our starting array to the final array, we can reverse those operations to get from the final array to the starting array. Since the conditions hold for the final array, they must thus hold for the starting array as well.
Now, we’ll show that doing operations doesn’t change the conditions. For generality, assume we added b_i to any segment with length i.
- Consider any (and all) p^k. If b_i is divisible by p^k, then nothing changed for this condition. Otherwise, because c is a difference array, exactly two elements of c change. For some x, c_x increases by b_i and c_{x + i} decreases by p_i. But x + i - x = i, and i is divisible by d (by definition), so both b_i and -b_i contribute to the same sum, meaning the sum doesn’t change.
- Analogous to above: any i where b_i > 0 is divisible by d.
- For all prime divisors p of d, suppose n is divisible by p^t, d by p^k, and i by p^s. If s \leq t, then \dfrac{b_i \cdot i}{\gcd(i, n)} is divisible by p^k, so b_i is divisible by p^k, so no element will change modulo p^k. Otherwise, s > t, and all sums with period p^t increase by \dfrac{b_i \cdot i}{p^t} which is divisible by p^k as \dfrac{b_i \cdot i}{gcd(i, n)} is.
So these three conditions are necessary for there to be an answer, since we can work backwards and show that these conditions are required for any valid array. To show that they’re sufficient, we’ll reduce the problem to Subtask 1. Let’s consider only the array c, and our goal is to make them all 0.
One operation lets us pick some x and y where |x - y| = i and add b_i to c_x and subtract b_i from c_y. We can also pick x, y where |x - y| = \gcd(i, n).
For some b_j, we’ll make all of the c_i divisible by all p^k divisible by b_j. If there’s some A divisible by p^{k - 1} where all c_i are divisible by A, we can make all c_i divisible by A \cdot p.
Take any b_i not divisible by p^k. For that b_i, let’s find a new value B_i divisible by b_i, divisible by A, and equal to p^{k - 1} modulo p^k. We know this number exists by chinese remainder theorem. So we can pick an x and a y and add p^{k - 1} to b_x and subtract p^{k - 1} from b_y (modulo p^k for both) for |x - y| = \gcd(i, n). Now we can invoke condition 1: let g be the GCD of all i where b_i isn’t divisible by p^k, then let d = \gcd(g, n). We can do this for all positions on distance d, as long as condition 1 is true, since the modular sum is 0.
So we made all c_i divisible by all p_k, and therefore also all b_i, and therefore the LCM of all b_i. As we did above, we can add/subtract the LCM on the distance d from the second condition, and just like we did before, we can use the second condition to make all c_i = 0.
Now all a_i are equal, and we have subtask 1. From subtask 1, we know we can add/subtract and \dfrac{b_i \cdot i}{\gcd(i, n)} to all elements, and thus add/subtract d = the GCD of all \dfrac{b_i \cdot i}{\gcd(i, n)}. Let all a_i be equal to X, then X is divisible by d if condition 3 is true, meaning we’re done and it’s possible, since we can simply decrease by d until we hit 0.
Why is X divisible by d? If we do one final prime power analysis and suppose n is divisible by p^t, d by p^k, then the sum a_1 + a_{p^t + 1} + a_{2p^t + 1} + \cdots = \dfrac{n \cdot X}{p^t} since all elements are equal to X. This is divisible by p^k (condition 3), and therefore so is X. So X is divisible by all the prime powers composing d, and therefore is divisible by d.
TIME COMPLEXITY:
Subtask 1
O(n\log{10^4}) for finding O(n) GCDs.
Main solution
O(10^4\log{10^4}) for finding divisors (and primes, and maybe sieve) efficiently.
O(n^2) for checking the conditions.
O(n^2 + 10^4\log{10^4}) in total.
SOLUTIONS:
Setter's Solution
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int maxN = 10000;
bool f[maxN + 1];
vector<int> all;
void init() {
for (int i = 2; i <= maxN; i++) {
if (!f[i]) {
f[i] = true;
for (int j = 2 * i; j <= maxN; j += i) {
f[j] = true;
}
int ci = i;
while (ci <= maxN) {
all.emplace_back(ci);
ci *= i;
}
}
}
}
void solve() {
int n;
cin >> n;
assert(1 <= n && n <= maxN);
vector<int> ini(n);
bool has_ini_non_zero = false;
for (int& c : ini) {
cin >> c;
assert(0 <= c && c <= maxN);
has_ini_non_zero |= (c != 0);
}
vector<int> a(n + 1);
bool has_non_zero = false;
for (int i = 1; i <= n; i++) {
cin >> a[i];
assert(0 <= a[i] && a[i] <= 10000);
has_non_zero |= (a[i] != 0);
}
if (!has_non_zero) {
if (has_ini_non_zero) {
cout << "NO\n";
}
else {
cout << "YES\n";
}
return;
}
bool ok = true;
vector<int> dif(n);
for (int i = 0; i < n; i++) {
dif[i] = ini[(i + 1) % n] - ini[i];
}
vector<int> gcd_sums(n + 1);
for (int d = 1; d <= n; d++) {
if (n % d == 0) {
vector<int> gg;
for (int j = 0; j < d; j++) {
int sum = 0;
for (int p = j; p < n; p += d) {
sum += dif[p];
}
gg.emplace_back(sum);
}
for (int j = 0; j < (int)gg.size(); j++) {
gcd_sums[d] = __gcd(gcd_sums[d], abs(gg[j]));
}
}
}
for (int p : all) {
int d = n;
for (int r = 1; r <= n; r++) {
if (a[r] % p != 0) d = __gcd(d, r);
}
assert(n % d == 0);
if (gcd_sums[d] % p != 0) {;
ok = false;
break;
}
}
if (!ok) {
cout << "NO\n";
return;
}
int d = n;
for (int i = 1; i <= n; i++) {
if (a[i] != 0) d = __gcd(d, i);
}
vector<int> gg;
for (int p = 0; p < d; p++) {
int sum = 0;
for (int j = p; j < n; j += d) {
sum += dif[j];
}
gg.emplace_back(sum);
}
sort(gg.begin(), gg.end());
if (gg[0] != gg.back()) {
cout << "NO\n";
return;
}
d = 0;
for (int i = 1; i <= n; i++) {
d = __gcd(d, (a[i] * i / __gcd(i, n)));
}
for (int r = 2; r <= d; r++) {
if (d % r == 0) {
int pr_d = 1;
while (d % r == 0) {
d /= r;
pr_d *= r;
}
int nn = n;
int pr = 1;
while (nn % r == 0) {
nn /= r;
pr *= r;
}
for (int bl = 0; bl < pr; bl++) {
int sum = 0;
for (int c = bl; c < n; c += pr) {
sum += ini[c];
}
if (sum % pr_d != 0) {
cout << "NO\n";
return;
}
}
}
}
cout << "YES\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
init();
int tst;
cin >> tst;
while (tst--) {
solve();
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
using nagai = long long;
nagai gcd(nagai a, nagai b) {
if (a == 0) return b;
if (b == 0) return a;
return __gcd(a, b);
}
nagai lcm(nagai a, nagai b){
return a / gcd(a, b) * b;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
vector<bool>ispr(10005, true);
vector<nagai>pks;
for(int i=2;i<ispr.size();++i) {
if (!ispr[i])continue;
for(int j=2*i;j<ispr.size();j += i)
ispr[j]=false;
nagai pk=i;
while(pk<ispr.size())
pks.push_back(pk), pk*=i;
}
while(t--) {
int n;
cin >> n;
vector<nagai>a(n);
vector<nagai>b(n);
for(auto&x:a)
cin >> x;
for(auto&x:b)
cin >> x;
if (count(a.begin(),a.end(),0) == n) {
cout << "YES\n";
continue;
}
b.insert(b.begin(), 0);
vector<int>c(n);
for(int i=0;i<n;++i)
c[i] = a[(i+1)%n] - a[i];
bool bad=false;
for(int pk:pks) {
bool ok=false;
for(int x:b)
if (x % pk == 0)ok=true;
if (!ok)continue;
nagai d = n;
for(int i=1;i<=n;++i)
if (b[i] % pk)
d = gcd(d, i);
for(int i=0;i<d;++i) {
nagai s = 0;
for(int j=i; j < n; j += d)
s += c[j];
if (s % pk){
bad=true;
}
}
}
nagai d1 = n;
for(int i=1;i<=n;++i)
if (b[i] != 0)
d1=gcd(d1, i);
for(int i=0;i<d1;++i) {
nagai s = 0;
for(int j=i; j < n; j += d1)
s += c[j];
if (s != 0) {
bad=true;
}
}
nagai d=0;
for(int i=1; i<=n;++i)
d = gcd(d, b[i] * lcm(i, n) / n);
if (d == 0) {
cout << "NO\n";
continue;
}
for(int p=2;p<=d;++p) {
if (ispr[p] && d % p == 0) {
nagai pt=1;
while(n%(pt*p) == 0)pt *= p;
nagai pk=1;
while(d%(pk*p) == 0) pk *= p;
for(int i=0;i<pt;++i) {
nagai s =0;
for(int j=i;j<n;j+=pt)
s += a[j];
if (s % pk)
bad=true;
}
}
}
if (!bad)
cout << "YES\n";
else
cout << "NO\n";
}
return 0;
}
Video Editorial(s)
My video: CodeChef September Lunchtime 2020 - All Solutions (Div. 1 + Div. 2) - YouTube
Official video: Adding on Segments (ADDONSEG) | September Lunchtime 2020 | Srikkanth R - YouTube