Takeaways

Get subtasks score is important!
Also learn more standard algorithms (Q2 and Q3 is standard algo!)

Happy String ... Again?

Author: s23f32
Preparation: s23f32
Solution:
Link to solution slide

JSOIII

Author: s22l19
Preparation: s22l19

Solution:

Subtask 1,2

You cannot change colour of any cells.
Simply find the length of the longest non-beautiful subarray. Naively implement is $O(N^3)$ to $O(N^2)$ (score: 30).

Subtask 3 (K=0)

Observation: denote each R as $1$ and B as $-1$. A subarray is beautiful if its sum $\ge 0$. Optimize the above solution.
We can do binary search for answer. When checking for a value of $M$, check whether there exists a subarray with length larger than or equal to $M$ is non-beautiful. We can construct a prefix sum array $ps[0…N]$.
So, you can loop $i$ from $1$ to $N$. At a $i$, check whether there exists a $l$ such that $ps[i]-ps[l-1]<0$. This expression means the subarray $[l…i]$ is non-beautiful. By swapping terms we can get $ps[i]< ps[l-1]$. So, if $max(ps[0…i-M]) > ps[i]$, there exist such $l$, and the $M$ is rejected.

Subtask 4,5,6

Use the binary search solution in subtask 3. Use a greedy approach to change colour. When you find a $l$ that $s[l…i]$ is non-beautiful, choose the rightmost $-1$ in $s[1…i]$ and update it to $1$. It is true that this approach minimizes the operations used. So reject that $M$ if the operations exceeds $K$.
Moreover, it can be proven that the index of $-1$s you update must be in the range $[i-M+1…i]$. Therefore you can actually do update without seg tree with careful implementation.
You can use seg tree to do update but the time complexity is too bad to AC this task.

Time complexity: $O(Nlog^2 N)$ for seg tree, $O(NlogN)$ if your update operation is $O(1)$.

Winnie, Yoyo and the Walnut Yoghurt

Author: wy24215
Preparation: wy24215

Something to tell you...

Greek people really have yoghurt with walnuts! What a healthy and fascinating combination. Yoghurt is for British English and Yogurt is for American English. If you use both of them, then it is Goodest English. Walnuts are good for your brain, and yoghurt is rich in protein and calcium, which is the perfect combination for breakfast for OIers. Guys should really try it yourself, although I haven't done so. Guess what’s the meaning behind the name of the problem. (it’s a weird one actually, just in order to achieve some special meaning)
Easiest and Very Standard problem in the problem set. Tell you a secret, the solution is just partial sum + binary search. Really learn them if you haven’t, as they are fundamentals. You can get decent scores if you know for-loop and manage to read the long long Goodest English.
Tasks Are Not Sort By Difficulty!!!
Use long long int!!!

Subtask 1:

Input two numbers, and see $(a+b)$ or $a$ or $b$ is larger.

Subtask 2:

Intuition: when $K = 2$, we can just pick any number and use their sum as the final result.
Therefore, the answer is the sum of every non-negative element in $W$, as we can get the largest sum by picking all the non-negative elements.
Caution! Handle the cases when every element is negative.

Subtask 3:

Using the idea of subtask 2, we can just merge every element as $W_i > 0$ in this subtask. However, we can find that we’ll leave 2 elements and cannot do further mergings when $N$ is even. So, we should choose the largest $N-1$ elements when $N$ is even and the sum of the whole array when $N$ is odd. To find the sum of largest $N-1$ elements, just find (total sum - minimum element), or sort the whole array to calculate.

Subtask 4:

Refer to subtask 2, we sum every non-negative element when $K = 2$. But this time we have yoghurts added. Looping the whole array every time will just cause $O(N \times Q)$ complexity, which will certainly lead to TLE.
How to speed up? Note that this is not range add, so we can just use a variable let’s say $H$ to store the total value added to all elements accumulatively, which is some kind of brief idea of lazy add you may see in different problems (e.g. M2214 “Fluctuating Market”, PL24L “Look left? Look right”, Segment Tree Lazy Addition,...). We sum all elements where $H + W_i >= 0$ which means $W_i >= -H$. So, we can sort the whole array, and precompute the suffix sum. For every query, binary search the smallest $i$ such that $W_i >= -H$, and answer with the (suffix sum $+$ number of elements $\times H$).
Caution Again! Handle the cases when every element is negative.

Subtask 5:

Actually, we can observe that the answer is exactly summing up any subset of $(1 + (K - 1) \times B)$ elements for a sum integer $D$, as we can describe the merging action as adding the values $K-1$ elements to a single element. Notice that negative elements can also be picked like in the case merge $[-1,2,3]$. So, just brute force on the number of elements and greedily pick the largest ones. Sort the array first so you can handle these easily. Make sure that the constants wouldn’t be too large, even $O(NKQ)$ may pass with such loose constraints. But still, implementing $O(NQ)$ with probably a log constant wouldn’t be harder than implementing $O(NKQ)$.

Full Solution:

Actually, the answer can be either:
> merge the maximum possible number of positive elements
> merge the maximum possible number of positive elements, and one more merge containing positive and negative elements
(try to prove it yourself and it’s not hard to prove :)
So, just binary search on the maximum number of positive elements you can merge. If it is $Z$, try both possibilities of $Z$ and $Z + K – 1$ elements. Sort the array and do partial sum (or just some precomputation), so that we can query the sum of $Z$ largest elements in at most $O(logN)$. When every $H$ is changed, just do the binary search and lazy add like Subtask 4.
Caution Again and Again! Handle the cases when every element is negative.

Alternative Solution 1:

Instead of doing binary search every time, sort the queries and we find the answers using two pointers technique. Notice that when $H$ increases, the $B$ in $(1 + (K - 1) \times B)$ either increase or keep the same. $O(Q+NlogN)$ is achieved still with a log constant, but it is practically faster as the $O(NlogN)$ using stl c++ sort is close to $O(N)$. Apply this trick when you face TLE with data with $N$ and $Q$ around $10^6$. Also, adding fast I/O cin.tie(nullptr)->ios:sync_with_stdio(0); is another important thing for constant optimization.

Other Solutions:

There are other interesting ways to solve this task and the author will just let you come up with ideas yourself.