Editorial for Fives

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: Sucram314

Subtask 1

In this subtask, $X = 1$ ~X = 1~. Thus, we must find the smallest number which is not representable on $N$ ~N~ hands.

It turns out that the pattern is 6, 16, 66, 166, 666, 1666, 6666, 16666, 66666 ...

In other words, if $N$ ~N~ is odd, the answer is 6...666, containing $(N+1)/2$ ~(N+1)/2~ 6's. If $N$ ~N~ is even, the answer is 16...666, containing $N/2$ ~N/2~ 6's and $1+N/2$ ~1+N/2~ digits in total.

In python, this can be written compactly as "16"[n%2]+"6"*(n//2).

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

Bonus

Interestingly, this is the exact same pattern found here. In roman numerals, the sequence, I, VI, XVI, LXVI, CLXVI, ..., achieved by concatenating the next type of roman numeral symbol to the left, corresponds exactly to 1, 6, 16, 66, 166, 666, 1666, 6666, 16666, 66666 ..., including $1$ ~1~ as the smallest number which cannot be represented with $0$ ~0~ hands.

Credits to Ivan_Li for noticing this.

Proof

To prove the pattern above is correct, we first note that it is never better to use three or more hands in one group. This is because:

Creating a number $K$ ~K~ from a single group would require at least $\lceil K / 5 \rceil$ ~\lceil K / 5 \rceil~ hands, but the same number could be constructed by concatenating $\lfloor\log_{10}K\rfloor+1$ ~\lfloor\log_{10}K\rfloor+1~ pairs of hands, each pair forming a digit from $0$ ~0~ to $9$ ~9~, with a total of $2(\lfloor\log_{10}K\rfloor+1)$ ~2(\lfloor\log_{10}K\rfloor+1)~ hands. For all $K \ge 16$ ~K \ge 16~, it holds that $\lceil K / 5 \rceil \ge 2(\lfloor\log_{10}K\rfloor+1)$ , so it is never better to use one group to construct numbers greater than or equal to $16$ ~16~.
The numbers from $11$ ~11~ to $15$ ~15~ are not worth constructing with one group, since they would require at least $3$ ~3~ hands, but they can alternatively be constructed with two hands in separate groups by simply concatenating one hand holding up $1$ ~1~ finger and the other hand holding up the desired units digit.
All numbers from $0$ ~0~ to $10$ ~10~ can be constructed with less than or equal to two hands in one group.

Intuitively, concatenation is much more efficient at representing numbers than addition, and addition is only used to give us access to the digits $6$ ~6~ through $9$ ~9~.

From this, we can now determine that among all representations of a number which use the minimum possible number of hands, there exists a representation which uses only groups with either $1$ ~1~ or $2$ ~2~ hands.

With one hand in a group, we can create the digits $0$ ~0~ to $5$ ~5~. With two hands in a group, we can create the digits $6$ ~6~ to $9$ ~9~, and we can technically create the sequence of digits $10$ ~10~, but we could already do that with two hands in separate groups, one holding up $1$ ~1~ finger, and the other $0$ ~0~. Thus, we can simply limit all possible sequences of digits we can make from groups containing $1$ ~1~ or $2$ ~2~ hands to be any single digit from $0$ ~0~ to $9$ ~9~, and we will still be using the minimum number of hands possible.

We can now rephrase the previous statement like so: Among all representations of a number which use the minimum possible number of hands, there exists a representation which constructs and concatenates each digit one by one using groups with either $1$ ~1~ or $2$ ~2~ hands. Since we know that the digits from $0$ ~0~ to $5$ ~5~ can be constructed with $1$ ~1~ hand and the digits from $6$ ~6~ to $9$ ~9~ must be constructed with $2$ ~2~ hands, we can infer that the minimum number of hands to represent a number $K$ ~K~ is the number of digits in $K$ ~K~ in the range $[0,5]$ ~[0,5]~ plus two times the number of digits in $K$ ~K~ in the range $[6,9]$ ~[6,9]~, or in other words,

The minimum number of hands to represent a number $K$ ~K~ is the number of digits in $K$ ~K~ plus the number of digits in $K$ ~K~ which are strictly greater than $5$ ~5~.

So, to solve subtask 1, we must find the minimum number $K$ ~K~ where the value described above exceeds $N$ ~N~. An intuitive way to find this number is to use a greedy approach. Observe that if $K$ ~K~ has a fixed number of digits, we should aim to maximize the number of digits of $K$ ~K~ which are strictly greater than $5$ ~5~ to maximize the minimum number of hands required to represent $K$ ~K~. We should also pick $6$ ~6~, the smallest digit which is striclty greater than $5$ ~5~, so as to minimize $K$ ~K~. If any digits are to be less than or equal to $5$ ~5~, we should make them $0$ ~0~ if they are not leading, and $1$ ~1~ otherwise. Additionally, notice that the number of hands needed to represent $K$ ~K~ is unaffected by permuting the digits of $K$ ~K~. Thus, we should always put the digits which are less than or equal to $5$ ~5~ in front (more significant digits) and the digits which are strictly greater than $5$ ~5~ to the right (less significant digits), so as to minimize $K$ ~K~.

For odd $N$ ~N~, this naturally leads to the construction 6...666, containing $(N+1)/2$ ~(N+1)/2~ 6's. Each 6 requires $2$ ~2~ hands to represent, so in total this number needs at least $(N+1)/2 \times 2 = N+1$ ~(N+1)/2 \times 2 = N+1~ hands to represent, which exceeds $N$ ~N~.

For even $N$ ~N~, this leads to the construction 16...666, containing a 1 followed by $N/2$ ~N/2~ 6's. The $1$ ~1~ takes $1$ ~1~ hand to represent, and each 6 requires $2$ ~2~ hands to represent, so in total this number needs at least $1 + N/2 \times 2 = N + 1$ ~1 + N/2 \times 2 = N + 1~ hands to represent, which exceeds $N$ ~N~.

Proof that all numbers strictly less than these constructed numbers CAN be represented on $N$ hands (and thus these constructed numbers are truly the first which cannot be represented on $N$ hands)

More formally, we can show that all numbers strictly less than the constructed unrepresentable numbers CAN be represented on $N$ ~N~ hands to prove that our constructed unrepresentable numbers are truly the first of their kind.

Claim: For all odd $N$ ~N~, all numbers strictly less than 6...666, which contains $(N+1)/2$ ~(N+1)/2~ 6's, can be represented on $N$ ~N~ hands (specifically with leading zeros as necessary such that the resulting representation contains exactly $(N+1)/2$ ~(N+1)/2~ digits).

Proof: Proceed by induction on odd $N$ ~N~.

Base Case: When $N = 1$ ~N = 1~, all numbers from $0$ ~0~ to $5$ ~5~ can be represented with $1$ ~1~ hand such that each representation contains exactly $(1+1)/2 = 1$ ~(1+1)/2 = 1~ digit.

Induction Hypothesis: Assume for some odd integer $N \ge 1$ ~N \ge 1~ that all numbers strictly less than 6...666, which contains $(N+1)/2$ ~(N+1)/2~ 6's, can be represented on $N$ ~N~ hands (specifically with leading zeros as necessary such that the resulting representation contains exactly $(N+1)/2$ ~(N+1)/2~ digits).

Induction Step: The next odd number is $N + 2$ ~N + 2~. Consider creating $(N+1)/2$ ~(N+1)/2~ pairs of hands, leaving one remaining hand. If we put the extra hand in its own group and make it the most sigificant digit, it can represent any digit from $0$ ~0~ to $5$ ~5~. The remaining $(N+1)/2$ ~(N+1)/2~ pairs of hands can create any sequence of $(N+1)/2$ ~(N+1)/2~ digits from $0$ ~0~ to $9$ ~9~. Thus, all numbers from 0...000 to 59...999 can be represented such that they contain sufficient leading zeros to have exactly $1+(N+1)/2 = ((N+2)+1)/2$ ~1+(N+1)/2 = ((N+2)+1)/2~ digits.

If instead a pair of hands is used to make $6$ ~6~ the most sigificant digit, we will be left with $N$ ~N~ hands, which by our induction hypothesis, can represent any sequence of digits from 0...000 to 6...6665 such that it contains exactly $(N+1)/2$ ~(N+1)/2~ digits using leading zeros as necessary. So by concatenating the $6$ ~6~ at the front, we can represent the remaining numbers from 60...000 to 6...6665 such that they contain exactly $1+(N+1)/2 = ((N+2)+1)/2$ ~1+(N+1)/2 = ((N+2)+1)/2~ digits.

Thus, all numbers strictly less than 6...666, which contains $((N+2)+1)/2$ ~((N+2)+1)/2~ 6's, can be represented on $N+2$ ~N+2~ hands (specifically with leading zeros as necessary such that the resulting representation contains exactly $((N+2)+1)/2$ ~((N+2)+1)/2~ digits).

By induction, the original claim is true.

Now, for even $N$ ~N~, we can either create $N/2$ ~N/2~ pairs of hands to represent any sequence of $N/2$ ~N/2~ digits from $0$ ~0~ to $9$ ~9~, which allows us to represent all numbers from 0...000 to 9...999 containing $N/2$ ~N/2~ digits, OR, we can use one hand to make the leading digit $1$ ~1~, and use the remaining $N-1$ ~N-1~ hands to create any sequence of digits from 0...000 to 6...6665 with leading zeros as necessary to have exactly $((N-1)+1)/2$ ~((N-1)+1)/2~ digits (by our construction for odd $N$ ~N~) to represent any number from 10...000 to 16...6665 on $N$ ~N~ hands. Thus, for even $N$ ~N~, all numbers strictly less than 16...666, which contains $1+N/2$ ~1+N/2~ digits, can be represented on $N$ ~N~ hands.

Subtask 2

Continuing off of the observations found in the proof for subtask 1, we can now generalize to finding the first number greater than or equal to $X$ ~X~ which is unrepresentable. Note that $X$ ~X~ is extremely big in this subtask (up to $10^6$ ~10^6~ digits), so we should not store it as an integer, but rather as a string or list of digits/characters.

If $X$ ~X~ is less than or equal to the smallest unrepresentable numbers found in subtask 1, we should simply print the answer to subtask 1.
If $X$ ~X~ is already unrepresentable, we should simply output $X$ ~X~. This can be checked by seeing if the number of digits in $X$ ~X~ plus the number of digits in $X$ ~X~ which are strictly greater than $5$ ~5~ exceeds $N$ ~N~.
Otherwise, $X$ ~X~ will have somewhere between $\lfloor N/2 \rfloor + 1$ ~\lfloor N/2 \rfloor + 1~ and $N$ ~N~ digits, inclusive. Thus, there will exist a number with the same number of digits as $X$ ~X~ which is unrepresentable (e.g. all $6$ ~6~'s requires at least $2(\lfloor N/2 \rfloor + 1) > N$ ~2(\lfloor N/2 \rfloor + 1) > N~ hands). So, we can fix the number of digits of the next unrepresentable number to be the same as the number of digits of $X$ ~X~ (let this be $D$ ~D~), and we require that the number of digits of the next unrepresentable number which are strictly greater than $5$ ~5~ to be strictly greater than $N - D$ ~N - D~.

Now, consider the behaviour when incrementing $X$ ~X~ until it has strictly greater than $N - D$ ~N - D~ digits which are strictly greater than $5$ ~5~. This will result in changes starting from the least significant digits, and will have new $6$ ~6~'s created (the smallest digit strictly greater than $5$ ~5~). Thus, we can consider replacing some suffix of $X$ ~X~ with $6$ ~6~'s such that $X$ ~X~ has more than $N - D$ ~N - D~ digits which are strictly greater than $5$ ~5~ in total. This can be implemented more easily by looping through the digits of $X$ ~X~ from least significant to most sigificant until a counter has exceeded $N - D$ ~N - D~, where each iteration the current digit is replaced with $6$ ~6~ and the counter is only incremented if it was less than or equal to $5$ ~5~. The reason this works is because the last digit which is replaced by a $6$ ~6~ must be less than or equal to $5$ ~5~ (so it is increased), and thus all the digits after it are subject to change.

Time Complexity: $\mathcal{O}(\log_{10}X)$ ~\mathcal{O}(\log_{10}X)~

Comments

There are no comments at the moment.