Lose it! (Codeforces 1176C)
Tags: Greedy, dp

You are given an array $$$a$$$ consisting of $$$n$$$ integers. Each $$$a_i$$$ is one of the six following numbers: $$$4, 8, 15, 16, 23, 42$$$.Your task is to remove the minimum number of elements to make this array good.An array of length $$$k$$$ is called good if $$$k$$$ is divisible by $$$6$$$ and it is possible to split it into $$$\frac{k}{6}$$$ subsequences $$$4, 8, 15, 16, 23, 42$$$.Examples of good arrays:  $$$[4, 8, 15, 16, 23, 42]$$$ (the whole array is a required sequence);  $$$[4, 8, 4, 15, 16, 8, 23, 15, 16, 42, 23, 42]$$$ (the first sequence is formed from first, second, fourth, fifth, seventh and tenth elements and the second one is formed from remaining elements);  $$$[]$$$ (the empty array is good). Examples of bad arrays:   $$$[4, 8, 15, 16, 42, 23]$$$ (the order of elements should be exactly $$$4, 8, 15, 16, 23, 42$$$);  $$$[4, 8, 15, 16, 23, 42, 4]$$$ (the length of the array is not divisible by $$$6$$$);  $$$[4, 8, 15, 16, 23, 42, 4, 8, 15, 16, 23, 23]$$$ (the first sequence can be formed from first six elements but the remaining array cannot form the required sequence). 

Input: The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of elements in $$$a$$$.The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ (each $$$a_i$$$ is one of the following numbers: $$$4, 8, 15, 16, 23, 42$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

Output: Print one integer — the minimum number of elements you have to remove to obtain a good array.


Sample Inputs:
5
4 8 15 16 23

12
4 8 4 15 16 8 23 15 16 42 23 42

15
4 8 4 8 15 16 8 16 23 15 16 4 42 23 42

Sample Outputs:
5

0

3

Solution (Python):
n = int(input())
ar = list(map(int, input().split()))
lst = {4: 4, 8: 4, 15: 8, 16: 15, 23: 16, 42: 23}
dc = {4: 0, 8: 0, 15: 0, 16: 0, 23: 0, 42: 0}
for x in ar:
    if dc[lst[x]] > dc[x] or x == 4:
        dc[x] += 1
print(n - dc[42] * 6)

Solution (Python):
n = int(input())
a = map(int, input().split(' '))
num = [0 for x in range(43)]
for x in a:
    if x == 4:
        num[4] += 1
    elif x == 8 and num[4] > 0:
        num[4] -= 1
        num[8] += 1
    elif x == 15 and num[8] > 0:
        num[8] -= 1
        num[15] += 1
    elif x == 16 and num[15] > 0:
        num[15] -= 1
        num[16] += 1
    elif x == 23 and num[16] > 0:
        num[16] -= 1
        num[23] += 1
    elif x == 42 and num[23] > 0:
        num[23] -= 1
        num[42] += 1
print(n - num[42] * 6)

Solution (Python):
n = int(input())
a = map(int, input().split(' '))
num = [0, 0, 0, 0, 0, 0]
for x in a:
    if x == 4:
        num[0] += 1
    elif x == 8 and num[0] > 0:
        num[0] -= 1
        num[1] += 1
    elif x == 15 and num[1] > 0:
        num[1] -= 1
        num[2] += 1
    elif x == 16 and num[2] > 0:
        num[2] -= 1
        num[3] += 1
    elif x == 23 and num[3] > 0:
        num[3] -= 1
        num[4] += 1
    elif x == 42 and num[4] > 0:
        num[4] -= 1
        num[5] += 1
print(n - num[5] * 6)