Internet Problem Solving Contest

IPSC 2018

Solution to Problem A – Armed bandit

Easy subproblem

Sure, you could go with the spirit of the task and generate the output using a random generator, but why bother? It was much easier to output n ones, or simply to copy the sequence k1, …, kn from the input to the output.

But the actual “pro move” is to solve the hard subproblem and to submit its solution also as the solution to the easy subproblem.

Hard subproblem

When comparing two strings, we are looking at their characters from the left to the right, until we find the first difference. Hence, if we want to make sure that our string will be the lexicographically smallest of all possible strings, we have to construct it greedily from the left to the right. At each position we have to make sure we use the smallest character possible.

What is the best character we can use? There are three possible answers, in order of preference:

Whenever we move to a new wheel, we have to use a 1 as the next character because the numbers on the wheel don’t start with a 0. Afterwards, we may have an option to add some 0s: one if ki ≥ 10 and another if ki = 100.

This gives us a very simple algorithm: