J. Catch the Monster

Codeforces

IDCF10134J

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Manse and Eckels are special agents of time patrol. Now they are trying to catch Faceless Chrono Monster, whose existence threatens the integrity of space-time continuum. The monster dwells between worlds on the Time Tree, consisting of n time nodes, connected with time corridors. Each character can move from one node to another through time corridors. There are time corridors, and any time node can be reached from any other one by moving through the time corridors. Manse and Eckels can initially appear in two arbitrary (not necessarily distinct) time nodes, wherever they want, after which they would be able to move between time nodes through time corridors independently of each other. As soon as one of them meets the Monster, the Monster will be instantly destroyed, no matter whether it happened in the node or in one of the corridors. The problem is that the Faceless Chrono Monster moves along the Time Tree many times faster than patrolmen, and, most importantly, foresees the future. Thereby, he knows in advance, in which time nodes the heroes will appear and how they will move, so he can use this, planning his escape. The Monster is unbelievably clever, so he will use his abilities optimally to survive. Will Mance and Eckels be able to destroy the Monster? The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of time nodes. The next lines describe time corridors. They contain two integers each, xi and yi, separated by a space (1 ≤ xi, yi ≤ n, xi ≠ yi) — numbers of time nodes connected by i-th time corridor. If the heroes will be able to destroy the Monster, output «_YES_» (without quotes), otherwise output «_NO_» (without quotes). ## Input The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of time nodes.The next lines describe time corridors. They contain two integers each, xi and yi, separated by a space (1 ≤ xi, yi ≤ n, xi ≠ yi) — numbers of time nodes connected by i-th time corridor. ## Output If the heroes will be able to destroy the Monster, output «_YES_» (without quotes), otherwise output «_NO_» (without quotes). [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of subarrays, with $ 1 \leq n \leq 15 $. Let $ S = \{S_1, S_2, \dots, S_n\} $ be the set of given subarrays, where each $ S_i = (a_{i,1}, a_{i,2}, \dots, a_{i,m_i}) $ is a sequence of integers with $ 1 \leq m_i \leq 100 $ and $ 1 \leq a_{i,j} \leq 10^9 $. **Constraints** Each $ S_i $ is a contiguous subarray of the target array $ A $. **Objective** Find the minimal length of an array $ A $ such that every $ S_i \in S $ appears as a contiguous subarray in $ A $. Equivalently, find the shortest superarray that contains all $ S_i $ as contiguous subsequences.

API Response (JSON)

{
  "problem": {
    "name": "J. Catch the Monster",
    "description": {
      "content": "Manse and Eckels are special agents of time patrol. Now they are trying to catch Faceless Chrono Monster, whose existence threatens the integrity of space-time continuum. The monster dwells between wo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10134J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Manse and Eckels are special agents of time patrol. Now they are trying to catch Faceless Chrono Monster, whose existence threatens the integrity of space-time continuum. The monster dwells between wo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of subarrays, with $ 1 \\leq n \\leq 15 $.  \nLet $ S = \\{S_1, S_2, \\dots, S_n\\} $ be the set of given subarrays, where each $ S_i = (a_{i,1}, a_{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments