proof-545-c.md

I'm trying to solve: https://codeforces.com/contest/545/problem/C. I have a dubious greedy solution: https://codeforces.com/contest/545/submission/120920246 I'm unsure how to write the exchange argument. Here's the sketch I have so far.

It's hopefully clear that it's always optimal to have the first tree lean left and the last tree lean right. So we now have the prove that the construction for trees [1..n-2] is optimal.

Let O* be the optimal solution, O be the solution discovered by the above algorithm. Let index i be the first index where O* and O decide to do something different to a tree. We have i > 0, i < n-2 since we assume that the algorithms agree on the first and last tree.

We have 6 cases (rip?) at index i: the possibilities are L for leaning left, U for standing up, and R for leaning right.

• O*=L, O=U: If there is enough space to lean left, O will choose to lean left. This violates the construction of O.
• O*=L, O=R: Same as above; If there is space to lean left, O will choose to lean left. This violates the construction of O.
• O*=U, O=L: Since O and O* agree upto i and O chooses to lean left, there must be enough space to lean left for O*. This creates a strictly better solution, which violates the optimality of O*.
• O*=U, O=R: [Now what? we can't control O based on O* or vice versa. I don't understand how to handle this case.]
• O*=R, O=L: There must be enough space for O* to lean L. O*=R only limits the space available for the next tree. So we can modify O* to lean left and reach the same optimality.
• O*=R, O=U: If it's possible to lean right, then O will choose to do so. This violates the construction of O.

I find the entire "proof" I've written above dubious. How would one actually prove that the greedy algorithm works?