AOI Study Hub

Appearance

Dorm Labeling ​

Problem Statement ​

Editorial ​

You are given a list of numbers , and you are asked to sort each number by where .

Constraints:

Subtask 1: ​

This is your standard brute force subtask: for each number, just calculate their by iterating over all of and saving the maximum GCD witnessed so far.

For one pair of elements, there is a complexity of to compute the GCD. For each element, we need to compute pairs, and there are elements so the complexity is .

The additional time alloted to sorting by {} is , which is dwarfed by the term. The complexity doesn't change. A solution of this complexity solves the subtask for .

Subtask 2: All are prime. ​

The assumption that are prime helps cut down the computation for each immensely: the GCD of two primes numbers p, q is either (when ) or (when ). Consequently, each is either or for each . Students can simply use a set data structure to detect duplicate primes ( per check) and set accordingly. Since there are elements and operations per element, the elements can be determined in time.

Once again, sorting has the same complexity so the final solution complexity isn't any different. This solves the subtask for .

Subtask 3: . ​

This subtask was added to introduce the idea of eliminating duplicates. There are two important properties of GCD that are used here:

  • For all integers , we have .
  • The GCD between an element and any other integer is at most .

These two properties are pretty intuitive: the largest number that can divide and is , and there is no number larger than that divides .

How are these two facts useful? Well, one can observe that if any occurs more than once, we already know that is atleast . However, we also know that there is no GCD larger than obtainable between and another number. We can thus eliminate all duplicate elements and set for said elements. There will be at most unique values remaining. We can use the quadratic time solution provided by the first subtask to compute remaining values .

This solves the problem in time.

Subtask 4: are distinct integers between 1 and . ​

For all numbers , we know that there exists a multiple in the array, and we know that , so their .

However, for numbers , we need a little more work: we need to find the largest divisor of each . One can observe that this is the same as finding the smallest divisor of , as we can just divide by its smallest divisor to get its largest divisor. Since this divisor is always prime (there is a simple proof by contradiction), we simply have to use a modified eratosthenes' sieve to find the smallest prime that divides each . This takes time and space, which is doable for .

Once we have all , we simply sort, which gives the dominant term of our solution.

Subtask 5: For all , we have atleast one such that . ​

The reasoning in the previous subtask in useful here as well, as a sieve style solution is needed.

The constraint has an interesting consequence: If each dorm has one such that , then all of the numbers with that dorm number are going to be multiples of the smallest value. Thus, finding the dorm number of any consists of finding the largest that divides it. Here is where the most important idea for this problem comes to mind: you may actually use each to do this by setting as the largest available multiple of

The reason this is possible is that, in the worst case, you have to do at most reads and writes. Thus, you can compute the of each element in steps.

After sorting, you have a final complexity of , which solves the problem for our constraints.

Subtask 6: Full Solution ​

The final solution for the problem consists of using the previous idea and doing the following for each between to : if there exists two values that are divisible by , then we set their value as . This works because the last number set in each is the largest number that divides and another number present in . We can do this quickly over a frequency array in time (bound seen in previous subtask), and thus efficiently compute our values.

This fully solves the task.

Here is a sample implementation of the full solution:

cpp
#include <bits/stdc++.h>
using namespace std;

int MAX = 1e6;

int main()
{
    
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n, buf;
    cin >> n;
    
    vector<int> vs(n+1, 0), freq(MAX+1, 0);

    for(int i = 0; i < n; ++i){    
        cin >> vs[i];
        if(freq[vs[i]] != 0) freq[vs[i]] = vs[i];
        else freq[vs[i]] = 1;
    }
    

    for(int i = 2; i < MAX+1; ++i){
        
        int valmod = 0, prev;
        
        for(int j = i; j < MAX+1; j += i){

            if(freq[j]){

                if(valmod == 0) prev = j;
                else if(valmod == 1) freq[prev] = max(freq[prev], i);
                
                if(valmod > 0) freq[j] = max(freq[j], i);
                valmod++;

            }
            
        }
    }

    vector<int> sorting(n, 0);
    iota(sorting.begin(), sorting.end(), 0);
    
    sort(
        sorting.begin(), sorting.end(), 
        [&](int &a, int &b){
            
            if(freq[vs[a]] < freq[vs[b]]) return true;
            if(freq[vs[a]] > freq[vs[b]]) return false;

            if(vs[a] < vs[b]) return true;
            if(vs[a] > vs[b]) return false;

            return a < b;
        }
    );
    
    for(int i = 0; i < sorting.size(); ++i){
        cout << sorting[i] + 1; 
        if(i < sorting.size() - 1) cout << " ";
    }
    

    return 0;
}