F. Musical Chairs

Codeforces

IDCF10226F

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Essa is playing Musical Chairs with his friends, Musical chairs, is a game of elimination involving players, chairs, and music, with one fewer chair than players. When the song ends whichever player fails to sit on a chair is eliminated, with a chair then being removed and the process repeated until only one player remains. As we know Essa gets really competitive and will be willing to do anything to win, so he memorized each song's length in the playlist and the order they will be played. He also knows the order of the chairs that will be eliminated at the beginning of each turn, now at each beginning of a turn, Essa decides whether the group moves in clockwise or counterclockwise. Each player changes their position after each second. The chairs will be used to form a circle, so if Essa chooses to move clockwise, each $i^("th")$ player will move to $i + 1$ position and the player at the last position will move to the first position. If Essa chooses to move counterclockwise, each $i^("th")$ player will move to $i -1$ position, and the player at the first position will move to the last position. Given Essa's initial position, the length of each song and the order the chairs will be eliminated. Is there a way Essa can win? Note that each time a chair is removed, the circle gets smaller. The first line will contain 2 integers $n$ number of players ($2 <= n <= 1000$) and $p$ Essa's initial position ($1 <= p <= n$). The second line will contain $n -1$ integers, the length of the $i^("th")$ song in seconds ($1 <= a i^("th") <= 10^9$). The third line will contain $n -1$ distinct integers $j^("th")$ the order that the chairs will be eliminated ($1 <= a j^("th") <= n$). print "Yes" without quotations if there's a way Essa can win, otherwise print "No" without quotations. ## Input The first line will contain 2 integers $n$ number of players ($2 <= n <= 1000$) and $p$ Essa's initial position ($1 <= p <= n$).The second line will contain $n -1$ integers, the length of the $i^("th")$ song in seconds ($1 <= a i^("th") <= 10^9$).The third line will contain $n -1$ distinct integers $j^("th")$ the order that the chairs will be eliminated ($1 <= a j^("th") <= n$). ## Output print "Yes" without quotations if there's a way Essa can win, otherwise print "No" without quotations. [samples]

**Definitions** Let $ N \in \mathbb{Z} $ be the number of fighters. For each fighter $ i \in \{1, \dots, N\} $: - $ (x_i, y_i) \in \mathbb{R}^2 $: position in the arena. - $ a_i \in [0, 359] $: center angle of field of view (in degrees). - $ r_i \in [0, 89] $: half-angle range of field of view (in degrees). The field of view of fighter $ i $ is the conical region centered at $ (x_i, y_i) $, extending from angle $ a_i - r_i $ to $ a_i + r_i $ (modulo 360), with infinite radius. Kassandra starts at an arbitrary position (not specified) and may move freely **until** she knocks out a fighter. Once she knocks out fighter $ j $, she occupies position $ (x_j, y_j) $. **Constraints** 1. $ 1 \le N \le 3000 $ 2. All $ (x_i, y_i) $ are distinct. 3. For each $ i $, $ 0 \le a_i \le 359 $, $ 0 \le r_i \le 89 $. **Objective** Find a permutation $ \pi \in S_N $ (ordering of knockout) such that for all $ k \in \{1, \dots, N\} $: - When Kassandra moves to knock out fighter $ \pi_k $, she is **not** in the field of view of any fighter $ j \in \{ \pi_1, \dots, \pi_{k-1} \} $ **before** the knockout. - After knocking out $ \pi_k $, she is at $ (x_{\pi_k}, y_{\pi_k}) $. If such a permutation exists, output $ \pi_1, \pi_2, \dots, \pi_N $. Otherwise, output $ -1 $. **Note**: Kassandra is not in the field of view of any fighter **at the start** (assumed safe).

API Response (JSON)

{
  "problem": {
    "name": "F. Musical Chairs",
    "description": {
      "content": "Essa is playing Musical Chairs with his friends, Musical chairs, is a game of elimination involving players, chairs, and music, with one fewer chair than players. When the song ends whichever player ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10226F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Essa is playing Musical Chairs with his friends, Musical chairs, is a game of elimination involving players, chairs, and music, with one fewer chair than players.\n\nWhen the song ends whichever player ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of fighters.  \nFor each fighter $ i \\in \\{1, \\dots, N\\} $:  \n- $ (x_i, y_i) \\in \\mathbb{R}^2 $: position in the arena.  \n- $ a_i \\in [0, 359] $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments