Editorial for SAC '22 Code Challenge 3 P3 - Bob Sort - Olympiads Online Judge

Editorial for SAC '22 Code Challenge 3 P3 - Bob Sort

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: maxcruickshanks

First, find $\lfloor \log_{10}(\max(A_i)) + 1 \rfloor$ $⌊ \log_{10} (max (A_{i})) + 1 ⌋$ by iterating across the array.

Second, create an array of pairs that store the value modulo the respective round (e.g., for round 1, mod the value by $10^1$ $10^{1}$ ; for round 2, mod the value by $10^2$ $10^{2}$ ; etc.).

Third, sort that array by the modulo value using a custom comparator or built-in functions.

Finally, output that round and repeat the second and third steps until you have reached the final round.

Time Complexity: $\mathcal{O}(N \log(N) \lfloor \log_{10}(\max(A_i)) + 1 \rfloor)$ $O (N \log (N) ⌊ \log_{10} (max (A_{i})) + 1 ⌋)$

Comments

There are no comments at the moment.