Phoenix and Socks (Codeforces 1515D)
Tags: Greedy, two pointers

To satisfy his love of matching socks, Phoenix has brought his $$$n$$$ socks ($$$n$$$ is even) to the sock store. Each of his socks has a color $$$c_i$$$ and is either a left sock or right sock. Phoenix can pay one dollar to the sock store to either:   recolor a sock to any color $$$c'$$$ $$$(1 \le c' \le n)$$$  turn a left sock into a right sock  turn a right sock into a left sock  The sock store may perform each of these changes any number of times. Note that the color of a left sock doesn't change when it turns into a right sock, and vice versa. A matching pair of socks is a left and right sock with the same color. What is the minimum cost for Phoenix to make $$$n/2$$$ matching pairs? Each sock must be included in exactly one matching pair.

Input: The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.The first line of each test case contains three integers $$$n$$$, $$$l$$$, and $$$r$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n$$$ is even; $$$0 \le l, r \le n$$$; $$$l+r=n$$$) — the total number of socks, and the number of left and right socks, respectively.The next line contains $$$n$$$ integers $$$c_i$$$ ($$$1 \le c_i \le n$$$) — the colors of the socks. The first $$$l$$$ socks are left socks, while the next $$$r$$$ socks are right socks.It is guaranteed that the sum of $$$n$$$ across all the test cases will not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print one integer — the minimum cost for Phoenix to make $$$n/2$$$ matching pairs. Each sock must be included in exactly one matching pair.

Note: In the first test case, Phoenix can pay $$$2$$$ dollars to:   recolor sock $$$1$$$ to color $$$2$$$  recolor sock $$$3$$$ to color $$$2$$$  There are now $$$3$$$ matching pairs. For example, pairs $$$(1, 4)$$$, $$$(2, 5)$$$, and $$$(3, 6)$$$ are matching.In the second test case, Phoenix can pay $$$3$$$ dollars to:   turn sock $$$6$$$ from a right sock to a left sock  recolor sock $$$3$$$ to color $$$1$$$  recolor sock $$$4$$$ to color $$$1$$$  There are now $$$3$$$ matching pairs. For example, pairs $$$(1, 3)$$$, $$$(2, 4)$$$, and $$$(5, 6)$$$ are matching.

Sample Inputs:
4
6 3 3
1 2 3 2 2 2
6 2 4
1 1 2 2 2 2
6 5 1
6 5 4 3 2 1
4 0 4
4 4 4 3

Sample Outputs:
2
3
5
3

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def map_int():
    return map(int, input().split())

def solve():
    (n, l, r) = map_int()
    c = list(map_int())
    if r > l:
        c = c[l:n] + c[:l]
        (l, r) = (r, l)
    color = [0] * (n + 1)
    for i in range(n):
        color[c[i]] += 1 if i < l else -1
    ans = rem = n // 2 - r
    bad = 0
    for cnt in color:
        if cnt > 1:
            used = min(cnt // 2, rem)
            cnt -= 2 * used
            rem -= used
        if cnt > 0:
            bad += cnt
    print(ans + bad - rem)
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def s():
    (n, l, r) = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    d = [0] * (n + 1)
    for i in range(n):
        if i < l:
            d[a[i]] -= 1
        else:
            d[a[i]] += 1
    (impl, impr, l, r, a, b) = (0, 0, 0, 0, 0, 0)
    res = 0
    for e in d:
        if e > 0:
            l += e
            a += e // 2
            impl += e % 2
        else:
            e = abs(e)
            r += e
            b += e // 2
            impr += e % 2
    if l > r:
        (l, r, a, b, impl, impr) = (r, l, b, a, impr, impl)
    res = impr
    res += max(0, l - impr) // 2 + b
    print(res)
for _ in range(int(input())):
    s()

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def s():
    (n, l, r) = [int(i) for i in input().split()]
    a = [int(i) for i in input().split()]
    d = [0] * (n + 1)
    for i in range(n):
        if i < l:
            d[a[i]] -= 1
        else:
            d[a[i]] += 1
    (l, r, res, p, le, re) = (0, 0, 0, 0, [[0], [0]], [[0], [0]])
    for e in d:
        if e > 0:
            l += e
            if e % 2:
                le[1] += [e]
            else:
                le[0] += [e]
        else:
            r += abs(e)
            if abs(e) % 2:
                re[1] += [abs(e)]
            else:
                re[0] += [abs(e)]
    if l > r:
        (l, r) = (r, l)
        (re[0], re[1]) = (le[0].copy(), le[1].copy())
    res = len(re[1]) - 1
    l = max(0, l - res)
    res += l // 2
    for i in re[1]:
        res += i // 2
    for i in re[0]:
        res += i // 2
    print(res)
for _ in range(int(input())):
    s()