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:
- Find M, the index of the card with maximum A_i.
- For any x \neq M, if \max(A_x, B_x) \gt \max(A_M, B_M), Alice can win by choosing card x.
- 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. - 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)