RESTORE - Editorial

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:

  1. B_i = i
  2. 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;
}

VIDEO EDITORIAL:

2 Likes

great questions

1 Like

Well I simply printed a[i]th prime number for this question.

5 Likes

I considered all even numbers from 2x10^6 to 4x10^6. Whenever a number is in its own index position we choose an even number starting from the end, otherwise the index position which the number points to gets the even number and the number gets the (even number at the index it points to)/2

1 Like

O(N)

int main()
{
int t; cin>>t;
while(t–)
{
int n; cin>>n;
for(int i=1; i<=n; ++i )
{
int x; cin>>x;
cout<<(n-x+1)<<" “;
}
cout<<”\n";
}
return 0;
}

4 Likes

my mind has blown after reading this editorial

6 Likes

I have done something different, see my solution https://www.codechef.com/viewsolution/39579823

1 Like

In the tester’s solution , the vector of prime numbers which consist of prime numbers upto value 10^6 should definately has a size of less than 10^5.
and in the code "pr[b] " is used and b has a range uptil 10^5 , so why does the code work?
Could anyone please explain.

Well, I don’t think that A[i] = N-B[i] (indexing done from 1 to N) works. Let’s take an example
B = [5,2,3,4,5], then A = [1,2,2,1,0] but A[2] divides A[5]. So, B[2] should be 5 but it is 2.

1 Like

yeah,you get it right! , Instead we can use A[i] = (N+1)-B[i] .

hey there, can you please explain how you arrived with that n-x+1 expression ?

1 Like

-> for any i, b[i] >= i
suppose there is a number at a[i], then obviously it should divide itself so the minimum value of max index it can divide is i itself. Though it can be greater than i in case if it divides someone on it’s right side but never smaller than i.

Suppose there is a B[k] which is = k and suppose several positions i on its left side contain B[i] = k .
How can we construct A array ?
We can make all these left side elements that contain k, equal to the value at A[k].
But how we ensure they don’t divide any number after k th position? We will try to keep all the right elements less than A[k].
How?
Since those all A[i] always have value of A[k] which is on their right. One thing we can do is, the more the k the less value we give in A[k].

It will also work if you replace n-x+1 by 1000000 -x

@shivam_18rxx

2 Likes

Is
5 2 3 2 5 an invalid input?

Yes

What should be the output for this:
1
5
2 4 3 4 5

will be consider as invalid input

https://www.codechef.com/viewsolution/39480729
why i am getting wa for subtask 1

After running this code i got RuntimeError but while submitting got AC,
How ? please Explain…

1 Like

I tried to do the same but I am getting TLE. Can you please review my code.
https://www.codechef.com/viewsolution/39796851

Kunwar Pratap Singh Bro, this logic is best than I have seen others,
can you please explain this logic of (n-x+1)?

edit:

saw your explanation and though I had some difficulty in understanding it, being beginner, but it’s nice and clean and easy to implement solution ever for this problem.