Playing the Smaller Number
InterviewTime limit1sMemory limit512 MB
Given two odd-length card sets, decide if one player can force a majority of rounds by winning when their card is strictly smaller, using a matching strategy.
- Level
Medium7 of 10
- Topics
- Sorting, Greedy, Two pointers
- Solved
- No attempts yet
Statement
Joo-eon went to a board game cafe with his girlfriend and enjoyed their date playing several board games. Just as he was about to pay for the 3-hour couple set, he saw a new event written next to the price tag.
The event said: "Win against the owner and it's free; lose or draw and pay an extra 5000 won." Confident in his board game skills, Joo-eon asked the owner about the rules, which were as follows.
- Each player receives N cards. (N is odd)
- Each player picks one card, and the numbers written on the two cards are compared. (Each number is an integer between 0 and 100,000)
- The player who played the card with the smaller number gains 1 point, and the cards used in that round are discarded. (On a tie, neither player gains a point)
- After N rounds, the player who has gained at least (N+1)/2 points wins.
- If nobody has gained at least (N+1)/2 points, the game ends with no winner.
Joo-eon wants to play only if he has even the slightest chance of winning.
Given the numbers on the owner's cards and the numbers on Joo-eon's cards, determine whether Joo-eon should play.
Input
N is given on the first line. (1 ≤ N < 100,000, N is odd)
The numbers on the N cards Joo-eon received are given on the second line.
The numbers on the N cards the owner received are given on the third line.
Output
If Joo-eon has even the slightest chance of winning, print "YES". If there is no chance of Joo-eon winning, print "NO".
Hint
- Joo-eon: 2, owner: 3
- Joo-eon: 1, owner: 2
- Joo-eon: 3, owner: 5
For sample input 1, playing as above gives a case where Joo-eon gains 3 points and wins the game. Since Joo-eon has a chance of winning, print YES.