This challenge is inspired by a thread in the C board that was lost during the forum reset. It's complexity lies in finding the correct algorithm, the implementation is trivial.

I also added a second question, one that wasn't part of the thread in the C forum, which is pretty hard to answer.

I can give a small hint for the second question, it involves graphs...Code:Two stone age men have gathered an impressive collection of boulders in their cave, all of different size and weight, standing neatly one after the other, in the order they have been collected. To restore some order in the room, they want to arrange the boulders from the smallest to the largest, with the smallest at the entrance of the cave and the largest close to the back wall. Each boulder is only represented by its weight, so the heavier it is, the largest it is (we assume that they are all made of the same material). As there are only 2 stone age men, and the space inside the cave is limited, they are only allowed to swap two boulders at a time. Additionally, to save their energy, they want to use a method that allows them to move the minimum necessary weight only. 1. Write an algorithm that takes an array of boulders and orders it from the smallest to the largest, by only swapping two boulders at a time but with the least effort in terms of kilos moved. Example: {5, 3, 1} -> {1, 3, 5} and necessary effort: 1+5 = 6 {6, 4, 1, 2} -> {6, 1, 4, 2}, effort 5 -> {6, 2, 4, 1}, effort 3 -> {1, 2, 4, 6}, effort 7 total effort: 15 2. Prove that your solution is optimal.