I. Bashar and Hamada

Codeforces

IDCF10226I

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Bashar is a very smart person, he invented a new function $F (S)$, where $S$ is a multiset of integers. The function $F (S)$ returns the sum of the absolute difference between every pair of elements in $S$. For example $F (${$3, 3, 1, 7$}$)$ = $bar.v 3 -3 bar.v$ + $bar.v 3 -1 bar.v$ + $bar.v 3 -7 bar.v$ + $bar.v 3 -1 bar.v$ + $bar.v 3 -7 bar.v$ + $bar.v 1 -7 bar.v$ = $18$. After that Bashar gave Hamada an array $a$ that contains $n$ integers, and asked him to solve this problem. For every $k$ such that $(2 <= k <= n)$, Hamada should choose a subsequence of $k$ integers from $a$, such that $F (S)$ is maximised. Hamada couldn't solve the problem and he asked you for help. The first line of input contains one integer $n$ $(2 <= n <= 3 times 10^5)$ which is the size of array $a$. The second line contains $n$ integers, the $i^(t h)$ one is $a_i$ $(1 <= a_i <= 10^8)$, which is the $i^(t h)$ element in the array. For every $k$ such that $(2 <= k <= n)$, print the maximum possible $F (S)$ of a subsequence of size $k$, starting from $k = 2$ ending at $k = n$. a subsequence of size $k$ is a sequnece that can be obtained be removing $n -k$ integers from $a$. ## Input The first line of input contains one integer $n$ $(2 <= n <= 3 times 10^5)$ which is the size of array $a$.The second line contains $n$ integers, the $i^(t h)$ one is $a_i$ $(1 <= a_i <= 10^8)$, which is the $i^(t h)$ element in the array. ## Output For every $k$ such that $(2 <= k <= n)$, print the maximum possible $F (S)$ of a subsequence of size $k$, starting from $k = 2$ ending at $k = n$. [samples] ## Note a subsequence of size $k$ is a sequnece that can be obtained be removing $n -k$ integers from $a$.

**Definitions** Let $ s $ be a string representing the hierarchical structure of $ n $ soldiers, where each soldier is encoded as: $$ \text{Soldier} = \text{Id} + \text{Subordinates}, \quad \text{Subordinates} = (\text{Soldier})^* $$ Each soldier's ID is a positive integer, and every ID from $ 1 $ to $ n $ appears exactly once. Let $ \text{parent}[i] \in \{0, 1, 2, \dots, n\} $ denote the supervisor of soldier $ i $, where $ \text{parent}[i] = 0 $ iff soldier $ i $ is the root (king). **Constraints** 1. $ 1 \le n \le 1.4 \times 10^5 $ 2. $ |s| \le 10^6 $ 3. The string $ s $ is well-formed: every opening bracket `(` has a matching closing bracket `)`, and IDs are positive integers in $ [1, n] $, each appearing exactly once. **Objective** Parse the string $ s $ to determine the parent of each soldier $ i \in \{1, \dots, n\} $, and output $ \text{parent}[1], \text{parent}[2], \dots, \text{parent}[n] $ as space-separated integers.

API Response (JSON)

{
  "problem": {
    "name": "I. Bashar and Hamada",
    "description": {
      "content": "Bashar is a very smart person, he invented a new function $F (S)$, where $S$ is a multiset of integers. The function $F (S)$ returns the sum of the absolute difference between every pair of elements ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10226I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bashar is a very smart person, he invented a new function $F (S)$, where $S$ is a multiset of integers.\n\nThe function $F (S)$ returns the sum of the absolute difference between every pair of elements ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s $ be a string representing the hierarchical structure of $ n $ soldiers, where each soldier is encoded as:  \n$$ \\text{Soldier} = \\text{Id} + \\text{Subordinates}, \\quad \\text{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments