Substring Removal Game

Source: Codeforces 1398B

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

You get points for deleting 1s, so it seems natural to take as many 1s as you can on each move. Before we start coding, we should convince ourselves that this strategy is actually optimal, and make plans to calculate the outcome systematically.

2. If we take from a block of k consecutive 1s, should we always take all of them?
   • Consider the opposite; taking less than the whole block.
     • What happens to the rest of those 1s and the corresponding points?
     • How can you easily compare this to the outcome from taking the whole block?

Now we have established that each move consists of taking either 0s or a whole block of 1s.

3. Should we always take 1s instead of 0s (if both are present)?
   • Seems obvious, but deletion changes the string, so maybe deleting 0s might set up a good move for us in the future.

There’s one last piece of the strategy to prove.

4. Should we always take the largest block of 1s?
   • Remember that Alice and Bob are playing perfectly, so anything you’ve proven earlier applies to both players’ moves.

Now that we have an ideal strategy, let’s plan how to calculate the resulting scores.

5. How would you identify the scoring moves that will be played?
   • These are the blocks of consecutive 1s in the string.
   • What is the time complexity of your algorithm?
     • Try to make only one pass of the string.
6. Implement this idea in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which reads a single string and prints the block lengths to the stderr output stream, space-separated and in order from left to right.
   • Run your tests and debug if necessary.
7. How would you calculate the players’ scores?
   • You’ll need to determine which scoring moves are played by Alice, and which are played by Bob.
   • What is the time complexity of your algorithm?
   • Check the output format from the problem: what quantity were we asked to report, and with what (if any) formatting?
8. Implement this idea in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Extend your earlier program to print the required output to stdout.
   • Run your tests and debug if necessary.
9. The original problem has several test cases per file.
   • Can we solve each test case one-by-one as above?
     • Estimate the number of operations and therefore the running time of such a program.
10. Implement this idea in code.
    • Reflector:
      • What potential pitfalls can you think of?
      • Write some tests to check for these pitfalls.
    • Other group members:
      • Extend your earlier program to print the required output to stdout.
    • Run your tests and debug if necessary.
11. Submit your program for judging! - Debug as required.