Recently, I have been quite intrigued by the mathematical breakthroughs published by OpenAI and other frontier AI labs, especially in breaking previously conjectured time complexity lower bounds for many well-known problems. I think the community of Codeforces would greatly benefit from seeing some similar discoveries, so this is the first of many blogs on SONoptimized algorithms.↵
↵
Many Codeforces problems present a scenario with some length variable $n$, typically around the size of $2 \times 10^5$. It is also very common to see an array $a$ of length $n$, with integer elements $a_i \leq 10^9$. We will see that, if we must sort these elements, we can actually achieve a time complexity of $O(n \log^{1 - \epsilon}n)$ time, with $\epsilon = 1$.↵
↵
**Key observation:** $n^2 = (2 \times 10^5)^2 = 4 \times 10^{10} > \max(a_i)$↵
↵
Consider all $a_i$ in base $n$. Because $n^2 > \max(a_i)$, we know that they can all be represented in the form $xy_n$ (with $x = \lfloor a_i/n \rfloor, y = a_i \% n$). Now, the following method will suffice to sort the array:↵
↵
1. Allocate an array $L$ of $n$ empty lists↵
2. Iterate $a_1$ through $a_n$, appending $a_i$ to $L_{(a_i \% n + 1)}$↵
3. Empty array $a$, and iterate $L_1$ through $L_n$, concatenating each $L_i$ to the end of $a$↵
4. Empty all the lists within $L$↵
5. Iterate $a_1$ through $a_n$, appending $a_i$ to $L_{(\lfloor a_i/n \rfloor + 1)}$↵
6. Repeat step (3)↵
↵
As each step will only take $O(n)$, the entirety of this sorting process will be linear.↵
↵
<spoiler summary="Implementation">↵
```↵
void sort(int n, vector<int>& a) {↵
vector<vector<int>> L(n);↵
for (int a_i : a) L[a_i % n].push_back(a_i);↵
a.clear();↵
for (vector<int> L_i : L) for (int a_i : L_i) a.push_back(a_i);↵
for (int i = 0; i < n; ++i) L[i].clear();↵
for (int a_i : a) L[a_i / n].push_back(a_i);↵
a.clear();↵
for (vector<int> L_i : L) for (int a_i : L_i) a.push_back(a_i);↵
}↵
```↵
</spoiler>↵
↵
↵
Many Codeforces problems present a scenario with some length variable $n$, typically around the size of $2 \times 10^5$. It is also very common to see an array $a$ of length $n$, with integer elements $a_i \leq 10^9$. We will see that, if we must sort these elements, we can actually achieve a time complexity of $O(n \log^{1 - \epsilon}n)$ time, with $\epsilon = 1$.↵
↵
**Key observation:** $n^2 = (2 \times 10^5)^2 = 4 \times 10^{10} > \max(a_i)$↵
↵
Consider all $a_i$ in base $n$. Because $n^2 > \max(a_i)$, we know that they can all be represented in the form $xy_n$ (with $x = \lfloor a_i/n \rfloor, y = a_i \% n$). Now, the following method will suffice to sort the array:↵
↵
1. Allocate an array $L$ of $n$ empty lists↵
2. Iterate $a_1$ through $a_n$, appending $a_i$ to $L_{(a_i \% n + 1)}$↵
3. Empty array $a$, and iterate $L_1$ through $L_n$, concatenating each $L_i$ to the end of $a$↵
4. Empty all the lists within $L$↵
5. Iterate $a_1$ through $a_n$, appending $a_i$ to $L_{(\lfloor a_i/n \rfloor + 1)}$↵
6. Repeat step (3)↵
↵
As each step will only take $O(n)$, the entirety of this sorting process will be linear.↵
↵
<spoiler summary="Implementation">↵
```↵
void sort(int n, vector<int>& a) {↵
vector<vector<int>> L(n);↵
for (int a_i : a) L[a_i % n].push_back(a_i);↵
a.clear();↵
for (vector<int> L_i : L) for (int a_i : L_i) a.push_back(a_i);↵
for (int i = 0; i < n; ++i) L[i].clear();↵
for (int a_i : a) L[a_i / n].push_back(a_i);↵
a.clear();↵
for (vector<int> L_i : L) for (int a_i : L_i) a.push_back(a_i);↵
}↵
```↵
</spoiler>↵
↵
