Olympiad challenge?

Question

Algorithms

The boy Petya decided to prepare a birthday present for his mother - a holiday breakfast. He decided to make delicious tea and bake pancakes. Unfortunately, not having outstanding culinary skills, Petya couldn't keep up with the pancakes. Each of them turned out to be burnt on one side and undercooked on the other. As a result, Petya got N black-and-white pancakes. He laid all the pancakes on a large plate on top of each other. Now Petya wants to turn them over so that they all lie with the light side up - Petya thinks that mom will like them better this way. To turn the pancakes, he has a spatula, with which he can take several top pancakes (from one to the whole stack) and turn them all together (in such a way that the top pancake is in place of the bottom of the taken pancakes).
What is the minimum number of such actions that Petya needs to turn all pancakes with the bright side up?

Answer 1

Let's write down the sequence of pancakes with the numbers 0 (light side up) and 1 (dark side up). Let's call an inversion a transition from 1 to 0 or from 0 to 1. One stack flip can add or subtract a maximum of one inversion on the border between the flipped and non-flipped parts (all inversions inside the flipped part are preserved, only change sign). Therefore, the minimum number of flips to eliminate all inversions is equal to the number of inversions in the original stack of pancakes. If the first pancake lies with the dark side up, another flip of the entire stack will be required to solve the problem.

Answer 2

DEFINITION. Mess - a) black pancake at the bottom; b) white pancake on black, black on white.
THEOREM. A flip fixes at most one disorder.
PROOF. Neither in the overturned stack, nor in the remaining one, as there was a mess, it remains so. We have a chance to fix one mess - the one we shoveled into.
CONSEQUENCE. The bottom estimate is the number of disturbances.
THEOREM. This limit is achievable.
INDUCTION BASE. We have 0 disturbances. All pancakes are white - you really need 0 moves.
STEP INDUCTION. It is proved that the boundary is reachable for 0…N−1 disturbances. Now let there be N disturbances.
If the number of unrest is odd, there will be a black pancake at the top. Turn over the entire stack, except for the bottom white pancakes. We lose one disorder in one move, and for N−1 the boundary is reachable.
If the number of riots is even, there is a white pancake at the top. Since there are not 0 unrest, the white pancakes lie on the black ones. Let's turn the white group over (losing one mess) and get a black pancake at the top. We lose one disorder in one move, and for N−1 the boundary is reachable.
ALGORITHM. Count the number of riots in the stack, output it. O(N).

Answer 3

Obviously, the maximum number of flips will be if the pancakes lie to each other on the same sides (white to white, black to black). In this case, to order, you need to do N-1 flips.
The number of flips increases by 1 (because at the end it turns out that the entire stack is black side up) if:
1. N is not even and the first pancake is black at the beginning
2. N is even and the first pancake is white
Total, the maximum number of flips is: N