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