The Good, the Great, and the Superb
Time limit1sMemory limit512 MB
Given a sequence of digits, find the minimum number of elements to change so the sequence becomes Good, Great, or Superb, where Superb is constant, Great has adjacent gaps at most 1, and Good splits into Great or Superb blocks.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Greedy, Array, Implementation
- Solved
- No attempts yet
Problem
This problem deals with three kinds of integer sequences: Good, Great, and Superb.
A sequence is Superb if it has at least 3 elements and all elements have the same value. For example, (1, 1, 1), (4, 4, 4, 4), and (9, 9, 9, 9, 9, 9) are Superb sequences.
A sequence is Great if it has at least 3 elements and the difference between any two successive elements is at most 1. By definition, every Superb sequence is also a Great sequence. For example, (1, 2, 3, 4), (4, 4, 3, 2, 3), and (5, 5, 5) are Great sequences.
A sequence is Good if it can be built by concatenating any Great or Superb sequences. By definition, every Great or Superb sequence is also a Good sequence. For example,
- (2, 2, 3, 6, 6, 6) comes from (2, 2, 3) concatenated with (6, 6, 6).
- (5, 5, 5, 5) comes from (5, 5, 5, 5).
- (4, 3, 4, 7, 7, 8, 9, 2, 1, 0) comes from (4, 3, 4) concatenated with (7, 7, 8, 9) and (2, 1, 0).
You are given a sequence S of N integers. Find three integers a, b, and c, which are the minimum number of elements whose values you must change to turn S into a Good sequence, a Great sequence, and a Superb sequence, respectively.
Input
The first line contains an integer N (3 ≤ N ≤ 100000), the number of integers in S. The next line contains the N integers Si (0 ≤ Si ≤ 9) that make up S.
Output
Print one line with three integers a, b, and c separated by single spaces: the minimum number of elements whose values you must change to turn S into a Good sequence, a Great sequence, and a Superb sequence, respectively.