D. Gold paint optimization

Codeforces

IDCF10179D

Time10000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

See PDF statement in attachment. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of nodes. Let $ P = (p_1, p_2, \dots, p_n) $ be the parent array, where $ p_i \in \{0, 1, \dots, i-1\} $, and $ p_i = 0 $ indicates node $ i $ is a root. Let $ T = (V, E) $ be the rooted forest with $ V = \{1, 2, \dots, n\} $ and $ E = \{ (p_i, i) \mid p_i \neq 0 \} $. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 0 \leq p_i < i $ for all $ i \in \{1, \dots, n\} $ **Objective** Find a permutation $ A = (a_1, a_2, \dots, a_n) $ of $ \{1, 2, \dots, n\} $ such that, when the method from the previous problem is applied to $ A $, the resulting forest (in terms of parent-child structure) is isomorphic to $ T $ under node relabeling. The method (from previous problem): - Nodes are processed in order $ 1 $ to $ n $. - Each node $ i $ is attached as a child to the *rightmost* previously processed node with value *greater than* $ a_i $. - If no such node exists, it becomes a root. **Goal**: Construct $ A $ such that the *tree structure* induced by this rule is isomorphic to $ T $.

API Response (JSON)

{
  "problem": {
    "name": "D. Gold paint optimization",
    "description": {
      "content": "See PDF statement in attachment. ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10179D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "See PDF statement in attachment.\n\n[samples]...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of nodes.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be the parent array, where $ p_i \\in \\{0, 1, \\dots, i-1\\} $, and $ p_i = 0 $ indicates node $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments