← All solutions

Shortest judge solution: 826 bytes. Shortest team solution (during contest): 836 bytes.

The most naive algorithm would be to simply try all possible bases b (after a moment’s thought one sees that b can be at most y − 1) and see which ones yield only decimal digits. However, the numbers are too big for this to work.

The key observation is that either b must be small, or y written in base b must be small. In particular, if we let d denote the number of digits of y written in the optimal base b, we have that b^d−1 ≤ y. With y ≤ 10¹⁸, this implies that either b < 10⁵, or d < 5. Thus we can check all values of b up to 100 000, and all 4-digit numbers x as the value of y in base b, and see what yields the best solution (this requires a routine for computing b given y in base 10 and y in base b, which is easiest done by binary search over b though one has to be careful about overflows).

In general, for n-bit numbers, the time complexity of this algorithm is 2^O(√n). There is also a polynomial time algorithm for this problem (we leave this as an exercise).