E. Exhibition of Clownfish

Codeforces
IDCF10234E
Time1000ms
Memory256MB
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, m, k \in \mathbb{Z}^+ $ denote the number of planks, number of colors, and maximum allowed segment length, respectively. Let $ A = (a_1, a_2, \dots, a_m) \in \mathbb{Z}^m $ be the vector of paint amounts, where $ \sum_{i=1}^m a_i = n $ and $ 1 \le a_i \le n $. **Constraints** 1. $ 1 \le n \le 2 \cdot 10^5 $ 2. $ 1 \le m, k \le n $ 3. $ 1 \le a_i \le n $ for all $ i \in \{1, \dots, m\} $ 4. $ \sum_{i=1}^m a_i = n $ 5. Each plank must be assigned exactly one color $ i \in \{1, \dots, m\} $ 6. No contiguous segment of planks with the same color may exceed length $ k $ **Objective** Find a sequence $ C = (c_1, c_2, \dots, c_n) \in \{1, \dots, m\}^n $ such that: - For each color $ i $, the number of indices $ j $ with $ c_j = i $ is exactly $ a_i $, - Every maximal contiguous subsequence of equal values in $ C $ has length at most $ k $, or output $-1$ if no such sequence exists.
API Response (JSON)
{
  "problem": {
    "name": "E. Exhibition of Clownfish",
    "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": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10234E"
  },
  "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, m, k \\in \\mathbb{Z}^+ $ denote the number of planks, number of colors, and maximum allowed segment length, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_m) \\in \\mathbb{Z}^m ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments