> B5 only included submission with explanations in the comments

Problems: [TLX](https://tlx.toki.id/problems/osnp-2023)

# B1
We can simply store the sum and the count of fruits in container $A$ and $B$ in a variable. For container B, it is required to store the fruits individual weights in an array, and then sort it in a non-decreasing order.

Then we can greedily take the first element of container $B$ and move it to container $A$, while the condition $avg(A) \leq avg(B)$ is not satisfied, where $avg(X)$ denotes the average weight of fruits in container $X$.

Additionally, from the example case, it seems that the problem statement has a typo. And we're required to take weights of $\geq b$ instead of $>b$. For this part, we can use a do while loop, and take all fruits with equal weights.

Time complexity increased to n log n due to sorting.

Time complexity: $O(n\ log\ n)$

---

# B2
Let $A_i$ be the strength of the i-th potion. If there exists a strictly increasing sequence of length $M$, where $M$ is maximum and for each $i$, it holds that $A_i + K < A_{i+1}$ $(1 \leq i < M)$, and $M+K \leq A_1$ then $M$ is the answer.

Let $A_0$ be a potion excluded from such sequence, and $A_0 < A_i$ for any $i$. Then if $A_0 + K \geq A_i$ and $A_0 + K < A_{i+1}$ in the described sequence, then we can replace $A_i$ with $A_0$ and the sequence will still be valid, so the answer is still $M$. Otherwise, $A_0$ must be included in the sequence for the maximum $M$.

We can greedily take the first element satisfying the condition $T < A_x$ where T is current tree height, and $A_x$ is the strength of the potion to use, until the condition is not satisfied.

$A_x$ can be found simply by doing a binary search or just using any potion possible linearly, either way, complexity is the same due to sorting.

Time complexity: $O(n\ log\ n)$

---

# B3

> $D_i$ is the difficulty to build a powerplant in the $i$-th village, and $Ti$ is the cost to build a powerplant by the $i$-th company.

To minimize cost, it is required to minimize $D_is$ and $T_is$ used.

Minimizing $T_is$ is simple, because any company can work on any village. We can simply sort the array containing $T_is$ in a non-decreasing order.

Minimizing $D_is$ can be done through multiple ways. One of which is using DSU.
For every join operation between a pair of village, the parent will store the minimum difficulty. So to get the minimum $D_is$ after all roads have been considered, is to simply get the difficulties of roots from the village 1 to N, yielding an array of $D_is$ with size $k$, then sort them in a non-decreasing order.

After minimizing the $D_is$ and $T_is$, if $k$ is greater than $M$, then it is impossible. So we output `-1`.

Otherwise, pair the $D_is$ and $T_is$ in such a way that minimizes the total cost.

It turns out, to minimize the total cost, pairing the lowest $D_is$ with the highest $T_is$ yields minimum cost.

$\displaystyle\sum_{i=1}^{k} D_{i} \cdot T_{k-i+1}$

Where $k$ is the count of parents after all the join processes. We ignore $T_i$ when $(k < i \leq M)$ to minimize cost.

Time complexity: $O(n\ log\ n)$

---

# B4 - Solution
In this problem, there are 4 movement types:

- Left
- Right
- Left followed by right
- Right followed by left

> There are many ways to solve this problem, and the attached solution here is not optimal. The answer can be found in $O(n)$ using two pointers.

For one directional movements, we can simply do a binary search for $X - K$ (left) and $X + K$ (right).

For the latter 2 types of movements, simply iterate for every artifacts, and do a binary search for the left or right indices. Also, to reduce the time complexity, it is beneficial for us to use a prefix sum for artifacts values.
- When $X \geq C_i$, left index is $i$ and right position is $X + (K - 2\ |C_i - X|)$ (Left followed by right)
- When $X \leq C_i$, right index is $i$ and left position is $X - (K - 2\ |C_i - X|)$ (Right followed by left)

*Note that position is different from index. To get the other index, we need to do a binary search with the position.

The maximum value of all these types of movements is the answer.

Time complexity: $O(n\ log\ n)$

---

# B5

For B5's Solution, visit [Upsolve Submission](https://tlx.toki.id/submissions/1478026)

---