Letter Exchange (Codeforces 1785B)
Tags: Greedy, graphs

A cooperative game is played by $$$m$$$ people. In the game, there are $$$3m$$$ sheets of paper: $$$m$$$ sheets with letter 'w', $$$m$$$ sheets with letter 'i', and $$$m$$$ sheets with letter 'n'.Initially, each person is given three sheets (possibly with equal letters).The goal of the game is to allow each of the $$$m$$$ people to spell the word "win" using their sheets of paper. In other words, everyone should have one sheet with letter 'w', one sheet with letter 'i', and one sheet with letter 'n'.To achieve the goal, people can make exchanges. Two people participate in each exchange. Both of them choose exactly one sheet of paper from the three sheets they own and exchange it with each other.Find the shortest sequence of exchanges after which everyone has one 'w', one 'i', and one 'n'.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$m$$$ ($$$2 \le m \le 10^5$$$) — the number of people.The $$$i$$$-th of the next $$$m$$$ lines contains a string $$$s_i$$$ of length $$$3$$$ consisting of lowercase English letters 'w', 'i', and 'n', denoting the letters person $$$i$$$ has on their sheets of paper at the beginning of the game, in arbitrary order.Each of the letters 'w', 'i', and 'n' appears on the sheets of paper exactly $$$m$$$ times in total.It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print a non-negative integer $$$k$$$ — the smallest number of exchanges people need to make everyone have one 'w', one 'i', and one 'n'.In each of the next $$$k$$$ lines print four tokens $$$a_1$$$ $$$c_1$$$ $$$a_2$$$ $$$c_2$$$, describing the exchanges in chronological order ($$$1 \le a_1, a_2 \le m$$$; $$$a_1 \ne a_2$$$; $$$c_1, c_2$$$ are one of $$$\{\mathtt{w}, \mathtt{i}, \mathtt{n}\}$$$): person $$$a_1$$$ gives letter $$$c_1$$$ to person $$$a_2$$$, while person $$$a_2$$$ gives letter $$$c_2$$$ to person $$$a_1$$$ at the same time.If there are multiple solutions, print any.


Sample Inputs:
3
2
nwi
inw
3
inn
nww
wii
4
win
www
iii
nnn

Sample Outputs:
0
2
2 w 3 i
3 w 1 n
3
2 w 3 i
2 w 4 n
3 i 4 n

Solution (Python):
def II():
    return int(input())

def LI():
    return list(map(int, input().split()))

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

def exo1():

    def solve():
        n = II()
        l = LI()
        tab = [0] * (n + 1)
        maxi = 0
        for x in l:
            tab[x] += 1
            maxi = max(maxi, x)
        level = 0
        res = 0
        for i in range(1, maxi + 1):
            while level and tab[i]:
                res += level
                level -= 1
                tab[i] -= 1
            if not tab[i]:
                level += 1
        print(res)
    for _ in range(II()):
        solve()
inp = '2\n3\n3 1 2\n6\n4 1 5 4 1 1'

def exo2():

    def solve():

        def num(c):
            if c == 'i':
                return 0
            if c == 'n':
                return 1
            if c == 'w':
                return 2
        n = II()
        s = [input() for _ in range(n)]
        d = [[[] for _ in range(3)] for _ in range(3)]
        for (i, val) in enumerate(s, start=1):
            (a, b, c) = [num(x) for x in val]
            if a == b:
                if a == c:
                    d[a][(5 - a) // 2].append(i)
                    d[a][(2 - a) // 2].append(i)
                else:
                    d[a][3 - a - c].append(i)
            elif a == c or b == c:
                d[c][3 - a - b].append(i)
        x = min(len(d[0][1]), len(d[1][0])) + min(len(d[0][2]), len(d[2][0])) + min(len(d[2][1]), len(d[1][2]))
        ans = sum([sum([len(x) for x in y]) for y in d])
        print((ans - 2 * x) * 2 // 3 + x)
        let = ['i', 'n', 'w']
        while d[0][1] and d[1][0]:
            x = d[0][1].pop()
            y = d[1][0].pop()
            print(x, 'i', y, 'n')
        while d[2][1] and d[1][2]:
            x = d[2][1].pop()
            y = d[1][2].pop()
            print(x, 'w', y, 'n')
        while d[0][2] and d[2][0]:
            x = d[0][2].pop()
            y = d[2][0].pop()
            print(x, 'i', y, 'w')
        while d[0][1]:
            x = d[0][1].pop()
            y = d[1][2].pop()
            z = d[2][0].pop()
            print(x, 'i', y, 'n')
            print(y, 'i', z, 'w')
        while d[1][0]:
            x = d[1][0].pop()
            y = d[0][2].pop()
            z = d[2][1].pop()
            print(x, 'n', y, 'i')
            print(y, 'n', z, 'w')
    for _ in range(II()):
        solve()
inp = '3\n2\nnwi\ninw\n3\ninn\nnww\nwii\n4\nwin\nwww\niii\nnnn'
inp = '6\n14\nwin\nwii\niin\nwii\nnwn\nwnn\nwin\niww\nnni\nwwi\niwn\nini\nnwn\nnww\n7\nnwi\nini\nwwi\nnww\ninw\nwnn\niin\n7\niwn\nwwi\nwin\nnni\nnwi\nwin\ninw\n2\niwn\niwn\n2\niww\nnin\n5\nini\nniw\nnwi\nwwn\niwn\n'
exo2()

def exo2():

    def solve():
        pass
    for _ in range(II()):
        solve()
inp = ''

def exo2():

    def solve():
        pass
    for _ in range(II()):
        solve()
inp = ''

def exo2():

    def solve():
        pass
    for _ in range(II()):
        solve()
inp = ''

def input():
    global inp
    if isinstance(inp, str):
        inp = list(reversed(inp.split('\n')))
    return inp.pop()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().strip()
from collections import Counter
t = int(input())
for _ in range(t):
    n = int(input())
    stuff = [[[] for i in range(4)] for i in range(4)]
    win = 'win'
    for k in range(n):
        s = input()
        a = 0
        b = 0
        c = 0
        for p in s:
            if p == 'w':
                a += 1
            if p == 'i':
                b += 1
            if p == 'n':
                c += 1
        sus = [a, b, c]
        maxi = sus.index(max(sus))
        buffer = []
        for i in range(3):
            if sus[i] == 0:
                stuff[i][maxi].append(k + 1)
    for i in range(3):
        for j in range(3):
            if i > j:
                continue
            while stuff[i][j] and stuff[j][i]:
                buffer.append([stuff[i][j].pop(), win[j], stuff[j][i].pop(), win[i]])
    if stuff[0][1]:
        for i in range(len(stuff[0][1])):
            buffer.append([stuff[0][1][i], win[1], stuff[2][0][i], win[0]])
        for i in range(len(stuff[1][2])):
            buffer.append([stuff[1][2][i], win[2], stuff[2][0][i], win[1]])
    elif stuff[0][2]:
        for i in range(len(stuff[0][2])):
            buffer.append([stuff[0][2][i], win[2], stuff[1][0][i], win[0]])
        for i in range(len(stuff[2][1])):
            buffer.append([stuff[2][1][i], win[1], stuff[1][0][i], win[2]])
    print(len(buffer))
    for i in buffer:
        print(*i)

Solution (Python):
import queue
for _ in range(int(input())):
    iw = queue.Queue()
    nw = queue.Queue()
    wi = queue.Queue()
    in_ = queue.Queue()
    wn = queue.Queue()
    ni = queue.Queue()
    zap = []
    for num in range(int(input())):
        s = list(input())
        w = s.count('w')
        i = s.count('i')
        n = s.count('n')
        if w > 1 and i < 1:
            wi.put_nowait(num)
        if w > 1 and n < 1:
            wn.put_nowait(num)
        if n > 1 and i < 1:
            ni.put_nowait(num)
        if n > 1 and w < 1:
            nw.put_nowait(num)
        if i > 1 and n < 1:
            in_.put_nowait(num)
        if i > 1 and w < 1:
            iw.put_nowait(num)
    for r in range(min(wi.qsize(), iw.qsize())):
        zap.append(f'{wi.get_nowait() + 1} w {iw.get_nowait() + 1} i')
    for r in range(min(wn.qsize(), nw.qsize())):
        zap.append(f'{wn.get_nowait() + 1} w {nw.get_nowait() + 1} n')
    for r in range(min(in_.qsize(), ni.qsize())):
        zap.append(f'{in_.get_nowait() + 1} i {ni.get_nowait() + 1} n')
    while in_.qsize() > 0 and nw.qsize() > 0 and (wi.qsize() > 0):
        n1 = nw.get_nowait() + 1
        w1 = wi.get_nowait() + 1
        i1 = in_.get_nowait() + 1
        zap.append(f'{n1} n {w1} w')
        zap.append(f'{w1} n {i1} i')
    while ni.qsize() > 0 and iw.qsize() > 0 and (wn.qsize() > 0):
        n1 = ni.get_nowait() + 1
        w1 = wn.get_nowait() + 1
        i1 = iw.get_nowait() + 1
        zap.append(f'{n1} n {w1} w')
        zap.append(f'{n1} w {i1} i')
    print(len(zap))
    for e in zap:
        print(e)