I. Interplanetary

Codeforces
IDCF10234I
Time1000ms
Memory1024MB
Difficulty
English · Original
Formal · Original
The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf [samples]
**Definitions** Let $ n, p, M, m \in \mathbb{Z}^+ $ be given integers. Let $ C = \{(x_i, y_i) \mid i \in \{1, \dots, n\}\} $ be the set of complaints, where $ 1 \le x_i < y_i \le p $. Let $ S = \{(l_j, r_j) \mid j \in \{1, \dots, p\}\} $ be the set of power constraints for each station $ j $, where $ 1 \le l_j \le r_j \le M $. Let $ I = \{(u_k, v_k) \mid k \in \{1, \dots, m\}\} $ be the set of interfering station pairs, where $ 1 \le u_k < v_k \le p $. **Constraints** 1. For each complaint $ (x, y) \in C $, at least one of stations $ x $ or $ y $ must be selected. 2. For each selected station $ j $, the chosen signal power $ f $ must satisfy $ l_j \le f \le r_j $. 3. For each interfering pair $ (u, v) \in I $, stations $ u $ and $ v $ cannot both be selected. 4. The signal power $ f $ must be an integer in $ [1, M] $. **Objective** Find an integer $ f \in [1, M] $ and a subset $ T \subseteq \{1, \dots, p\} $ such that: - $ \forall (x, y) \in C $, $ x \in T $ or $ y \in T $, - $ \forall j \in T $, $ l_j \le f \le r_j $, - $ \forall (u, v) \in I $, $ \neg (u \in T \land v \in T) $. If such $ f $ and $ T $ exist, output $ |T| $, $ f $, and the elements of $ T $. Otherwise, output $ -1 $.
API Response (JSON)
{
  "problem": {
    "name": "I. Interplanetary",
    "description": {
      "content": "The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10234I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf\n\n[samples]...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, p, M, m \\in \\mathbb{Z}^+ $ be given integers.  \nLet $ C = \\{(x_i, y_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of complaints, where $ 1 \\le x_i < y_i \\le p $.  \nLet $ S = ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments