Two Out of Three (Codeforces 1894B)
Tags: Others, constructive algorithms

You are given an array $$$a_1, a_2, \ldots, a_n$$$. You need to find an array $$$b_1, b_2, \ldots, b_n$$$ consisting of numbers $$$1$$$, $$$2$$$, $$$3$$$ such that exactly two out of the following three conditions are satisfied: There exist indices $$$1 \leq i, j \leq n$$$ such that $$$a_i = a_j$$$, $$$b_i = 1$$$, $$$b_j = 2$$$. There exist indices $$$1 \leq i, j \leq n$$$ such that $$$a_i = a_j$$$, $$$b_i = 1$$$, $$$b_j = 3$$$. There exist indices $$$1 \leq i, j \leq n$$$ such that $$$a_i = a_j$$$, $$$b_i = 2$$$, $$$b_j = 3$$$.If such an array does not exist, you should report it.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 500)$$$ — the number of test cases. Each test case is described as follows.The first line of each test case contains an integer $$$n$$$ $$$(1 \leq n \leq 100)$$$ — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 100)$$$ — the elements of the array $$$a$$$.

Output: For each test case, print -1 if there is no solution. Otherwise, print $$$b_1, b_2, \ldots, b_n$$$ — an array consisting of numbers $$$1$$$, $$$2$$$, $$$3$$$ that satisfies exactly two out of three conditions. If there are multiple possible answers, you can print any of them.

Note: In the first test case, $$$b = [1, 2, 3, 1, 1, 1]$$$ satisfies condition $$$1$$$ because for $$$i = 4$$$, $$$j = 2$$$: $$$a_i = a_j$$$, $$$b_i = 1$$$, and $$$b_j = 2$$$. It also satisfies condition $$$2$$$ because for $$$i = 6$$$, $$$j = 3$$$: $$$a_i = a_j$$$, $$$b_i = 1$$$, and $$$b_j = 3$$$. However, it does not satisfy condition $$$3$$$. In total, exactly two out of three conditions are satisfied.

Sample Inputs:
9
6
1 2 3 2 2 3
7
7 7 7 7 7 7 7
4
1 1 2 2
7
1 2 3 4 5 6 7
5
2 3 3 3 2
3
1 2 1
9
1 1 1 7 7 7 9 9 9
1
1
18
93 84 50 21 88 52 16 50 63 1 30 85 29 67 63 58 37 69

Sample Outputs:
1 2 3 1 1 1 
-1
3 2 2 1 
-1
2 1 2 1 3 
-1
1 1 2 2 1 2 2 3 3
-1
3 2 1 3 3 3 3 2 2 1 1 2 3 1 3 1 1 2

Solution (Python):
from collections import Counter, defaultdict

def invert(kv):
    ans = defaultdict(list)
    for (k, v) in kv.items():
        ans[v].append(k)
    return ans

def print_ans(nums):
    strs = list(map(str, nums))
    s = ' '.join(strs)
    print(f'{s}')
t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    ans = [1] * n
    num_to_indices = defaultdict(list)
    for (i, num) in enumerate(nums):
        num_to_indices[num].append(i)
    num_to_freq = Counter(nums)
    freq_to_nums = invert(num_to_freq)
    tracker = [0, 0, 0]
    cnt = 0
    success = False
    v = 2
    for freq in reversed(sorted(freq_to_nums)):
        nums = freq_to_nums[freq]
        for num in nums:
            if freq >= 2:
                cnt += 1
                ans[num_to_indices[num][0]] = 2 if cnt == 1 else 3
                if cnt == 2:
                    success = True
                    break
        if success:
            break
    if success:
        print_ans(ans)
    else:
        print(-1)

Solution (Python):
for t in range(int(input())):
    n = int(input())
    a = input().split()
    b = ['1'] * n
    v = {}
    c = set()
    for (i, j) in enumerate(a):
        if j in v:
            v[j].append(i)
            c.add(j)
        else:
            v[j] = [i]
        if len(c) == 2:
            break
    if len(c) == 2:
        (x, y) = c
        b[v[x][0]] = '2'
        b[v[y][0]] = '3'
        print(' '.join(b))
    else:
        print(-1)

Solution (Python):
from collections import Counter

def solution(arr):
    counter = Counter(arr)
    first_pair = False
    pair_num = None
    for (a, val) in counter.items():
        if val >= 2:
            first_pair = True
            pair_num = a
    second_pair = False
    second_pair_num = None
    for (a, val) in counter.items():
        if val >= 2 and a != pair_num:
            second_pair = True
            second_pair_num = a

    def get_arr():
        out = []
        pair_num_i = 1
        second_i = 1
        for c in arr:
            if c == pair_num:
                if pair_num_i >= 3:
                    out.append('1')
                else:
                    out.append(str(pair_num_i))
                    pair_num_i += 1
            elif c == second_pair_num:
                if second_i >= 4:
                    out.append('1')
                else:
                    out.append(str(second_i))
                    second_i += 2
            else:
                out.append('1')
        return ' '.join(out)
    if first_pair and second_pair:
        print(get_arr())
    else:
        print(-1)
import sys
for (i, line) in enumerate(sys.stdin):
    if i == 0 or i % 2 == 1:
        continue
    if i % 2 == 0:
        lst = line.strip().split(' ')
        solution(lst)