This blog is for documenting my learning journey in competitive programming. Hope someone enjoys it and finds it helpful for their own learning.

Credit to ChatGPT and Claude for helping me find some great modern 1900 problems.

Theory

• I would recommend knowing all USACO Guide Gold topics. I think you should know most of them to get to CM, plus some more data structures such as tries and advanced segment tree techniques.

• To understand this blog, I would recommend completing all USACO Guide Silver topics.

Problem 1: 2174B

• The problem looks like classical DP, but $$$k$$$ is pretty high. In normal DP, we could do $$$dp[\text{position}][\text{prefix_max}][\text{cost}]$$$ and, for every state, try changing the current element into $$$k$$$ possible values. Total complexity: $$$O(nk^3)$$$.

• However, this is obviously going to TLE since the number of operations is too high for 2 seconds. So we try to find some observations that lead to a DP optimization.

1. Consider the optimal array $$$b$$$. If $$$b_i \gt 0$$$, then it should increase the prefix maximum. Otherwise, setting $$$b_i \gt 0$$$ would be suboptimal.

2. Using the first observation, we can see that the positive values in the optimal array $$$b$$$ would be strictly increasing. We can consider each element's contribution to the total sum as $$$b_i \cdot (\text{distance to the next positive element or the end})$$$.

• So we want to maximize the contribution. We should make the larger $$$b_i$$$ contribute more? Then it is optimal to put $$$b_i$$$ as far to the left as possible.

• This means we can store the first position that can hold value $$$i$$$, which removes the position dimension from our DP. Therefore, we can use $$$dp[\text{prefix_max}][\text{cost}]$$$, which helps us AC this problem.

Code: My solution

Problem 2: 2138B

• When the problem looks weird / ad hoc, the only way is casework :)

INITIAL KNOWLEDGE NEEDED:

• The minimum number of adjacent swaps needed to sort an array is the number of inversions in the array. Every swap of an adjacent inverted pair changes $$$a_i \gt a_{i+1}$$$ into $$$a_i \lt a_{i+1}$$$, reducing the number of inversions by $$$1$$$.

• After doing some casework, we can conclude that the array is not perfect if there is a triple $$$a_i \gt a_j \gt a_x$$$, where $$$i \lt j \lt x$$$. Otherwise, it is perfect.

• Once we get that, the answer is simple: calculate the maximum position $$$i$$$ such that there is a triple ending at $$$i$$$, and for every query, just use a segment tree to get the maximum in $$$[l, r]$$$.

Code: My solution

Problem 3: 2217D

• This problem was really hard for me to figure out.

• But the problem can be changed into splitting the array at each $$$p_i$$$, giving segments $$$[p_i, p_{i+1}-1]$$$, along with the first and last segments.

• Consider a change to be a position where $$$a_i \ne a_{i+1}$$$.

• We can pair changes from one segment with changes from another segment. This guarantees that one $$$p_i$$$ is between the two segments. Try drawing it out or imagining it.

• We can keep pairing changes from different segments as long as the largest number of changes in one segment is at most half the total number of changes.

• Otherwise, we match as many changes as possible with the other segments, then add the remaining changes in the biggest segment.

Code: My solution

Problem 4: 2231D

• This one is general knowledge of prefix sums + A BUNCH OF CASEWORK.

• Consider all the cases you need. Debugging skill IS THE MAIN SKILL NEEDED in this problem. If you AC all the sample test cases, then you would AC the tests... probably :)

• I'm not going into the details for this problem.

Code: My solution

Problem 5: 2246D

• This problem is game theory. Usually, there is an optimal way for Alice / Bob to defeat the other player, and if you know that optimal strategy, you can find the answer.

• The optimal strategy for Bob here is really simple.

• If there is an odd element in array $$$a$$$, he can always swap that odd element into $$$a_2$$$ and force $$$a_1$$$ to become $$$0$$$ through $$$-1$$$ or $$$/2$$$ operations. This turns it into a brute-force problem.

• So Alice should add to some elements to reduce the number of moves by making all numbers end in $$$X$$$ zeroes in binary. This allows the array to be divided by $$$2$$$ a total of $$$X$$$ times before Bob executes his optimal strategy.

• For each $$$X$$$, find the cost. But there is a second thing you should debug: what if you could do some more operations on $$$a_i$$$ to reduce the cost even further after dividing by $$$2$$$ a total of $$$X$$$ times? For example, $$$255 \to 256$$$.

• The extra addition cost would be $$$\text{amount_add} \cdot 2^X$$$. We know that we can reduce the number of moves by at most the bit count of the current number, which would be around $$$20$$$ to $$$30$$$. So just brute force it.

Code: My solution

Problem 6: 2133D

• This problem looks weird at first, but it's actually still casework. Literally almost every problem :))

• So let's say we ignore the chain damage thing. What would be the optimal answer without chain damage? Obviously, kill the top one first, then the second, then the third, and so on. The topmost one should be dropped first.

• Using that idea, when would it be beneficial to use the chain? It would be beneficial when there is a bunch of ones in front of a number. So when should we use the chain, and when should we not? That leads us to DP.

• We're looping from $$$n-1$$$ down to $$$0$$$ because it is optimal to throw the topmost one first.

Case 1: We just kill mob $$$i$$$ and add $$$dp[i+1]$$$ to the cost.

Case 2: We kill mob $$$i$$$, throwing mob $$$i+1$$$ down and creating a chain reaction. This leads to a few more cases.

Let $$$v$$$ be the first position after $$$i+1$$$ with $$$a_v \gt 1$$$.

Let $$$\text{fallcost}$$$ be the cost of eliminating both $$$a_i$$$ and $$$a_{i+1}$$$.

• We take $$$\text{fallcost} + dp[v]$$$, making them two separate stacks.

• We take $$$\text{fallcost} + dp[v-1]$$$, making $$$v$$$ fall.

• We take $$$\text{fallcost} + \text{cost}[v] - 1 + \text{remaining cost}$$$, adding position $$$v$$$ to the chain fall.

Code: My solution

Problem 7: 2226D

• Classic ad hoc / casework problem :))

• Okay, so let's do some casework. Hmm, if I want to sort the array, I should be able to move the smallest element to the left?

• I can swap adjacent elements if they have different parity.

• So then I can make all the even elements go to the left and all the odd elements go to the right.

• Okay, so how do I move the smallest element to the left? Hmm, what if there is a way to create a "reversing device" that allows me to put the elements in order?

• This gives us an insight: if the smallest and biggest elements have different parity, we can use the previous observation. Move all the elements with even parity after the biggest one to the rightmost side, and all the elements with the smallest element's parity before it to the leftmost side. This makes the biggest and smallest elements touch. Then we can move elements of either parity into this device and swap everything into its correct place.

• What if the biggest and smallest elements have the same parity? Then we could choose the second biggest, third biggest, fourth biggest...

• We could also choose the second smallest, third smallest, and so on.

• So let $$$v$$$ be the smallest value with different parity from the minimum, and let $$$g$$$ be the biggest value with different parity from the maximum.

• We can always swap elements within $$$[\text{minimum}, g]$$$ and within $$$[v, \text{maximum}]$$$. But we cannot swap an element smaller than $$$v$$$ with an element bigger than $$$g$$$, because that would require an element bigger than $$$g$$$ or smaller than $$$v$$$ with the opposite parity.

• So just compare the biggest position of an element smaller than $$$v$$$ and the smallest position of an element bigger than $$$g$$$. If they overlap in the wrong order, then it's impossible; otherwise, it's possible.

Code: My solution

Problem 8: 2066B

• Looks kinda hard, but it's still casework :)))

• Hmm, okay, what if we think about the MEX of the subsequence we pick? If the MEX is $$$0$$$, then we can pick all elements greater than $$$0$$$.

• We cannot choose $$$0$$$ twice, because including $$$0$$$ updates the MEX.

• So the answer must be either the total number of elements greater than $$$0$$$, or that number plus $$$1$$$.

• Then it's a matter of updating the MEX and checking whether taking all the positive elements plus one $$$0$$$ is valid.

Code: My solution

Thank you for reading!