Editorial for DMOPC '21 Contest 6 P1 - Bigger Big Integer

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: 4fecta

Subtask 1

For this subtask, notice that the tens digit contributes more towards the value of the number than the ones digit, so we should always ensure that it is the larger of the two digits.

Time Complexity: $\mathcal{O}(1)$ ~\mathcal{O}(1)~

Subtask 2

For this subtask, we may simply simulate swapping every pair of adjacent digits and compare it to the current best answer (using either a String or BigInteger class).

Time Complexity: $\mathcal{O}(D^2)$ ~\mathcal{O}(D^2)~

Subtask 3

For this subtask, note that we should swap at the first index pair $i$ ~i~ and $i+1$ ~i+1~ for which $X_i < X_{i+1}$ ~X_i < X_{i+1}~. Intuitively, increasing the value of the $i$ ~i~-th digit is better than increasing the value of any later digit because of the relative significance of each place value.

Time Complexity: $\mathcal{O}(D)$ ~\mathcal{O}(D)~

Comments

There are no comments at the moment.