TWOCARD - Editorial

PROBLEM LINK:

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

Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

There are N cards, each with two values A_i and B_i. The A_i values are distinct.

Alice will choose one of the cards, and then Bob will choose whichever remaining card has the maximum A_i value.
If Alice chooses card x and Bob chooses y, Alice wins iff \max(A_x, B_x) \gt \max(A_y, B_y).

Can Alice win?

EXPLANATION:

Alice has N possible cards to choose from; we can try all of them as x, find Bob’s choice for y, and compare.

Since all the A_i values are distinct, there’s a unique maximum among them.
Let M be the index of this maximum.

If Alice doesn’t choose card M, Bob will always choose card M, because it’s the overall maximum and so certainly will be the maximum of the remaining cards.

On the other hand, if Alice does choose M, Bob can’t choose M anymore, so he will choose a different card.
Bob’s choice can be easily found in \mathcal{O}(N) time; it’ll just be whichever card has the second-largest A_i value.

So, we have a simple algorithm to check Alice’s victory:

  1. Find M, the index of the card with maximum A_i.
  2. For any x \neq M, if \max(A_x, B_x) \gt \max(A_M, B_M), Alice can win by choosing card x.
  3. Let M_2 be the index of the second maximum A_i.
    If \max(A_M, B_M) \gt \max(A_{M_2}, B_{M_2}), Alice wins by choosing card M.
  4. If both above checks fail, Alice cannot win.

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()))

    mx = 0
    for i in range(n):
        if a[i] > a[mx]: mx = i
    
    ans = 'No'
    for i in range(n):
        if i == mx: continue

        # take this -> bob will definitely take mx
        if max(a[i], b[i]) > max(a[mx], b[mx]): ans = 'Yes'
    
    # take mx -> bob will take second max
    mx2 = -1
    for i in range(n):
        if i == mx: continue
        if mx2 == -1 or a[i] > a[mx2]: mx2 = i
    if max(a[mx], b[mx]) > max(a[mx2], b[mx2]): ans = 'Yes'
    
    print(ans)

just check your code first … its not running properly

2 Likes

because this is the code of red-blue sort problem

Oops, I’d attached code of the wrong problem. Thanking for reporting, it’s updated now.