PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: mamaleshrh
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You are given L and R.
Consider the array A = [L, L+1, L+2, ,\ldots R].
Find any array B of the same length as A such that:
- Each integer from L to R appears exactly once in B.
- \gcd(A_i, B_i) = 1 for each i.
EXPLANATION:
The key to solving this task is to start small.
Since L \lt R, let’s look at the smallest possible case: when R = L+1.
We have A = [L, L+1] in this case; and the only options for B are [L, L+1] or [L+1, L].
Of them,
- B = [L, L+1] doesn’t work because \gcd(L+1, L+1) = L+1 \gt 1.
- It’s easy to see that B = [L+1, L] does work, because \gcd(L, L+1) = 1 for any positive integer L.
Why?
Suppose L and L+1 have a common factor, say d.
This means L = xd and L+1 = yd for some integers x, y.
But then 1 = (L+1)-L = yd - xd = d\cdot (y-x).
This means d must also be a factor of 1.
The only factor of 1 is 1 itself, so this forces d = 1, meaning the only common factor of L and L+1 is 1.
Let’s move to a slightly larger case: what about R = L+2?
Now, we have A = [L, L+1, L+2].
As noted earlier, the gcd of “adjacent” integers is 1; so L+1 can be paired with either L or L+2.
However, since elements cannot be paired with themselves, we’re forced to pair L with L+2 at some point.
That is, our only candidates for B are [L+2, L, L+1] and [L+1, L+2, L].
A bit of analysis should tell you that:
- If L is odd, \gcd(L, L+2) = 1, so either of the above arrays are valid as B.
This can be proved similarly to how \gcd(L, L+1) was proved above, and is left as an exercise to the reader. - If L is even, \gcd(L, L+2) = 2 \gt 1, and no valid rearrangement exists.
Finally, let’s extend these results to general L and R.
Let N = R-L+1 denote the total number of elements.
Then,
- If N is even, take two adjacent elements at a time and swap them, using the R=L+1 case.
That is, one possible answer array is
B=[L+1, L, L+3, L+2, L+5, L+4, \ldots, R, R-1] - If N is odd and L is odd, fix the first three elements using the R=L+2 case; after which you have an even number of elements so once again break them into twos.
That is, you’ll get
B=[L+1, L+2, L, L+4, L+3, L+6, L+5, \ldots, R, R-1].
That leaves the case when N is odd but L is even.
As we saw earlier, when N = 3 this case had no solution.
And indeed this extends to larger N too: for any odd N\geq 3, if L is even no solution can exist.
Proof
This can be proved with a relatively simple extension of what we did for the N = 3 case.
There, we observed that L and L+2 would always be paired with each other (or one of them with itself), giving a GCD that’s an even number and so certainly not 1.
Now, suppose we have the elements L, L+1, \ldots, R; with L being even.
The even numbers among them are L, L+2, L+4, \ldots, R-2, R.
In particular, strictly more then half the numbers are even.
The pigeonhole principle now tells us that no matter how the pairing is done, some even number will be paired with some other even number; and their GCD will also be an even number (and hence, not 1).
Hence, no solution exists.
We’ve isolated the only case where no answer exists; and given an explicit construction for every other case. This completes the solution.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>//oset name name.order_of_key(#ele<k) *name.find_by_order(index) less_equal greater greater_equal
#define vi vector<int>
#define pii pair<int, int>
#define mii map<int, int>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define int long long
#define ld long double
#define pb push_back
#define all(v) v.begin(), v.end()
#define back(v) v.rbegin(), v.rend()
#define yes cout << "YES" \
<< "\n";
#define no cout << "NO" \
<< "\n";
#define deb(a) cerr << #a << "=" << (a) << "\n";
#define nl "\n"
#define FastIO \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
using namespace std;
#define mod 1000000007
const int oo = 1e18;
void solve()
{
int l, r;
cin >> l >> r;
if ((r - l + 1) % 2 == 0)
{
for (int i = l; i <= r; i += 2)
{
cout << i + 1 << " " << i << " ";
}
}
else if (r % 2 == 0 && l % 2 == 0)
{
cout << -1 << nl;
return;
}
else
{
for (int i = l; i <= r - 3; i += 2)
{
cout << i + 1 << " " << i << " ";
}
cout << r - 1 << " " << r << " " << r - 2 << " ";
}
cout << nl;
}
signed main()
{
FastIO;
// freopen("P6_5.in", "r", stdin);
// freopen("P6_5.out", "w", stdout);
int test = 1;
cin >> test;
while (test--)
{
solve();
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
l, r = map(int, input().split())
if l%2 == 0 and r%2 == 0:
print(-1)
continue
a = []
if l%2 == 1 and r%2 == 1:
a = [l+1, l+2, l]
l += 3
while l < r:
a.append(l+1)
a.append(l)
l += 2
print(*a)