Mr. Perfectly Fine (Codeforces 1829C)
Tags: Greedy, bitmasks

Victor wants to become "Mr. Perfectly Fine". For that, he needs to acquire a certain set of skills. More precisely, he has $$$2$$$ skills he needs to acquire. Victor has $$$n$$$ books. Reading book $$$i$$$ takes him $$$m_i$$$ minutes and will give him some (possibly none) of the required two skills, represented by a binary string of length $$$2$$$.What is the minimum amount of time required so that Victor acquires all of the two skills? 

Input: The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of books available.Then $$$n$$$ lines follow. Line $$$i$$$ contains a positive integer $$$m_i$$$ ($$$1 \leq m_i \leq 2 \cdot 10^5$$$) and a binary string of length $$$2$$$, where $$$s_{i1} = 1$$$ if reading book $$$i$$$ acquires Victor skill $$$1$$$, and $$$s_{i1} = 0$$$ otherwise, and $$$s_{i2} = 1$$$ if reading book $$$i$$$ acquires Victor skill $$$2$$$, and $$$s_{i2} = 0$$$ otherwise.It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer denoting the minimum amount of minutes required for Victor to obtain both needed skills and $$$-1$$$ in case it's impossible to obtain the two skills after reading any amount of books. 

Note: In the first test case, we can use books $$$2$$$ and $$$3$$$, with a total amount of minutes spent equal to $$$3 + 4 = 7$$$.In the second test case, we can use the books $$$1$$$ and $$$4$$$, with a total amount of minutes spent equal to $$$3 + 2 = 5$$$.In the third test case, we have only one option and that is reading book $$$1$$$ for a total amount of minutes spent equal to $$$5$$$.

Sample Inputs:
6
4
2 00
3 10
4 01
4 00
5
3 01
3 01
5 01
2 10
9 10
1
5 11
3
9 11
8 01
7 10
6
4 01
6 01
7 01
8 00
9 01
1 00
4
8 00
9 10
9 11
8 11

Sample Outputs:
7
5
5
9
-1
8

Solution (Python):
import sys
input = sys.stdin.readline
from math import *
mod = 1000000007

def solve():
    n = int(input())
    mini1 = 200001
    mini2 = 200001
    minib = 200001
    for i in range(n):
        (bi, xi) = input().split()
        mi = int(bi)
        if xi == '10':
            if mini1 > mi:
                mini1 = mi
        elif xi == '01':
            if mini2 > mi:
                mini2 = mi
        elif xi == '11':
            if minib > mi:
                minib = mi
    if minib == 200001:
        if mini1 == 200001 or mini2 == 200001:
            print(-1)
        else:
            print(mini1 + mini2)
    elif mini1 == 200001 or mini2 == 200001:
        print(minib)
    else:
        print(min(mini1 + mini2, minib))
for _ in range(int(input())):
    solve()

Solution (Python):
import math, os, sys
from collections import defaultdict
if os.path.exists('input.txt'):
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
import sys
input = sys.stdin.readline

def task():
    n = int(input())
    lst = [99999999, 99999999, 99999999]
    for _ in range(n):
        (a, b) = input().split()
        if b == '10' and int(a) < lst[0]:
            lst[0] = int(a)
        elif b == '01' and int(a) < lst[1]:
            lst[1] = int(a)
        elif b == '11' and int(a) < lst[2]:
            lst[2] = int(a)
    if lst[0] == lst[2] == 99999999 or lst[1] == lst[2] == 99999999:
        print(-1)
    elif lst[0] + lst[1] < lst[2]:
        print(lst[0] + lst[1])
    else:
        print(lst[2])
f = 1
if f == 1:
    for _ in range(int(input())):
        task()
else:
    task()
sys.stdout.close()
sys.stdin.close()

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    d = {'00': 0, '01': float('inf'), '10': float('inf'), '11': float('inf')}
    for x in range(n):
        (m, s) = input().rstrip('\n').split()
        m = int(m)
        if d[s] > m:
            d[s] = m
    ans = min(d['10'] + d['01'], d['11'])
    ans = -1 if ans == float('inf') else ans
    print(ans)