PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
For an array A, we define its score as follows:
- Repeat this process N-2 times: if \gcd(A_1, A_3) \leq \gcd(A_2, A_3), delete A_1. Otherwise delete A_2.
Re-index the elements to start from 1 after the deletion. - The score is the final value of A_1.
You’re given N, X, Y. Find any array of length N containing distinct integers in [1, N] such that A_N = X, A_{N-1} = Y, and \text{score}(A) \neq Y.
EXPLANATION:
Since the algorithm to compute score has us going from left to right, observe that after making the first i moves, we’ll be left with exactly one element that was originally among indices [1, i+1]; as well as all elements at indices \ge i+2.
Let Z_i denote the only element among indices [1, i+1] that remains after the first i moves.
Let’s look at the very last move: just before it’s made, the array will look like [Z_{N-3}, Y, X], and then either Z_{N-3} or Y will be deleted.
We want \text{score}(A) \neq Y, which means Y must be deleted in the last move.
For this to happen, \gcd(X, Z_{N-3}) \gt \gcd(X, Y) must hold.
In particular, if there’s no integer in [1, N] (excluding X and Y) with a larger gcd with Y than \gcd(X, Y), no solution can exist at all.
Otherwise, let’s find any K \in [1, N] such that \gcd(X, K) \gt \gcd(X, Y) (and K \neq X, Y), and try to arrange the first N-2 elements so that their result is K, i.e. Z_{N-3} = K.
It’s quite hard to control what’s going on if we place K at the start or middle of the array, since we’ll need to ensure it goes a long period of time without getting deleted.
So, a reasonable idea is to try and place it at the very end.
Let’s thus set A_{N-2} = K.
Now, how do we ensure that A_{N-2} doesn’t get deleted?
For this to happen, we look at the penultimate move.
The array will look like [Z_{N-4}, K, Y, X].
Then, if \gcd(Z_{N-4}, Y) \leq \gcd(K, Y), Z_{N-4} will be deleted; otherwise K will be deleted.
So, we need to find a way to make \gcd(Z_{N-4}, Y) not larger than \gcd(K, Y).
One immediate idea is to try and make \gcd(Z_{N-4}, Y) equal 1, since the condition will certainly be satisfied then.
One way of doing this is to just choose Z_{N-4} = 1, since \gcd(1, Y) = 1 for any Y.
Again, because control over long lengths of time is hard, we place 1 at the very end, i.e. set A_{N-3} = 1.
This brings us back to the same analysis: how do we ensure 1 isn’t deleted beforehand?
Again, looking at the previous move, we see the array will look like [Z_{N-5}, 1, K, Y, X].
So, we’d need \gcd(Z_{N-5}, K) \leq \gcd(1, K).
However, we know \gcd(1, K) = 1 for sure - meaning Z_{N-5} should satisfy \gcd(Z_{N-5}, K) = 1.
Suppose such a value (other than 1, X, Y) exists; let’s set it to be A_{N-4}.
It turns out that this is enough!
To see why: note that the array before the previous move looks like [Z_{N-6}, A_{N-4}, 1, K, Y, X].
But \gcd(Z_{N-6}, 1) = 1 = \gcd(A_{N-4}, 1), so Z_{N-6} will certainly be the element deleted at this stage, no matter what it is - after which our construction of the last 5 elements will guarantee that the score is not Y.
This means after the last 5 elements have been fixed using our above algorithm, the remaining N-5 values can be arranged in any order at all and we’ll be fine!
There are a couple of details to take care of here though.
First and foremost is the existence of A_{N-4}, i.e. a value in [1, N] other than 1, X, Y that is coprime to K.
It turns out that such a value always exists, as long as N \geq 7.
Proof
First, note that since K was chosen to be such that \gcd(X, K) \gt \gcd(X, Y), K is certainly not coprime to X.
Y might be coprime to K, but either way at most one value coprime to K is forbidden.This means, if we can always find two different integers coprime to K, at least one of them will be available for sure.
Now let’s look at a couple of cases.
First, suppose 2 \lt K \lt N.
Then, we know that K-1 and K+1 are certainly coprime to K, and K-1 \gt 1 as well.
So, at least one of them is available to us.Next, suppose K = 2.
Since N \geq 7, we know 3 and 5 are coprime to 2, and so at least one of them will be available.K = 1 is never going to happen since we know K is not coprime to X.
That leaves the case of K = N.
There are now several different arguments that can be made.
- For all N \geq 7, we have \phi(N) \gt 2, where \phi(N) denotes the totient function of N, i.e. the number of integers in [1, N] coprime to N.
Since \phi(N) \gt 2, and we know 1 is always coprime to N, this means we have at least 2 coprimes that are not 1, and we’re done.- Alternately, a more intuitive idea is to note that N is coprime to N-1, and also there must be some prime smaller than N-1 that doesn’t divide N.
This is because it’s impossible for N to be divisible by all the primes smaller than N-1: there are too many of them, and their product will exceed N very quickly.
If N \lt 7 you can simply brute-force all permutations to check if an appropriate permutation exists, so we’re done here.
The second issue is that we explicitly used the value 1 in our construction - which is not possible if either X or Y are themselves 1, since values need to be distinct.
So, we need to further look at the cases of X = 1 or Y = 1.
The case of X = 1 is trivial: it is coprime to everything, so no matter what we do we’ll have \gcd(Z_{N-3}, Y) = 1 = \gcd(X, Y), meaning Z_{N-3} will be deleted and the score will be Y.
So, if X = 1 no solution can exist anyway (note that this would’ve been already covered when we checked for some K with \gcd(X, K) \gt \gcd(Y, K) so there’s no need to explicitly run this check again.)
As for Y = 1: if we find any K such that \gcd(X, K) \gt \gcd(Y, K) = \gcd(1, K) = 1, we can place it at index N-2 and arrange the remaining N-3 elements can be arranged in any order.
This is because, after N-4 moves, the array will look like [Z_{N-4}, K, 1, X], after which:
- \gcd(Z_{N-4}, 1) = 1 = \gcd(K, 1), so Z_{N-4} will be deleted.
The array is [K, 1, X]. - \gcd(K, X) \gt 1 by choice of K, so Y = 1 will be deleted and the score is not Y as we desired.
In summary:
- If N \lt 7, bruteforce over all N! permutations and see if an appropriate one exists.
6! = 720 so this is easily fast enough; and if you’re still worried you can just run the bruteforce once and store all the answers. - For N \geq 7, first find any integer K \in [1, N] other than X or Y such that \gcd(K, X) \gt \gcd(Y, X).
This can be done in linear time by just testing everything. - If no such K exists the answer is -1, otherwise:
- If Y = 1, the last three elements of A are [K, 1, X] and the other elements can be arranged in any order.
- If Y \gt 1, find any integer K_2 other than 1, X, Y such that \gcd(K_2, K) = 1.
The last five elements are [K_2, 1, K, Y, X], and the remaining N-5 elements can be arranged in any order.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, x, y; cin >> n >> x >> y;
if (n <= 6) {
// Brute
vector p(n, 0);
iota(begin(p), end(p), 1);
bool done = false;
do {
if (p[n-1] != x or p[n-2] != y) continue;
int c = p[0];
for (int i = 1; i+1 < n; ++i) {
if (gcd(c, p[i+1]) <= gcd(p[i], p[i+1])) c = p[i];
}
if (c != y) {
for (int i : p) cout << i << ' ';
cout << '\n';
done = true;
break;
}
} while (next_permutation(begin(p), end(p)));
if (!done) cout << -1 << '\n';
continue;
}
// Find z with gcd(z, x) > gcd(x, y)
int z = 0;
for (int i = 1; i <= n; ++i) {
if (i == x or i == y) continue;
if (gcd(i, x) > gcd(x, y)) z = i;
}
if (z == 0) {
cout << -1 << '\n';
continue;
}
vector a(n, 0), mark(n+1, 0);
a[n-1] = x;
a[n-2] = y;
a[n-3] = z;
mark[x] = mark[y] = mark[z] = 1;
if (y > 1) {
// Find z2 with gcd(z2, z) = 1
int z2 = 0;
for (int i = 2; i <= n; ++i) {
if (i == x or i == y or i == z) continue;
if (gcd(i, z) == 1) z2 = i;
}
assert(z2 > 0);
a[n-4] = 1;
a[n-5] = z2;
mark[1] = mark[z2] = 1;
}
// If not 1, already done
int p = 0;
for (int i = 2; i <= n; ++i) {
if (mark[i]) continue;
a[p] = i;
++p;
}
for (int i : a) cout << i << ' ';
cout << '\n';
}
}