Sometimes I construct a solution, than I prove the solution is the best by proving it's not possible to get a better solution by modifying my solution by one step. (wow, a lot "by"s, forgive me XD)
For example The tutorial also use this method to prove.
The proof BASES ON the solution.
What if we modify more? From the second step on we cannot prove it anymore because the state before is not the solution.
That is to say :
We have solution1. We can change it to solution2,3 by one step and we know they are not better. We can change solution2 to solution4,5, and change solution4 to solution6,7,8, ans so on. The proof base on solution1, so, wo cannot know wether solution4 is not better than solution2, which means we cannot say that solution4 is not better than solution1.
We can only say that solutions near solution1 is not better than it. So maybe it's loose to say solution1 is the best.
The problem in Hello 2024 is clear because I make some asumption to prove. But this time I failed :(
For 1918B - Минимизируйте инверсии we can prove it as follows:
Suppose we have some solution with $$$k$$$ inversions, but $$$a$$$ isn't sorted. Since $$$a$$$ isn't sorted, we can find some $$$1\le i<n$$$ such that $$$a_i > a_{i+1}$$$. Let's swap $$$a_i$$$ with $$$a_{i+1}$$$ and $$$b_i$$$ with $$$b_{i+1}$$$. Since $$$a_i > a_{i+1}$$$ before the operation, the number of inversions in $$$a$$$ decreases by one. Depending on if $$$b_i < b_{i+1}$$$ or $$$b_i > b{i+1}$$$, the number of inversions in $$$b$$$ either increases by one or decreases by one. Thus, the total number of inversions after the operation is either $$$k$$$ or $$$k-2$$$. That is, the total number of inversions either stays constant or decreases. This also means that after multiple such operations, the total number of inversions is either the same as in the beginning or lower.
On each operation the number of inversions in $$$a$$$ decreases by one. Since the number of inversions in $$$a$$$ is finite, we will at some point reach the state where $$$a$$$ has zero inversions, i.e. $$$a$$$ is sorted. This final state will have at most $$$k$$$ total inversions, which we proved above. But the first state could've been any state! This means that the state where $$$a$$$ is sorted has at most as many total inversions as any other state. This is the same as saying that the state where $$$a$$$ is sorted has the minimal number of total inversions. $$$\square$$$
Thanks a lot, now i understand. <3