tanishq2507's blog

By tanishq2507, history, 15 months ago, In English

This base conversion algorithm has an application in this problem 1811E - Living Sequence.Why does the base conversion work here.What do the remainders signify in the base conversion?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
15 months ago, # |
  Vote: I like it +10 Vote: I do not like it

you can think of it like just converting to base 9 (because there are 9 digits) but with different namings/symbols.

»
15 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

In base 10, you can decompose numbers by their decimal cases, for example $$$832 = 8\cdot 10^2 + 3\cdot 10^1 + 2\cdot 10^0$$$. The same goes for an arbitrary base $$$B > 1$$$.

Let $$$n$$$ be a number in base $$$B$$$ with digits $$$d_k d_{k-1} \ldots d_1 d_0$$$. Following the same logic as of base $$$10$$$, $$$n$$$ can be written as $$$d_k\cdot B^k + d_{k-1} \cdot B^{k-1} + \ldots + d_0 \cdot B^0$$$. Now, notice that, all digits have "values" divisible by $$$B$$$, except for digit $$$0$$$. So, we can write $$$n$$$ in the follow way $$$n = B(d_k\cdot B^{k-1} + d_{k-1} \cdot B^{k-2} + \ldots + d_1 \cdot B^0) + d_0$$$. By Euclid's division lemma, the quotient of the division of $$$n$$$ by $$$B$$$ is $$$d_k\cdot B^{k-1} + d_{k-1} \cdot B^{k-2} + \ldots + d_1 \cdot B^0$$$, and the remainder is $$$d_0$$$. Observe that the quotient of that division is the base $$$B$$$ number $$$d_k d_{k-1} \ldots d_1$$$, which is our original number $$$n$$$, without it's last digit. Therefore, we can repeat this procedure until we find all the digits of $$$n$$$.

In the problem you mentioned, you're basically counting in base $$$9$$$, except we are using the digits $$$0, 1, 2, 3, 5, 6, 7, 8, 9$$$ instead of $$$0$$$ to $$$8$$$. So, all you need to do is find the base $$$9$$$ number, and map the digits $$$0, 1, \ldots 8$$$ to $$$0, 1, 2, 3, 5, 6, 7, 8, 9$$$.