MINMAXMEX - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You have two arrays A and B.
You’re allowed to swap A_i and B_i for an index i, however many times you like.

Find the minimum possible value of \max(\text{MEX}(A), \text{MEX}(B)).

EXPLANATION:

Since the MEX of an array is the smallest non-negative integer not belonging it, it’s helpful to think about which elements can be made to belong to which arrays.

If A_i = B_i for some index, swapping at this index is useless - and both A and B will always contain the element A_i.

If A_i \neq B_i for some index, we can decide which array gets the element A_i and which gets the element B_i.

With this in mind, let’s define two 0-indexed arrays \text{one} and \text{two}, such that:

  • If there exists an index i such that A_i = B_i = x, then \text{two}[x] = 1.
    Otherwise, \text{two}[x] = 0.
  • If there exists an index i such that A_i \neq B_i and either A_i = x or B_i = x, then \text{one}[x] = 1.
    Otherwise, \text{one}[x] = 0.

Building these two arrays can be done easily in linear time, just by iterating through the arrays A and B.

Once we have the arrays \text{one} and \text{two}, let’s iterate through possible values of the answer, from 0 upward.
Suppose we’re currently processing x. Then,

  • If \text{two}[x] = 1, then A and B will both always contain x.
    Nothing can be done here, so we increment x and carry on.
  • If \text{two}[x] = 0 and \text{one}[x] = 0, it means x doesn’t appear at all among the two arrays.
    If we reach this point, the answer is x.
  • If \text{two}[x] = 0 and \text{one}[x] = 1, it means we can choose which array receives the value x, by just giving all occurrences of the value x to one of the arrays so that the other array doesn’t have any.
    The first time this happens, one of the arrays will have its MEX fixed to x while the other array will continue on. Suppose we fix \text{MEX}(A) = x by giving all occurrences of x to B.
    The second time this happens, we can give all the values of x to A instead, which will fix \text{MEX}(B) = x as well; so that this x becomes the answer.

So, quite simply, the answer is either:

  • The smallest x for which \text{one}[x] = \text{two}[x] = 0, or
  • The second smallest x for which \text{one}[x] = 1 and \text{two}[x] = 0.
    Of course, take whichever is smaller between these two cases.

Since 0 \leq A_i, B_i \lt N, the answer cannot exceed N - so this runs in linear time overall.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    one, two = [0]*(n+1), [0]*(n+1)
    for i in range(n):
        if a[i] == b[i]: two[a[i]] = 1
        else:
            one[a[i]] = 1
            one[b[i]] = 1
    
    ct = 0
    for i in range(n+1):
        if one[i] == 0 and two[i] == 0:
            print(i)
            break
        elif two[i] == 0:
            if ct == 0: ct = 1
            else:
                print(i)
                break
3 Likes
3

Nice problem

4

in constraints it is mentioned that:

0≤Ai,Bi<N

but my code failed just because of the reason that i didn’t created the ‘two’ and ‘one’ arrays (specified in the question) of size n+1, since it is written that the value of elements will never be n, i can create the arrays to be of size n, and run the loop till n-1 only, but that code is failing.

please tell if i am missing something else or any other error in the code.

submission with array size n+1:
https://www.codechef.com/viewsolution/1180778733

submission with array size n:
https://www.codechef.com/viewsolution/1180780049

5

for this example A = [0,1,2,3], B = [0,1,2,3] you need to loop untill n rather than n-1.

1 Like