D. Magical Bamboos

Codeforces

IDCF10135D

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

In a magical forest, there exists N bamboos that don't quite get cut down the way you would expect. Originally, the height of the ith bamboo is equal to hi. In one move, you can push down a bamboo and decrease its height by one, but this move magically causes all the other bamboos to increase in height by one. If you can do as many moves as you like, is it possible to make all the bamboos have the same height? The first line of input is T – the number of test cases. The first line of each test case contains an integer N (1 ≤ N ≤ 105) - the number of bamboos. The second line contains N space-separated integers hi (1 ≤ hi ≤ 105) - the original heights of the bamboos. For each test case, output on a single line "yes” (without quotes), if you can make all the bamboos have the same height, and "no" otherwise. ## Input The first line of input is T – the number of test cases.The first line of each test case contains an integer N (1 ≤ N ≤ 105) - the number of bamboos.The second line contains N space-separated integers hi (1 ≤ hi ≤ 105) - the original heights of the bamboos. ## Output For each test case, output on a single line "yes” (without quotes), if you can make all the bamboos have the same height, and "no" otherwise. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ n_k \in \mathbb{Z} $ denote the number of bamboos, with $ 1 \leq n_k \leq 10^5 $. - Let $ H_k = (h_{k,1}, h_{k,2}, \dots, h_{k,n_k}) $ be the initial heights of the bamboos, where $ h_{k,i} \in \mathbb{Z} $ and $ 1 \leq h_{k,i} \leq 10^5 $. **Constraints** 1. $ 1 \leq T \leq 10^5 $ 2. For each test case $ k $: - $ 1 \leq n_k \leq 10^5 $ - $ 1 \leq h_{k,i} \leq 10^5 $ for all $ i \in \{1, \dots, n_k\} $ **Objective** Determine whether there exists a non-negative integer $ m $ (number of moves) and non-negative integers $ x_1, x_2, \dots, x_{n_k} $ (number of times each bamboo is pushed down) such that: - $ \sum_{i=1}^{n_k} x_i = m $, - and for all $ i, j \in \{1, \dots, n_k\} $: $$ h_{k,i} - x_i + (m - x_i) = h_{k,j} - x_j + (m - x_j) $$ Equivalently, after $ m $ total moves, all bamboos reach the same final height: $$ h_{k,i} + m - 2x_i = C \quad \text{for some constant } C, \text{ for all } i $$ Rewriting: $$ 2x_i = h_{k,i} + m - C $$ Thus, $ h_{k,i} + m - C $ must be even and non-negative for all $ i $, and $ x_i \geq 0 $. Since $ C $ is the common final height, and $ m $ is free to choose, the condition reduces to: All values $ h_{k,i} $ must have the same parity (i.e., all even or all odd). **Answer Condition** Output "yes" if all $ h_{k,i} $ in the test case have the same parity; otherwise, output "no".

API Response (JSON)

{
  "problem": {
    "name": "D. Magical Bamboos",
    "description": {
      "content": "In a magical forest, there exists N bamboos that don't quite get cut down the way you would expect.  Originally, the height of the ith bamboo is equal to hi. In one move, you can push down a bamboo a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10135D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In a magical forest, there exists N bamboos that don't quite get cut down the way you would expect. \n\nOriginally, the height of the ith bamboo is equal to hi. In one move, you can push down a bamboo a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the number of bamboos, with $ 1 \\leq n_k \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments