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.
- 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
- 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
