ECOO '21 Practice P4 - Noisy Commute

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

Note this problem was originally intended for the cancelled 2020 Girls Invitational Competition.

Morgan likes to listen to music on her commute to school. However, her commute is very noisy, and different areas have different noise levels. In order to listen to her music properly, she must adjust the volume of her music to be at most 10 decibels higher or lower than the surrounding volume.

For the best music listening experience, she wants to be able to change the volume as little as possible, or else the volume change will be too jarring for her. She can take one shortcut at any point, cutting out one noisy area of her commute.

Input Specification

The first line of input contains an integer N (1 \le N \le 10^5), the number of areas on her commute.

The next line contains N space-separated integers, labeled v_1, v_2, \ldots, v_N, where v_i is the volume of the area at location i in decibels. It is guaranteed that 10 \le v_i \le 10^4.

Output Specification

Output the minimum total decibel change.


Subtask 1 [12%]

N \le 4

Subtask 2 [17%]

N \le 200

Subtask 3 [25%]

N \le 2000

Subtask 4 [46%]

No further constraints.

Sample Input

73 11 58 48

Sample Output



Morgan can start off with her volume at 63 decibels and take a shortcut to skip out on the second area. Then, she can keep her volume at 63 decibels for the third area, and finally change it to 58 at the fourth area. 63 dB to 63 dB to 58 dB is a total change of 5 decibels.


There are no comments at the moment.