LuoTianyi and the Show (Codeforces 1824A)
Tags: Greedy, implementation

There are $$$n$$$ people taking part in a show about VOCALOID. They will sit in the row of seats, numbered $$$1$$$ to $$$m$$$ from left to right.The $$$n$$$ people come and sit in order. Each person occupies a seat in one of three ways:  Sit in the seat next to the left of the leftmost person who is already sitting, or if seat $$$1$$$ is taken, then leave the show. If there is no one currently sitting, sit in seat $$$m$$$. Sit in the seat next to the right of the rightmost person who is already sitting, or if seat $$$m$$$ is taken, then leave the show. If there is no one currently sitting, sit in seat $$$1$$$. Sit in the seat numbered $$$x_i$$$. If this seat is taken, then leave the show. Now you want to know what is the maximum number of people that can take a seat, if you can let people into the show in any order?

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — the number of people and the number of seats.The second line of each test case contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$-2 \le x_i \le m$$$, $$$x_i \ne 0$$$), the $$$i$$$-th of which describes the way in which the $$$i$$$-th person occupies a seat: If $$$x_i=-1$$$, then $$$i$$$-th person takes the seat in the first way. If $$$x_i=-2$$$, then $$$i$$$-th person takes the seat in the second way. If $$$x_i > 0$$$, then the $$$i$$$-th person takes a seat in the third way, i.e. he wants to sit in the seat with the number $$$x_i$$$ or leave the show if it is occupied.. It is guaranteed that sum of $$$n$$$ and the sum of $$$m$$$ over all test cases don't exceed $$$10^5$$$.

Output: For each test case output a single integer — the maximum number of people who can occupy a seat.

Note: In the first test case, all the people want to occupy the $$$5$$$ seat, so only $$$1$$$ people can occupy the seat.In the second test case, we can let people in order $$$1, 2, 3, 4$$$, then all but the last person can take a seat.In the third test case, we can let people into the show in that order:Let the third person in:–––3––– Let the fourth person in:–––34–– Let the fifth person in:–––345– Let the first person in:––1345– Let the second person in:–21345–Thus, all $$$5$$$ people took seats.In the fifth test case, we can let people into the show in this order:Let the fourth person in:––––4– Let the third person in:–––34– Let the sixth person in, he'll leave the show because he takes the third seat the third way and has to sit in the $$$4$$$ seat, but it's already taken:–––34–Let the fifth person in:––534–Let the first person in:–1534–Let the second person in:21534–Thus, $$$5$$$ of people took seats.In the seventh test case, we can let people into the show in this order:Let the third person in:3––––––Let the fourth person in:34––––– Let the fifth person in:345–––– Let the sixth person in:3456––– Let the first person in:34561––Let the second person in, he will leave the show because he occupies the first way, but the $$$1$$$ seat is taken:34561––Thus, $$$5$$$ people took seats.

Sample Inputs:
10
3 10
5 5 5
4 6
1 -2 -2 1
5 7
-1 -1 4 -2 -2
6 7
5 -2 -2 -2 -2 -2
6 6
-1 1 4 5 -1 4
6 8
-1 -1 -1 3 -1 -2
6 7
5 -1 -2 -2 -2 -2
3 1
-2 -2 1
2 5
5 -2
1 2
-1

Sample Outputs:
1
3
5
6
5
5
5
1
2
1

Solution (Python):
def calculate_min_rooms():
    t = int(input())
    results = []
    for _ in range(t):
        (n, m) = map(int, input().split())
        a = list(map(int, input().split()))
        c1 = a.count(-1)
        c2 = a.count(-2)
        a = sorted(set((i for i in a if i > 0)))
        ans = max(c1, c2) + len(a)
        l = 0
        r = len(a)
        for i in a:
            r -= 1
            ans = max(ans, 1 + min(i - 1, c1 + l) + min(m - i, c2 + r))
            l += 1
        results.append(min(ans, m))
    return results
if __name__ == '__main__':
    results = calculate_min_rooms()
    for result in results:
        print(result)

Solution (Python):
def solve(n, m, arr):
    count_1 = 0
    count_2 = 0
    ls = set()
    for num in arr:
        if num == -1:
            count_1 += 1
        elif num == -2:
            count_2 += 1
        elif num <= m:
            ls.add(num)
    ls = list(ls)
    ls.sort()
    maxi = 0
    for (i, num) in enumerate(ls):
        temp = len(ls)
        left = i + 1
        right = len(ls) - i - 1
        if count_1 > num - left:
            temp += num - left
        else:
            temp += count_1
        if m - right - num > count_2:
            temp += count_2
        else:
            temp += m - right - num
        if temp > maxi:
            maxi = temp
    temp = min(m, count_1 + len(ls))
    if temp > maxi:
        maxi = temp
    temp = min(m, count_2 + len(ls))
    if temp > maxi:
        maxi = temp
    print(maxi)
for t in range(int(input())):
    (n, m) = map(int, input().split())
    arr = list(map(int, input().split()))
    solve(n, m, arr)

Solution (Python):
def show(m, n, arr):
    num_left = 0
    num_right = 0
    unique_sits = set()
    prefix = []
    res = 0
    for i in arr:
        if i == -1:
            num_left += 1
        elif i == -2:
            num_right += 1
        else:
            unique_sits.add(i)
    unique_sits = sorted(list(unique_sits))
    cur_num = 0
    p1 = 0
    for i in range(m):
        prefix.append(cur_num)
        if p1 < len(unique_sits) and i + 1 == unique_sits[p1]:
            cur_num += 1
            p1 += 1
    prefix.append(cur_num)
    for num in unique_sits:
        if num > m:
            break
        cur_res = min(num - 1, num_left + prefix[num - 1]) + min(m - num, num_right + (prefix[-1] - prefix[num])) + 1
        res = max(cur_res, res)
    return min(max(res, min(n, max(num_left, num_right) + prefix[-1])), m, n)
testcases = range(int(input()))
for case in testcases:
    (n, m) = [int(i) for i in input().split(' ')]
    arr = [int(i) for i in input().split(' ')]
    print(show(m, n, arr))