Freedom of Choice (Codeforces 1894E)
Tags: Greedy, data structures

Let's define the anti-beauty of a multiset $$$\{b_1, b_2, \ldots, b_{len}\}$$$ as the number of occurrences of the number $$$len$$$ in the multiset.You are given $$$m$$$ multisets, where the $$$i$$$-th multiset contains $$$n_i$$$ distinct elements, specifically: $$$c_{i, 1}$$$ copies of the number $$$a_{i,1}$$$, $$$c_{i, 2}$$$ copies of the number $$$a_{i,2}, \ldots, c_{i, n_i}$$$ copies of the number $$$a_{i, n_i}$$$. It is guaranteed that $$$a_{i, 1} < a_{i, 2} < \ldots < a_{i, n_i}$$$. You are also given numbers $$$l_1, l_2, \ldots, l_m$$$ and $$$r_1, r_2, \ldots, r_m$$$ such that $$$1 \le l_i \le r_i \le c_{i, 1} + \ldots + c_{i, n_i}$$$.Let's create a multiset $$$X$$$, initially empty. Then, for each $$$i$$$ from $$$1$$$ to $$$m$$$, you must perform the following action exactly once: Choose some $$$v_i$$$ such that $$$l_i \le v_i \le r_i$$$ Choose any $$$v_i$$$ numbers from the $$$i$$$-th multiset and add them to the multiset $$$X$$$.You need to choose $$$v_1, \ldots, v_m$$$ and the added numbers in such a way that the resulting multiset $$$X$$$ has the minimum possible anti-beauty.

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 the test cases follows.The first line of each test case contains a single integer $$$m$$$ ($$$1 \le m \le 10^5$$$) — the number of given multisets.Then, for each $$$i$$$ from $$$1$$$ to $$$m$$$, a data block consisting of three lines is entered.The first line of each block contains three integers $$$n_i, l_i, r_i$$$ ($$$1 \le n_i \le 10^5, 1 \le l_i \le r_i \le c_{i, 1} + \ldots + c_{i, n_i} \le 10^{17}$$$) — the number of distinct numbers in the $$$i$$$-th multiset and the limits on the number of elements to be added to $$$X$$$ from the $$$i$$$-th multiset.The second line of the block contains $$$n_i$$$ integers $$$a_{i, 1}, \ldots, a_{i, n_i}$$$ ($$$1 \le a_{i, 1} < \ldots < a_{i, n_i} \le 10^{17}$$$) — the distinct elements of the $$$i$$$-th multiset.The third line of the block contains $$$n_i$$$ integers $$$c_{i, 1}, \ldots, c_{i, n_i}$$$ ($$$1 \le c_{i, j} \le 10^{12}$$$) — the number of copies of the elements in the $$$i$$$-th multiset.It is guaranteed that the sum of the values of $$$m$$$ for all test cases does not exceed $$$10^5$$$, and also the sum of $$$n_i$$$ for all blocks of all test cases does not exceed $$$10^5$$$.

Output: For each test case, output the minimum possible anti-beauty of the multiset $$$X$$$ that you can achieve.

Note: In the first test case, the multisets have the following form: $$$\{10, 10, 10, 11, 11, 11, 12\}$$$. From this multiset, you need to select between $$$5$$$ and $$$6$$$ numbers. $$$\{12, 12, 12, 12\}$$$. From this multiset, you need to select between $$$1$$$ and $$$3$$$ numbers. $$$\{12, 13, 13, 13, 13, 13\}$$$. From this multiset, you need to select $$$4$$$ numbers.You can select the elements $$$\{10, 11, 11, 11, 12\}$$$ from the first multiset, $$$\{12\}$$$ from the second multiset, and $$$\{13, 13, 13, 13\}$$$ from the third multiset. Thus, $$$X = \{10, 11, 11, 11, 12, 12, 13, 13, 13, 13\}$$$. The size of $$$X$$$ is $$$10$$$, the number $$$10$$$ appears exactly $$$1$$$ time in $$$X$$$, so the anti-beauty of $$$X$$$ is $$$1$$$. It can be shown that it is not possible to achieve an anti-beauty less than $$$1$$$.

Sample Inputs:
7
3
3 5 6
10 11 12
3 3 1
1 1 3
12
4
2 4 4
12 13
1 5
1
7 1000 1006
1000 1001 1002 1003 1004 1005 1006
147 145 143 143 143 143 142
1
2 48 50
48 50
25 25
2
1 1 1
1
1
1 1 1
2
1
1
1 1 1
1
2
2
1 1 1
1
1
2 1 1
1 2
1 1
2
4 8 10
11 12 13 14
3 3 3 3
2 3 4
11 12
2 2

Sample Outputs:
1
139
0
1
1
0
0

Solution (Python):
TT = int(input())

def solve():
    m = int(input())
    SUL = 0
    SUR = 0
    SUN = 0
    SUC = 0
    dictx = {}
    dictsux = {}
    dict_x = {}
    for i in range(m):
        (n, l, r) = list(map(int, input().split()))
        SUL += l
        SUR += r
        SUN += n
        a = list(map(int, input().split()))
        c = list(map(int, input().split()))
        suc = sum(c)
        for (ai, ci) in zip(a, c):
            if not ai in dictx:
                dictx[ai] = 0
                dict_x[ai] = 0
                dictsux[ai] = 0
            d = suc - ci
            if d < l:
                dictx[ai] += l - d
            dict_x[ai] += max(0, r - d)
            dictsux[ai] += ci
    if SUR - SUL > SUN:
        print(0)
        return
    mi = 10000000000000000000000000000000000000000000000
    for x in range(SUL, SUR + 1):
        if not x in dictx:
            print(0)
            return
        mi = min(mi, dictx[x] + max(0, x - dictx[x] - (SUR - dict_x[x])))
    print(mi)
    return
while TT:
    solve()
    TT -= 1

Solution (Python):
TT = int(input())

def solve():
    m = int(input())
    SUL = 0
    SUR = 0
    SUN = 0
    dictx = {}
    dict_x = {}
    for i in range(m):
        (n, l, r) = list(map(int, input().split()))
        SUL += l
        SUR += r
        SUN += n
        a = list(map(int, input().split()))
        c = list(map(int, input().split()))
        suc = sum(c)
        for (ai, ci) in zip(a, c):
            if not ai in dictx:
                dictx[ai] = 0
                dict_x[ai] = 0
            d = suc - ci
            if d < l:
                dictx[ai] += l - d
            dict_x[ai] += max(0, r - d)
    if SUR - SUL > SUN:
        print(0)
        return
    mi = 10000000000000000000000000000000000000000000000
    for x in range(SUL, SUR + 1):
        if not x in dictx:
            print(0)
            return
        mi = min(mi, dictx[x] + max(0, x - dictx[x] - SUR + dict_x[x]))
    print(mi)
    return
while TT:
    solve()
    TT -= 1

Solution (Python):
t = int(input())
while t > 0:
    t -= 1
    m = int(input())
    L = R = 0
    T = dict()
    intervals = []
    total = [0 for i in range(m)]
    for i in range(m):
        (n, l, r) = map(int, input().split())
        L += l
        R += r
        intervals.append((l, r))
        uniqs = list(map(int, input().split()))
        counts = list(map(int, input().split()))
        for j in range(n):
            total[i] += counts[j]
            if T.get(uniqs[j], None) == None:
                T[uniqs[j]] = {i: counts[j]}
            else:
                T[uniqs[j]][i] = counts[j]
    a = list(T.keys())
    a.sort()
    u = len(a)
    ind = 0
    while ind < u and a[ind] < L:
        ind += 1
    if ind == u or a[ind] != L:
        print(0)
    else:
        res = R
        flag = True
        while ind < u and a[ind] <= R:
            score = 0
            elements = R
            for key in T[a[ind]]:
                if total[key] - T[a[ind]][key] < intervals[key][0]:
                    score += intervals[key][0] - total[key] + T[a[ind]][key]
                    elements += intervals[key][0] - intervals[key][1]
                else:
                    elements += min(total[key] - T[a[ind]][key], intervals[key][1]) - intervals[key][1]
            if elements < a[ind]:
                res = min(res, score + a[ind] - elements)
            else:
                res = min(res, score)
            ind += 1
            if ind == u and a[ind - 1] != R or (ind != u and a[ind - 1] != a[ind] - 1 and (a[ind - 1] != R)):
                flag = False
                break
        print(flag * res)