Problem 5: Log Land

https://open.kattis.com/problems/logland

To approach this problem, we need to notice two important insights:

1. It's unfavorable to leave big denominations behind.

2. If any large denomination cannot be paired up, we can try to match it up with smaller denominations.

For example, if we have cash of the following values:

$$1, 1, 1, 1, 4$$

Instead of taking all the 1-dollar bills and leave the 4-dollar bill behind, we can take away everything, as the 4 1-dollar bills add up to 4 dollars. In the following editorial, we'll call this operation "merging".

Now the question becomes:

How do we know when we want to merge the smaller denominations?

The answer to that question is: why don't we merge all of them and worry later?

Let's take a look at an example:

$$1, 2, 2, 2, 2, 2, 4$$

We start from the smallest denomination, 1. As there is only one 1-dollar bill, we can't possibly split it or merge it, so we have to leave it behind.

Now we are left with the following cash to be dealt with:

$$2, 2, 2, 2, 2, 4$$

Now let's consider the 2 dollar denomination. We can merge 4 2-dollar bills into 2 4-dollar bills. There's 1 2-dollar bill that we cannot pair up, so unfortunately, we have to it behind.

Finally, we need to think about the 4 dollar bills. We have the following cash sitting in front of us:

$$4, 4, 4$$

First and foremost, we take away the pair of 4-dollar bills. That leaves us a single 4-dollar bill. It seems like we have to leave the 4 dollar bill behind now. However, remember that 2 of the 4-dollar bills are actually merged by 2-dollar bills. So, it's actually split-able! We don't have to leave any money behind this time!

Note that by taking this approach, we only leave money behind when it's absolutely impossible to split. Moreover, by not taking away the smaller denominations too early, but rather merging them into larger ones, we make sure that at any step, we have all the "pairing power" we can possibly get, thereby minimizing the loss of larger denominations.

Implementation Tips:

1. Keep a count of each denomination in an array so that arr[i] is the number $2^i$-dollar bills in the vault.

2. To determine whether we can split the last single cash, we need to store a boolean variable that tells us whether we have merged any smaller denominations to the current denomination in the previous step. If true, then we know that we can split it. Otherwise, we have to leave it behind.