Internet Problem Solving Contest

• Correct output for Q1
• Correct output for Q2
• Python 3 program solving Q1
• Python 3 program solving Q2

Let us assume that all ℓ_i are either integers or consist of lowercase English letter only. A label consisting of a mixture of digits and letters cannot be a valid label, and a label that begins with a 0 cannot be a valid label either. We can cut the sequence before the first such offending label before processing it in the ways described below.

Easy subproblem

For the easy subtask it was sufficient to try all reasonable possibilities (remember that k ≤ 2) and to pick the best one among them.

In other words, we can try the following cases:

• For k = 0 we just generate the sequence of positive integers.
• For k = 1 we try all possible 1 ≤ d₁ ≤ n, for each of them we check that ℓ_di is a 4-character string, and if it is, we generate the corresponding “Fizz sequence”.
• For k = 2, once we have a d₁ that was valid for k = 1, we also try all d₂ > d₁ and whenever we find one that produces a second valid label, we generate the corresponding Fizz Buzz sequence.

Each time we gerate a sequence, we simply find its longest prefix that matches the input sequence.

Easy subproblem again

The previous solution works but depending on the implementation and programming language used it can already be annoyingly slow. Luckily, there is a simple improvement that will speed up the search significantly.

Suppose we are in the case k = 1 and we found the smallest j such that the given label ℓ_j is a string. Then obviously d₁ = j is the only possibility we need to try. Larger d₁ won’t give us a better solution because its sequence will have the number j instead of the correct label ℓ_j in j-th position.

Then, in the case k = 2, this d₁ is again the only possible d₁ for the same reason. So instead of Θ(n²) pairs (d₁, d₂) we now only have to try Θ(n) possible d₂ with this single d₁.

Hard subproblem

Instead of applying brute force we will now try to deduce the d_i and s_i greedily. This solution will be a fairly straightforward generalization of our better solution for the easy subproblem.

We will go through the given labels from 1 to n. At the beginning, there are no pairs (d_j, s_j).

Each time we process a new label ℓ_i, there are two possibilities:

1. The label ℓ_i is an integer. In this case we need to check two things. First, i must not be a multiple of any of the d_j we already have. Second, ℓ_i must actually be i, not some other integer. (Did you miss this on your first try?) If either check fails, we have no way of saving it, this is the end of the valid prefix.

2. The label ℓ_i is a string. In this case we look at the pairs (d_j, s_j) we already determined, and we use them to construct the (possibly empty) label ℓ_i′ we should see according to what we know. Now there are three cases:

   • If ℓ_i = ℓ_i′, everything is in order and we move on.
   • If ℓ_i′ is not a proper prefix of ℓ_i, there is no way to fix this problem and thus this is the end of a valid prefix.
   • If ℓ_i′ is a proper prefix of ℓ_i, there is exactly one way to fix this problem: by introducing a new rule with step = i and label = the missing part of ℓ_i.

This way we incrementally construct the only possible set of rules that corresponds to the prefix we already processed. Hence, when we get stuck, we can be certain that the solution we just found is optimal.

An alternate implementation of the same idea is that whenever you determine a new rule (d_i, s_i), you immediately look at all multiples of d_i. If the label of a multiple of d_i starts with s_i, you remove the prefix s_i and keep the rest of the label. And if it doesn’t, you cut off the input sequence at that point.