Secret Santa (Codeforces 1530D)
Tags: Math, flows

Every December, VK traditionally holds an event for its employees named "Secret Santa". Here's how it happens.$$$n$$$ employees numbered from $$$1$$$ to $$$n$$$ take part in the event. Each employee $$$i$$$ is assigned a different employee $$$b_i$$$, to which employee $$$i$$$ has to make a new year gift. Each employee is assigned to exactly one other employee, and nobody is assigned to themselves (but two employees may be assigned to each other). Formally, all $$$b_i$$$ must be distinct integers between $$$1$$$ and $$$n$$$, and for any $$$i$$$, $$$b_i \ne i$$$ must hold.The assignment is usually generated randomly. This year, as an experiment, all event participants have been asked who they wish to make a gift to. Each employee $$$i$$$ has said that they wish to make a gift to employee $$$a_i$$$.Find a valid assignment $$$b$$$ that maximizes the number of fulfilled wishes of the employees.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.Each test case consists of two lines. The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of participants of the event.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$; $$$a_i \ne i$$$) — wishes of the employees in order from $$$1$$$ to $$$n$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print two lines.In the first line, print a single integer $$$k$$$ ($$$0 \le k \le n$$$) — the number of fulfilled wishes in your assignment.In the second line, print $$$n$$$ distinct integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$; $$$b_i \ne i$$$) — the numbers of employees assigned to employees $$$1, 2, \ldots, n$$$.$$$k$$$ must be equal to the number of values of $$$i$$$ such that $$$a_i = b_i$$$, and must be as large as possible. If there are multiple answers, print any.

Note: In the first test case, two valid assignments exist: $$$[3, 1, 2]$$$ and $$$[2, 3, 1]$$$. The former assignment fulfills two wishes, while the latter assignment fulfills only one. Therefore, $$$k = 2$$$, and the only correct answer is $$$[3, 1, 2]$$$.

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

Sample Outputs:
2
3 1 2
4
6 4 7 2 3 5 1

Solution (Python):
import collections
import itertools
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def li():
    return [int(i) for i in input().split()]

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()

def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1

def binary_search(n, a):
    l = len(a)
    low = 0
    high = l - 1
    while high >= low:
        mid = (high + low) // 2
        if a[mid] == n:
            return mid
        elif a[mid] > n:
            high = mid - 1
        else:
            low = mid + 1
    return -1
mod = 10 ** 9 + 7

def solve():
    n = II()
    a = LI()
    filled = [0] * (n + 1)
    ans = [0] * n
    for i in range(n):
        filled[a[i]] += 1
    left = []
    for i in range(1, n + 1):
        if filled[i] == 0:
            left.append(i)
    j = 0
    for i in range(n):
        if filled[a[i]] == 1:
            ans[i] = a[i]
        elif left[j] != i + 1:
            ans[i] = left[j]
            filled[a[i]] -= 1
            j += 1
        elif j + 1 < len(left):
            (left[j], left[j + 1]) = (left[j + 1], left[j])
            ans[i] = left[j]
            filled[a[i]] -= 1
            j += 1
        else:
            ans[i] = a[i]
    print(n - len(left))
    return ' '.join(map(str, ans))

def main():
    for _ in range(II()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
from collections import *
from sys import stdin
inputFunc = stdin.readline

def rearrange_array(a):
    remaining_nums = set(range(1, len(a) + 1))
    group_by_num = {}
    for i in range(len(a)):
        if a[i] in remaining_nums:
            remaining_nums.remove(a[i])
        if a[i] not in group_by_num:
            group_by_num[a[i]] = [i]
        else:
            group_by_num[a[i]].append(i)
    result = [0] * len(a)
    remaining_list = list(remaining_nums)
    j = 0
    for num in group_by_num:
        result[group_by_num[num][0]] = num
        for ind in range(1, len(group_by_num[num])):
            id = group_by_num[num][ind]
            result[id] = remaining_list[j]
            j += 1
            if result[id] == id + 1:
                (result[id], result[group_by_num[num][ind - 1]]) = (result[group_by_num[num][ind - 1]], result[id])
    cnt = 0
    for i in range(len(result)):
        if a[i] == result[i]:
            cnt += 1
    print(cnt)
    return result
for i in range(int(inputFunc())):
    n = inputFunc()
    a = list(map(int, inputFunc().strip().split()))
    print(*rearrange_array(a))

Solution (Python):
from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import copy
inf_var = 0
if inf_var == 1:
    inf = open('input.txt', 'r')
else:
    inf = sys.stdin
input = inf.readline

def read_one_int():
    return int(input().rstrip('\n'))

def read_one_float():
    return float(input().rstrip('\n'))

def read_list_of_ints():
    res = [int(val) for val in input().rstrip('\n').split()]
    return res

def read_list_of_ints_zero():
    return [int(val) - 1 for val in input().rstrip('\n').split()]

def read_str():
    return input().rstrip()

def assign(n, wishes):
    used = [0] * n
    res = 0
    res_assignment = [-1] * n
    for (i, w) in enumerate(wishes):
        if not used[w]:
            res_assignment[i] = w
            used[w] = 1
            res += 1
    free = deque()
    for i in range(n):
        if not used[i]:
            free.append(i)
    left = None
    for i in range(n):
        if res_assignment[i] == -1:
            trial = free.pop()
            if trial != i:
                res_assignment[i] = trial
            else:
                free.append(trial)
                trial = free.popleft()
                if trial != i:
                    res_assignment[i] = trial
                else:
                    left = trial
                    break
    if left is not None:
        cost = 2
        change = None
        for i in range(n):
            if i == left:
                continue
            cur_change = [i, res_assignment[i]]
            if wishes[i] == cur_change[1]:
                cur_cost = 1
                if wishes[left] == cur_change[1]:
                    cur_cost = 0
            else:
                cur_cost = 0
            if cur_cost < cost:
                cost = cur_cost
                change = cur_change
        if cost:
            res -= cost
        res_assignment[left] = change[1]
        res_assignment[change[0]] = left
    for i in range(n):
        res_assignment[i] += 1
    print(res)
    print(' '.join(map(str, res_assignment)))

def main():
    tests = read_one_int()
    for _ in range(tests):
        n = read_one_int()
        wishes = read_list_of_ints_zero()
        assign(n, wishes)
if __name__ == '__main__':
    main()