Boredom

Source: Codeforces 455A

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

2. Solve the testcase

   
   2 3 2 1 2 3 2 1 2

   and comment on how the order of values in the sequence affects the answer.

3. Summarise the testcase above, recording only the information that could conceivably affect the answer.
   • What data structure might be useful to represent this information?
   • Is it feasible to construct and query this data structure? Check the input constraints.

Let’s generalise from the sample testcases.

4. If the sequence has several copies of the integers x − 1, x and x + 1 only, and your first move is to choose x for deletion, what total will you achieve?

5. If the sequence is unrestricted and your first move is to choose x for deletion, what will (eventually) happen to any other copies of x in the array?

6. Characterise the collection of scoring moves that can arise from any input.

One complication is that the effects of a move go “both ways”, that is, choosing x affects values both smaller and larger than x.

7. Why might this be a complication?
   • Think about dependencies. Which moves affect which other moves?

We want to process the moves in some order.

8. Propose a natural order to consider the moves.

9. As you analyse the moves in this order, what values in the sequence are relevant at each step?

10. Propose a subproblem specification which includes at least the step of this order that you are up to.
    • If you knew the answers to all subproblems, how would you retrieve the overall answer?
    • The subproblem specification needs to contain all the values relevant to the DP, “screening” off the need to look any further back. These values can be stored either in the dimensions (key) or in the body (value) of the state, depending on what direction of calculation we want to follow.
11. Propose a recurrence to relate subproblems of this form to each other.
    • Is your subproblem specification sufficient, that is, can you form a valid recurrence?
12. Analyse the time complexity of your algorithm, and estimate the running time.
    • If the algorithm is too slow, consider optimisations to reduce the number of subproblems or the work per subproblem.

13. Implement this algorithm 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 solves the problem.
      • A tip: if you loop through both indices and values, use different loop counters to distinguish between them.
    • Run your tests and debug if necessary.
14. Submit your program for judging!
    • Debug as required.

For an extension, let’s consider if one of the very convenient constraints in the question was less convenient.

15. Solve the problem with a_i up to 10¹⁸.