PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author & Editorialis: Vasyl Protsiv
Tester: Istvan Nagy
DIFFICULTY:
Simple
PREREQUISITES:
Number theory
PROBLEM:
For an array a of size N let’s construct array B of size N as follows:
B_i = max \space j such that A_i divides A_j. (1 \le j \le N)
Given array B that was constructed from some array A with 1 \le A_i \le 4 \cdot 10^6. Find any suitable array A.
QUICK EXPLANATION:
A_i = N - B_i + 1 for each i from 1 to N will work.
EXPLANATION:
The first observation is that B_i \ge i for each i, because A_i divides A_i.
First subtask:
From the first observation we have that the only possible array B is [1, 2, ..., N] so all we have to do is to ensure that A_j is not divisible by A_i for j > i. One of the possible solutions is to make any decreasing array A. Also we can make an array A of pairwise distinct prime numbers. There are many other solutions.
Full solution:
Consider the following directed graph: for each i from 1 to N there is an edge from i to B_i. In order to simplify the explanations we will use indices in the array and corresponding vertices in the graph interchangeably.
The key observation is that there are no simple paths of length 2.
Proof: assume there is a path i → j → k (j = B_i, k = B_j), such that i \neq j \neq k. By definition of array B we have that A_i divides A_j and A_j divides A_k, therefore A_i divides A_k. From the other side, for each m > j we have that A_i does not divide A_m. But this contradicts the fact that k > j (from the first observation and j \neq k) and A_i divides A_k.
Thus vertices can be divided into two types:
- B_i = i
- B_i > i and B_{B_i} = B_i
We will call two vertices u and v equivalent if B_u = B_v. Note that all vertices can be partitioned into equivalence classes.
We claim that it’s always possible to create array A such that for each equivalence class all elements have the same value A_i within its class.
Proof:
Consider any valid answer A. Let’s define array A' as follows: A'_i = A_{B_i}, so now each element has same value A' as value A in rightmost element from its equivalence class. Clearly B_i can’t become smaller because A'_i still divides A'_{B_i}. And B_i can’t become larger because we only changed A'_i for vertices of second type, and if there were some indices i and j such that j > B_i and A'_i divides A'_j (notice that A_i divides A'_i) then there would be index k = B_j that k > B_i and A_i divides A_k. This contradicts the fact that A was some valid answer, so we can conclude that A' is also valid answer.
Hence now we can ignore vertices of the second type, and only assign values to entire equivalence classes.
Now clearly if for each i of the first type A_i doesn’t divide any A_j such that j > i then for each i A_i doesn’t divide any A_j such that j > B_i, because otherwise A_{B_i} (which is vertex of first type) would divide A_j.
Thus we have reduced our full problem to the problem from the first subtask. Now let’s assign any decreasing sequence of values to our classes (assuming numbering classes by the index of rightmost element). Also, we can assign pairwise distinct prime numbers, this way correctness is even more obvious. There are also many other solutions.
Time complexity is O(N) to assign decreasing sequence or O(N + maxA \cdot log(log(maxA))) to assign prime numbers.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VL = vector<LL>;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define FILL(a, b) memset(a, b, sizeof(a))
void dout() { cerr << endl; }
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
cerr << H << ' ';
dout(T...);
}
void solve()
{
int n;
cin >> n;
VI b(n);
FOR(i, 0, n)
{
cin >> b[i];
b[i]--;
}
VI a(n);
FOR(i, 0, n)
{
a[i] = n - b[i];
}
for (auto x : a)
{
cout << x << " ";
}
cout << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
using namespace std;
//RESTORE
int main(int argc, char** argv)
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.precision(10);
cout << fixed;
const int MAX = 1'500'002;
vector<bool> p(MAX, true);
vector<int> pr;
fore(i,2 ,MAX-1)
{
if (p[i])
{
int j = 2 * i;
while (j < MAX)
{
p[j] = false;
j += i;
}
pr.push_back(i);
}
}
int T;
cin >> T;
forn(tc, T)
{
int N, b;
cin >> N;
vector<int> B(N), A(N);
forn(i, N)
{
cin >> b;
cout << pr[b] << ' ';
}
cout << endl;
}
return 0;
}