L. Chess Match

Codeforces
IDCF10097L
Time2000ms
Memory256MB
Difficulty
English · Original
Formal · Original
Two best chess teams in the world are preparing to the match against each other. Both teams have n players. Each player has a rating, and the player with the higher rating always wins. Ratings of the players in the first team are a1, a2, ..., an, and in the second team — b1, b2, ..., bn. There are no players with equal ratings in both teams. The chess match between two teams consists of n games, called the games on the first, second, ..., n-th board. Before the match captains of both teams must decide which player will play on which board. When they do that, they don't know the opponent's choice. After that a single game is played on each board. The team with the higher score wins. For both teams, determine if it can win the match. The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of players in each team. The second line contains n space-separated integers ai (1 ≤ ai ≤ 109) — the ratings of the players in the first team. The third line contains n space-separated integers bi (1 ≤ bi ≤ 109) — the ratings of the players in the second team. All ai and bi are pairwise distinct. Output «_First_» if only first team can win, «_Second_» if only second team can win, «_Both_» if both teams can win, and «_None_» if there will be a draw in any case. Don't output quotes. ## Input The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of players in each team.The second line contains n space-separated integers ai (1 ≤ ai ≤ 109) — the ratings of the players in the first team.The third line contains n space-separated integers bi (1 ≤ bi ≤ 109) — the ratings of the players in the second team.All ai and bi are pairwise distinct. ## Output Output «_First_» if only first team can win, «_Second_» if only second team can win, «_Both_» if both teams can win, and «_None_» if there will be a draw in any case. Don't output quotes. [samples]
**Definitions** Let $ n \in \mathbb{Z}^+ $, $ A = (a_1, a_2, \dots, a_n) $, $ B = (b_1, b_2, \dots, b_n) $ be sequences of distinct positive integers representing the ratings of players in team 1 and team 2, respectively. **Constraints** $ 1 \leq n \leq 200000 $, $ 1 \leq a_i, b_j \leq 10^9 $, all elements in $ A \cup B $ are distinct. **Objective** Determine whether team 1 can win (i.e., score > team 2), team 2 can win, both can win, or neither can win (i.e., all match outcomes result in a draw), under optimal and independent assignment of players to boards (i.e., both teams choose bijections $ \sigma, \tau: [n] \to [n] $ independently to assign their players to boards, and the outcome of board $ i $ is determined by comparing $ a_{\sigma(i)} $ and $ b_{\tau(i)} $). Let $ W_1 $ be true if there exists a permutation $ \sigma $ such that for all permutations $ \tau $, the number of $ i \in [n] $ with $ a_{\sigma(i)} > b_{\tau(i)} $ is strictly greater than the number with $ a_{\sigma(i)} < b_{\tau(i)} $. Let $ W_2 $ be true if there exists a permutation $ \tau $ such that for all permutations $ \sigma $, the number of $ i \in [n] $ with $ b_{\tau(i)} > a_{\sigma(i)} $ is strictly greater than the number with $ b_{\tau(i)} < a_{\sigma(i)} $. Output: - “First” if $ W_1 \land \neg W_2 $ - “Second” if $ \neg W_1 \land W_2 $ - “Both” if $ W_1 \land W_2 $ - “None” if $ \neg W_1 \land \neg W_2 $
API Response (JSON)
{
  "problem": {
    "name": "L. Chess Match",
    "description": {
      "content": "Two best chess teams in the world are preparing to the match against each other. Both teams have n players. Each player has a rating, and the player with the higher rating always wins. Ratings of the ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10097L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Two best chess teams in the world are preparing to the match against each other. Both teams have n players. Each player has a rating, and the player with the higher rating always wins. Ratings of the ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ A = (a_1, a_2, \\dots, a_n) $, $ B = (b_1, b_2, \\dots, b_n) $ be sequences of distinct positive integers representing the ratings of players in team 1 an...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments