0
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Great explanation. Is there a process that let you to the above approach? Like I'm curious what the thought process was that led you to consider differences between adjacent bits. I wouldn't have thought of it, but I want to know what could lead someone else to think of it. $\endgroup$
    – user308485
    May 28, 2023 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.