I got the following problem: create a list containing exactly a zeros, b ones, c twos and d threes, where the absolute difference between two consecutivo numbers is exactly one. For seeing the original problem take a look here https://codeforces.com/contest/1265/problem/D.
The solution(and proof) provided by the authors is:
Firstly, let's arrange even numbers. It is optimal to arrange those numbers as 0,0,0,…,0,2,2,…2. Because we can place number 1 anywhere while number 3 only between two numbers 2 or at the end beside a number 2. So we need to maximize the number of positions where we can place number 3. The above gives us an optimal way. The next step is to place the remaining numbers 1,3. Inserting them in internal positions first then at the ends later.
However I don't feel like this proof is enough for me. For example, It is optimal to arrange those numbers, there is no proof for that or I'm missing something.
Can someone please provide another proof or helping me to understand better this one. Thanks in advance.