Proof techniques and correctness proof of minimum cost to make string equal

Question

I've lately been struggling to write correctness proofs for various algorithms, even when it is "obvious" to me that the algorithm works and is correct. For example, take the following problem:

Given a binary string $s$ of length $n$, you can perform an invert operation on index $i$ (0-indexed) which inverts the prefix of $s$ from index $0$ to index $i$ inclusive for a cost of $i+1$. What is the minimum total cost needed to make all characters of the string identical (i.e. $s$ will either be the string of all $0$s or the string of all $1$s)?

It is clear (to me) that the optimal way to do this is to simply loop through the array and invert the first $i$ characters to match the next character. But I am not sure how to turn this into a proof of optimality. An arbitrary algorithm could do something crazy, and I'm not sure how to argue that anything crazy is not better than the above algorithm. I'm looking for something rigorous, and not just the proof, but for the thought process leading up to the proof, because I want to be able to solve similar problems and convince myself that my solution is indeed definitely optimal.

Answer 1

Your string has k bit changes where bit i and bit i+1 are different. You reduce the number of bit changes by 1 by inverting the first I+1 bits. So that gives you a way to make all bits equal.

Then you need to prove that as long as you don’t invert the first I+1 bits the bit change from but I to I+1 will remain, so the set of inversions that you found is optimal. Each of those inversions is needed, but you can perform them in any order.

Now imagine a very similar problem that might be lot harder: The cost is not the number of bits changed, but the number of bits changed from 0 to 1. So inverting 0100 has a cost of 3, but inverting 0110 has a cost of two only. The same bit inversions are necessary. Can you reduce the cost by doing some unnecessary inversion twice? What is the difference in cost between doing inversion a then inversion b vs doing inversion b then inversion a?