Day 20 | Phoenix and Towers | C++

This is a good greedy problem. This problem asks us to place N blocks in M towers such that no two blocks have a height difference greater than x.

I will be honest with you the solution did not strike me without looking at the editorial. But I thought it to be a good experience to learn about greedy, sets, and pairs and also explain the editorial with more details.

Understanding the approach and it's reason

The solution approach is quite simple, we add the next block to the tower of the smallest current height.

But you must have some problems here.

1. How do you think of this solution by yourself in contests?

2. How to think of the proof yourself?

3. It is a little difficult to prove that it is the correct solution.

For the first two problems reply is the same, the more you practice the more you will get hang of thinking about greedy solutions and also how to prove them correct/incorrect.

By solving 11 more problems on greedy, you will be better from what skills you have now.

By solving 21 more problems you will become better than what you would have become after solving 11 more.

And so on

Keep practicing

Let's prove the solution

Now we know a few things

• There is no block of height > x

• We are adding to the smallest block

Now let's assume that after adding to the smallest tower, its height difference from some towers will become more than x

We are saying that this is not possible, hence if we keep doing this we can assign blocks to towers.

But why is that impossible?

Consider that currently, towers were of the height: h[0],h[1],...,h[m-1] (Sorted order)

We add a block of height B to the smallest tower

Now its height will be h[0] + B

let's say that for some i (i != 0),

(h[0] + B) - h[i] > x

h[0] - h[i] > x - B

How not that h[0] is smallest element, thus h[0] - h[i] <= 0

but blocks are no longer than x

thus x-B >= 0

therefore h[0] - h[i] > x - B can never be possible

How to implement the solution

There are two containers in C++ STL - set and pair which are very useful in implementing this solution

In brief,

a set is a data structure that keeps the data sorted and insertion and deletion happen in log(n) time complexity

a pair is a data structure to hold two values together

We will make a set of pairs.

Pairs will hold the height of a tower as the first value and the index of the tower as the second value

Note: In pair, comparison happens like this, first values are compared, if they differ, the then smaller first value is smaller pair, otherwise if first values are equal then the smaller second value is smaller

Example1: {10,15} > {9,16}

Example2: {10,15} < {10,16}

Since we have pair as {height, index} of the tower, the smallest pair in a set will have the smallest height, exactly what we needed.

Now we implement it like this

• Then we can pick the first element from the set

• Assign block to the tower

• Delete tower from the set

• Insert tower again with new height

Here is the C++ code | My submitted implementation

    int n,m,x;
    cin >> n >> m >> x;
    set<pair<int,int>> s;
    vector<int> blocks(n);
    for(int i = 0; i < n; i++)cin >> blocks[i];
    for(int i = 0; i < m; i++)s.insert(make_pair(0,i + 1));
    cout << "YES\n";
    for(int i = 0; i < n; i++){
        auto smallest = s.begin();
        int index = smallest->second;
        int value = smallest->first;
        cout << index << " ";
        s.erase(s.begin());
        // You can also make pair like this {first, second}
        s.insert({value + blocks[i], index});
    }
    cout << "\n";