Restore Memories

Author: s23f32
Preparation: s23f32

Solution

For subtasks with $All\ C_i\ equal$
You can get $47$ points by doing a greedy and tracking all positions of memories.

Now for full solution
Considering connected an edge between where $i$ initally is, and where it should end.
Each node has in-degree and out-degree of $1$
Therefore, the graph made of multiple cycles.
By swapping the positions of $2$ elements, you can:
1. Merge two cycles into one
2. Split one cycle into two
Our goal is to make each node point to itself (self-loop)
To "solve" a cycle, you either:
1. Use the minimum value in the cycle to break the cycle one by one
2. Merge the cycle with the node with minimum $C_i$, and use that node to break the cycle one by one

Basically in mathematical language,
Let $sz$ be the size of the loop,
$loopmn$ be the minimum cost within the loop,
$totmn$ be the minimum cost of the all nodes.
The cost of the loop is $min((sz-1)*loopmn,(sz+1)*totmn)$
Simply evaluate this in $O(n)$ to AC.

Relive Memories

Author: wy24215
Preparation: wy24215

Easiest task in the problem set, also longest statement. (longer statement -> easier task?)

Solution

First turn every (90 °-x) into x by flipping sin and cos. Notice that to maximise $A$, you have to add up every sin^2(x) and cos^2(x) whenever possible. So count the number of each of them, and the minimum number of one of them is $A$, which is the maximum number of sin^2(x) and cos^2(x) you can pair up. And you can find $B$ and $C$ subsequently. A fun fact is that of $B$ or $C$ must be $0$.

Recall Memories

Author: s22l19
Preparation: s22l19

Solution:

Part I (Average)

Subtask 2

The average of $A_{l…r}$ is $0$ if its sum is $0$.
The task become “find the number of subarray such that its sum is zero”.
It can be done by storing the prefix sum in std multiset or map or anything. (refer to C2435)

Subtask 3

Subtract each element in $A$ by $K$. Then the problem is same as in subtask 2.

Part II (Median)

Let $f(x)=($ number of subarrays such that the median is $\ge x)$. The answer of the task equals $f(K)-f(K+1)$.
To find $f(x)$, denote $B_i=1$ if $A_i\ge x$ or else $B_i=-1$. A subarray have median $\ge x$ when the sum of $B$ is larger than or equal to $0$. This can be calculated by keep track on the frequency array of prefix sum, similar to that in part I.