D. Meeting Bahosain

Codeforces

IDCF10226D

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Essa wanted to meet the most powerful number theorist of all time: Bahosain, but Bahosain does not waste his precious time, so he gave Essa this puzzle in order to test his abilities. Given two arrays, the second array only has distinct elements, Essa can do the following as many times as he wants to make all numbers in first array equal. The first line containing two space separated integers $n, m$ ($1 <= n, k <= 10^6$) represent the length of the first and second array. the second line contains n integers represent the first array ($1 <= a [ i ] <= 10^9$) the third line contains m integers represent the second array ($1 <= b [ i ] <= 10^9$) Print Yes, if it's possible to make all numbers in first array equal; and No in the opposite case. ## Input The first line containing two space separated integers $n, m$ ($1 <= n, k <= 10^6$) represent the length of the first and second array.the second line contains n integers represent the first array ($1 <= a [ i ] <= 10^9$)the third line contains m integers represent the second array ($1 <= b [ i ] <= 10^9$) ## Output Print Yes, if it's possible to make all numbers in first array equal; and No in the opposite case. [samples]

**Definitions** Let $ L \in \mathbb{Z} $ be the number of levels, $ 1 \leq L \leq 134 $. For each level $ \ell \in \{1, \dots, L\} $, let $ (r_\ell, c_\ell) \in \{1, \dots, 12\}^2 $ denote the robot's starting position. Let $ G $ be a fixed $ 12 \times 12 $ grid with cells classified as: - **Blocked** (fully black): impassable, - **White**: passable, - **Crossed**: passable and target. Let $ T \subseteq \{1, \dots, 12\}^2 $ be the set of crossed cells (target positions). **Constraints** 1. The robot starts on a non-blocked cell: $ (r_\ell, c_\ell) \notin \text{Blocked} $. 2. The robot may move in directions $ \{U, D, L, R\} $, but: - A move is invalid if it would take the robot to a blocked cell or outside the grid. - Invalid moves are ignored (robot stays in place). 3. The goal is to reach any cell in $ T $ in at most 1000 moves. **Objective** For each level $ \ell $, output: - An integer $ n_\ell \in \{0, 1, \dots, 1000\} $, the number of moves, - A string $ s_\ell \in \{U, D, L, R\}^{n_\ell} $, the sequence of moves, such that the robot, starting from $ (r_\ell, c_\ell) $ and applying $ s_\ell $ step-by-step (ignoring invalid moves), ends on a cell in $ T $.

API Response (JSON)

{
  "problem": {
    "name": "D. Meeting Bahosain",
    "description": {
      "content": "Essa wanted to meet the most powerful number theorist of all time: Bahosain, but Bahosain does not waste his precious time, so he gave Essa this puzzle in order to test his abilities. Given two array",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10226D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Essa wanted to meet the most powerful number theorist of all time: Bahosain, but Bahosain does not waste his precious time, so he gave Essa this puzzle in order to test his abilities.\n\nGiven two array...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ L \\in \\mathbb{Z} $ be the number of levels, $ 1 \\leq L \\leq 134 $.  \nFor each level $ \\ell \\in \\{1, \\dots, L\\} $, let $ (r_\\ell, c_\\ell) \\in \\{1, \\dots, 12\\}^2 $ denote the rob...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments