This blog is for documenting my learning journey in competitive programming, hope someone would enjoy and find it helpful for their learning.↵
Credit to chatgpt and claude to help me find some great 1900 problems (modern problem)↵
Theory:↵
+ I would recommend knowing all usaco.guide gold topics, I think you should be able to know most of them in order to get to cm + some more data structures such as trie, advance segment tree techniques↵
+ To able to understand the blog I would like you to ensure to do all usaco.guide silver topics.↵
↵
Problem 1: https://codeforces.me/problemset/problem/2174/B↵
+ the problem looks like classical dp but the k is pretty high, in normal dp, we could do dp[position][prefix_max][cost] and and for every state run change into k states, total complexity: n * k^3↵
+ However this is obviously going to TLE since amount of operation exceed 2 seconds, so we try to find some observation that going to lead to dp optimization.↵
↵
1. consider the optimal array b, if bi > 0, then it should change the prefix_max into a higher prefix max otherwise it would be unoptimal to put it more bi > 0↵
2. Using the first observation, we could observe that the optimal array b would be increasing (for all value bi > 0), we can consider the contribution of each element to the total sum, bi * (distance to the next element > 0 or the end).↵
+ so we want to maximise the contribution so we should make the larger bi contribute more? so it is optimal for us to put bi more to the left, which mean we could store the first position that could store value i which disconnect the dimension POsition in our dp, thefore allowing dp[prefix_max][cost] that help us AC this problem.↵
code : https://ideone.com/5UW1cs↵
↵
Problem 2: https://codeforces.me/problemset/problem/2138/B↵
+ when the problem looks weird / ad hoc, the only way is casework :)↵
+ INITAL KNOWLEDGE IN ORDER TO SOLVE:↵
- minimum amount of swap to sort a array is the amount of INVERSION in the array because every swap move ai > ai + 1 into ai < ai+1 which reduces the amount of inversion by 1.↵
+ after caseworking we can conlude that there must be a triple where ai > aj > ax (where i < j < x), such that the array would be not perfect, otherwise perfect.↵
+ so when getting that the answer is simple caculate the maximum position i such that there is a triple ending at i, and for every query just segment tree max in range [l-r].↵
code: https://ideone.com/qJyNS8↵
↵
Problem 3: https://codeforces.me/problemset/problem/2217/D↵
+ This problem is really hard for me to figure it out↵
+ but the problem can be change into cutting each value pi in to each segment [pi — p(i+1)-1] and also the ending and first segment.↵
+ consider a change where ai != ai + 1;↵
+ for each segment we can merge change from 1 segment to the other because we can match one segment to the other and it garuntee that 1 pi would be in the middle of the 2 segment (Try drawing it out or imagining it), this would only work if the biggest segment change <= total_amount of change / 2↵
+ Other wise we match as much as possible to the other segment and add the remaining changes in the biggest element.↵
code : https://ideone.com/pOBXb0↵
↵
Problem 4: https://codeforces.me/problemset/problem/2231/D↵
+ This one is general knowledge of prefix sum + A BUNCH OF CASEWORK↵
+ consider all the casework that you need and debugging skill IS THE MAIN SKILL NEEDED in the problem, if you ac all the sample tc then you would ac the tests (probably)↵
+ im not going to dive into details for this problem↵
code : https://ideone.com/qgmWrY↵
↵
Problem 5:https://codeforces.me/problemset/problem/2246/D↵
+ This problems is game theory, usually there is a optimal way for ALICE/BOB to defeat the other one and if you know the optimal way you can find the answer↵
+ the optimal way here for bob is really simple:↵
+ If there exist a odd in array a, he can always swap the odd element to a2 and force a1 to -1 to a0 or /2 to a0 until it turns into 0, which is turns into a bruteforce problem↵
+ so allice should add to some element inorder to reduce amount of move by making all number end in X zeroes, which allow the array to get divide by 2 X times before Bob excute the optimal strategy↵
+ for each X, find cost, but there is a second thing you should debug, what if you could do some operations to ai to reduce cost Even more after dividing by 2 X times to make the number even more, ex : 255 -> 256. so the cost would be adding by (amount_add * 2^x), we know that we can reduce at most by the bit_count of current number which would be around 20 — 30. so just brute.↵
code : https://ideone.com/dkefKz↵
↵
Problem 6: https://codeforces.me/problemset/problem/2133/D↵
+ This problem looks weird at first but its actually still case work, (literally almost every problem)↵
+ so lets say we ignore that fact of the chain damage thing, what would be the optimal answer without the chain damage? obviously cutting the top one first then second then third,... in some order, but the topmost one should be dropped first.↵
+ using that idea when will it be beneficial to use the chain?, it would be beneficial when theres a bunch of ones in front of a number, so when to use chain when to not, that lead us to dp.↵
+ Cases: (we're looping from n -1 -> 0 because it is optimal to throw the topmost one first.)↵
+ case 1: we just kill mob i and then add dp[i+1] to cost;↵
+ case 2: we kill mob i, throwing mob i + 1 down which create a chain reaction that leads to 2 more cases:↵
call first position after i +1 that is > 1: v↵
call cost eliminating both a[i] and a[i+1] : fallcost;↵
- we just take dp[v] and add to cost of eliminating both a[i] and a[i+1] (make it two seperate stack)↵
- we take fallcost + dp[v — 1](making v fall)↵
- fallcost + cost[v] — 1 + remaining cost (adding position v to the chain fall).↵
code: https://ideone.com/RHwYnL↵
↵
Problem 7: https://codeforces.me/problemset/problem/2226/D↵
+ classic adhoc / casework problem :))↵
+ ok so lets do some case work, hmm if I want to sort the array, I should be able to move the smallest one to the left? ↵
+ I can swap adjacent element if they are different in parity↵
+ so then I can make all the even parity go to the left and odd go to the right. ↵
+ ok so then how do I move the element smallest to the left hmm, what if there is a way to create a "reversing device" that aloow me to make the element go in order?↵
+ that allows an insight where if the smallest and biggest element is the different parity, we can use second insight, then you move all the even parity after the biggest one to the rightmost, and all the one to the left of the smallest parity to the leftmost, which make biggest and smallest touch, and then you can move any parity into it and swap everything into its correct place.↵
+ what if the biggest and smallest have the same parity, then we could choose second biggest, third biggest, fourth biggest,...↵
+ we could also choose second smallest, third smallest,.. and so on↵
+ so consider v = smallest position that is differnt parity to the first and find g = the biggest position that have different parity that the biggest element.↵
+ we can always swap element from [smallest — g] and [v — biggest] but we cannot swap an element < v and bigger than > g because then their must be an element bigger than g or smaller than v that is diferent parity than the first one. so then just compare the biggest psition of element before v and smallest position of a number after g, and if they intersect then its impossible and vice versa.↵
code : https://ideone.com/TnlYto↵
↵
problem 8: https://codeforces.me/problemset/problem/2066/B↵
+ looks kinda hard, but its still casework :)))↵
+ hmm ok looks good, what if we assume the mex of the subsequence after array, what if after the array the mex is 0, then we could pick all element > 0.↵
+ we cannot pick 2 of the same element twice after updating mex.↵
+ so we cannot choose 0 twice because it always update mex, so the answer must be either, {total amount of element > 0, total amount of element > 0 + 1} then its updating the mex and verifying if total amount of element > 0 + 1 is good.↵
code: https://ideone.com/wQllGy. 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](https://usaco.guide/gold). 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](https://usaco.guide/silver).↵
↵
## Problem 1: [2174B](https://codeforces.me/problemset/problem/2174/B)↵
↵
+ 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 > 0$, then it should increase the prefix maximum. Otherwise, setting $b_i > 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](https://ideone.com/5UW1cs)↵
↵
## Problem 2: [2138B](https://codeforces.me/problemset/problem/2138/B)↵
↵
+ 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 > a_{i+1}$ into $a_i < 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 > a_j > a_x$, where $i < j < 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](https://ideone.com/qJyNS8)↵
↵
## Problem 3: [2217D](https://codeforces.me/problemset/problem/2217/D)↵
↵
+ 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](https://ideone.com/pOBXb0)↵
↵
## Problem 4: [2231D](https://codeforces.me/problemset/problem/2231/D)↵
↵
+ 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](https://ideone.com/qgmWrY)↵
↵
## Problem 5: [2246D](https://codeforces.me/problemset/problem/2246/D)↵
↵
+ 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](https://ideone.com/dkefKz)↵
↵
## Problem 6: [2133D](https://codeforces.me/problemset/problem/2133/D)↵
↵
+ 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 > 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](https://ideone.com/RHwYnL)↵
↵
## Problem 7: [2226D](https://codeforces.me/problemset/problem/2226/D)↵
↵
+ 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](https://ideone.com/TnlYto)↵
↵
## Problem 8: [2066B](https://codeforces.me/problemset/problem/2066/B)↵
↵
+ 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](https://ideone.com/wQllGy)↵
↵
Thank you for reading!
Credit to chatgpt and claude to help me find some great 1900 problems (modern problem)↵
Theory:↵
+ I would recommend knowing all usaco.guide gold topics, I think you should be able to know most of them in order to get to cm + some more data structures such as trie, advance segment tree techniques↵
+ To able to understand the blog I would like you to ensure to do all usaco.guide silver topics.↵
↵
Problem 1: https://codeforces.me/problemset/problem/2174/B↵
+ the problem looks like classical dp but the k is pretty high, in normal dp, we could do dp[position][prefix_max][cost] and and for every state run change into k states, total complexity: n * k^3↵
+ However this is obviously going to TLE since amount of operation exceed 2 seconds, so we try to find some observation that going to lead to dp optimization.↵
↵
1. consider the optimal array b, if bi > 0, then it should change the prefix_max into a higher prefix max otherwise it would be unoptimal to put it more bi > 0↵
2. Using the first observation, we could observe that the optimal array b would be increasing (for all value bi > 0), we can consider the contribution of each element to the total sum, bi * (distance to the next element > 0 or the end).↵
+ so we want to maximise the contribution so we should make the larger bi contribute more? so it is optimal for us to put bi more to the left, which mean we could store the first position that could store value i which disconnect the dimension POsition in our dp, thefore allowing dp[prefix_max][cost] that help us AC this problem.↵
code : https://ideone.com/5UW1cs↵
↵
Problem 2: https://codeforces.me/problemset/problem/2138/B↵
+ when the problem looks weird / ad hoc, the only way is casework :)↵
+ INITAL KNOWLEDGE IN ORDER TO SOLVE:↵
- minimum amount of swap to sort a array is the amount of INVERSION in the array because every swap move ai > ai + 1 into ai < ai+1 which reduces the amount of inversion by 1.↵
+ after caseworking we can conlude that there must be a triple where ai > aj > ax (where i < j < x), such that the array would be not perfect, otherwise perfect.↵
+ so when getting that the answer is simple caculate the maximum position i such that there is a triple ending at i, and for every query just segment tree max in range [l-r].↵
code: https://ideone.com/qJyNS8↵
↵
Problem 3: https://codeforces.me/problemset/problem/2217/D↵
+ This problem is really hard for me to figure it out↵
+ but the problem can be change into cutting each value pi in to each segment [pi — p(i+1)-1] and also the ending and first segment.↵
+ consider a change where ai != ai + 1;↵
+ for each segment we can merge change from 1 segment to the other because we can match one segment to the other and it garuntee that 1 pi would be in the middle of the 2 segment (Try drawing it out or imagining it), this would only work if the biggest segment change <= total_amount of change / 2↵
+ Other wise we match as much as possible to the other segment and add the remaining changes in the biggest element.↵
code : https://ideone.com/pOBXb0↵
↵
Problem 4: https://codeforces.me/problemset/problem/2231/D↵
+ This one is general knowledge of prefix sum + A BUNCH OF CASEWORK↵
+ consider all the casework that you need and debugging skill IS THE MAIN SKILL NEEDED in the problem, if you ac all the sample tc then you would ac the tests (probably)↵
+ im not going to dive into details for this problem↵
code : https://ideone.com/qgmWrY↵
↵
Problem 5:https://codeforces.me/problemset/problem/2246/D↵
+ This problems is game theory, usually there is a optimal way for ALICE/BOB to defeat the other one and if you know the optimal way you can find the answer↵
+ the optimal way here for bob is really simple:↵
+ If there exist a odd in array a, he can always swap the odd element to a2 and force a1 to -1 to a0 or /2 to a0 until it turns into 0, which is turns into a bruteforce problem↵
+ so allice should add to some element inorder to reduce amount of move by making all number end in X zeroes, which allow the array to get divide by 2 X times before Bob excute the optimal strategy↵
+ for each X, find cost, but there is a second thing you should debug, what if you could do some operations to ai to reduce cost Even more after dividing by 2 X times to make the number even more, ex : 255 -> 256. so the cost would be adding by (amount_add * 2^x), we know that we can reduce at most by the bit_count of current number which would be around 20 — 30. so just brute.↵
code : https://ideone.com/dkefKz↵
↵
Problem 6: https://codeforces.me/problemset/problem/2133/D↵
+ This problem looks weird at first but its actually still case work, (literally almost every problem)↵
+ so lets say we ignore that fact of the chain damage thing, what would be the optimal answer without the chain damage? obviously cutting the top one first then second then third,... in some order, but the topmost one should be dropped first.↵
+ using that idea when will it be beneficial to use the chain?, it would be beneficial when theres a bunch of ones in front of a number, so when to use chain when to not, that lead us to dp.↵
+ Cases: (we're looping from n -1 -> 0 because it is optimal to throw the topmost one first.)↵
+ case 1: we just kill mob i and then add dp[i+1] to cost;↵
+ case 2: we kill mob i, throwing mob i + 1 down which create a chain reaction that leads to 2 more cases:↵
call first position after i +1 that is > 1: v↵
call cost eliminating both a[i] and a[i+1] : fallcost;↵
- we just take dp[v] and add to cost of eliminating both a[i] and a[i+1] (make it two seperate stack)↵
- we take fallcost + dp[v — 1](making v fall)↵
- fallcost + cost[v] — 1 + remaining cost (adding position v to the chain fall).↵
code: https://ideone.com/RHwYnL↵
↵
Problem 7: https://codeforces.me/problemset/problem/2226/D↵
+ classic adhoc / casework problem :))↵
+ ok so lets do some case work, hmm if I want to sort the array, I should be able to move the smallest one to the left? ↵
+ I can swap adjacent element if they are different in parity↵
+ so then I can make all the even parity go to the left and odd go to the right. ↵
+ ok so then how do I move the element smallest to the left hmm, what if there is a way to create a "reversing device" that aloow me to make the element go in order?↵
+ that allows an insight where if the smallest and biggest element is the different parity, we can use second insight, then you move all the even parity after the biggest one to the rightmost, and all the one to the left of the smallest parity to the leftmost, which make biggest and smallest touch, and then you can move any parity into it and swap everything into its correct place.↵
+ what if the biggest and smallest have the same parity, then we could choose second biggest, third biggest, fourth biggest,...↵
+ we could also choose second smallest, third smallest,.. and so on↵
+ so consider v = smallest position that is differnt parity to the first and find g = the biggest position that have different parity that the biggest element.↵
+ we can always swap element from [smallest — g] and [v — biggest] but we cannot swap an element < v and bigger than > g because then their must be an element bigger than g or smaller than v that is diferent parity than the first one. so then just compare the biggest psition of element before v and smallest position of a number after g, and if they intersect then its impossible and vice versa.↵
code : https://ideone.com/TnlYto↵
↵
problem 8: https://codeforces.me/problemset/problem/2066/B↵
+ looks kinda hard, but its still casework :)))↵
+ hmm ok looks good, what if we assume the mex of the subsequence after array, what if after the array the mex is 0, then we could pick all element > 0.↵
+ we cannot pick 2 of the same element twice after updating mex.↵
+ so we cannot choose 0 twice because it always update mex, so the answer must be either, {total amount of element > 0, total amount of element > 0 + 1} then its updating the mex and verifying if total amount of element > 0 + 1 is good.↵
code: https://ideone.com/wQllGy
↵
Credit to ChatGPT and Claude for helping me find some great modern 1900 problems.↵
↵
## Theory↵
↵
+ I would recommend knowing all [USACO Guide Gold topics](https://usaco.guide/gold). 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](https://usaco.guide/silver).↵
↵
## Problem 1: [2174B](https://codeforces.me/problemset/problem/2174/B)↵
↵
+ 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 > 0$, then it should increase the prefix maximum. Otherwise, setting $b_i > 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](https://ideone.com/5UW1cs)↵
↵
## Problem 2: [2138B](https://codeforces.me/problemset/problem/2138/B)↵
↵
+ 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 > a_{i+1}$ into $a_i < 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 > a_j > a_x$, where $i < j < 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](https://ideone.com/qJyNS8)↵
↵
## Problem 3: [2217D](https://codeforces.me/problemset/problem/2217/D)↵
↵
+ 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](https://ideone.com/pOBXb0)↵
↵
## Problem 4: [2231D](https://codeforces.me/problemset/problem/2231/D)↵
↵
+ 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](https://ideone.com/qgmWrY)↵
↵
## Problem 5: [2246D](https://codeforces.me/problemset/problem/2246/D)↵
↵
+ 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](https://ideone.com/dkefKz)↵
↵
## Problem 6: [2133D](https://codeforces.me/problemset/problem/2133/D)↵
↵
+ 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 > 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](https://ideone.com/RHwYnL)↵
↵
## Problem 7: [2226D](https://codeforces.me/problemset/problem/2226/D)↵
↵
+ 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](https://ideone.com/TnlYto)↵
↵
## Problem 8: [2066B](https://codeforces.me/problemset/problem/2066/B)↵
↵
+ 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](https://ideone.com/wQllGy)↵
↵
Thank you for reading!
