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 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; for round 2, mod the value by 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)


Comments

There are no comments at the moment.