Complete the Word

Source: Codeforces 716B

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.

For now, let’s just determine whether the string is nice or not, and worry about filling in any question marks later.

Start with special cases of the problem. Suppose there are no question marks, i.e. string s is purely alphabetic.

2. Design a subroutine to test whether a given character ch appears in string t of length 26.
   • Approximately how many operations are required?
   • Recorder: write a code snippet which implements this subroutine.
3. Extend this subroutine to test each letter of the alphabet in turn to determine whether each appears exactly once from index i to index i+25 of s.
   • Approximately how many operations are required?
   • Recorder: edit the earlier code snippet to implement this.
4. Hence design an algorithm which determines whether string s is nice by testing each substring independently.
   • Analyse the complexity of your algorithm in terms of n, the length of string s.
   • Estimate the running time of an implementation of your algorithm. What factors are relevant?
   • You do not need to write code for this question.

Now, let’s add back more of the original problem. Suppose string s consists of uppercase letters and question marks, with the task of determining whether it is nice or not.

5. Recall that a length 26 substring containing each letter exactly once makes a purely alphabetic string nice. What change(s) must we make to this criterion in order to apply it to string s?
   • Use approximately the same number of operations as in Q2 above.
   • Recorder: modify your code snippet from Q2 accordingly.
6. Hence design an algorithm which determines whether string s is nice.
   • Use approximately the same number of operations as in Q3 above.
   • Recorder: lead the implementing of a program which executes this algorithm, printing either YES or NO.
   • Reflector: propose some challenging test cases, and explain why they are challenging.
   • Test and debug as required.

It remains to complete the word.

7. Suppose that the length 26 substring starting at index i satisfies the criterion from Q4. Design a subroutine which fills in any question marks within the substring so that each letter appears once within the completed word.
   • Approximately how many operations are required?
   • Recorder: write a code snippet which implements this subroutine.
8. There could still be question marks elsewhere in s. How should we fill those in?
9. Put it all together.
   • Recorder: compose a program which builds on the earlier subroutines to solve the problem.
   • Reflector: propose some challenging test cases, and explain why they are challenging.
   • Test and debug as required.
10. Submit your program for judging!
    • Debug as required.

The solution we’ve developed is sufficient for the given bounds, but it’s far from optimal.

11. Recall that we tested each substring by going through each letter in turn. Can you instead test all letters in parallel?
    • What data structure could help you count the occurrences of each letter?
    • Approximately how many operations are required now, per substring?
12. Modify your earlier solution to make use of this optimisation.
    • Estimate the new running time.
    • Test and submit!

There are even further optimisations available.

13. Until this point, we’ve considered each substring independently. However, consecutive substrings have a lot in common! What information can you carry from one substring to the next, and what updates do you need to make?
    • Approximately how many operations are required now, per substring?
14. Modify your earlier solution to make use of this optimisation.
    • Estimate the new running time.
    • Test and submit!

For an extension, let’s add updates! Note that you need some material from future lectures to solve the following problem.

15. Suppose ZS gives you the length n of the string, initially all question marks, and also m updates (up to 50,000) of the form “change the character at index i of the string to ch”, where ch can be an uppercase letter or a question mark. After each update you must report whether or not it is possible to fill in any missing letters so that the resulting word is nice.

    Sample Input

    26 3
    1 A
    2 A
    1 B

    Sample Output

    YES
    NO
    YES

    Explanation

    The first line indicates that the string initially has 26 question marks, and three updates will follow.

    • After the first update, there are many valid strings. One example is AZYXWVUTSRQPONMLKJIHGFEDCB.
    • The second update makes the task impossible, as no string AA... can have all letters.
    • The final update replaces the first A with a B, so strings such as BACDEFGHIJKLMNOPQRSTUVWXYZ are valid.