Hi CF ! Long time , no see. I have an interesting problem for you.

## Statement

*N* dwarfs fell into a pit with depth of *D* cm. For every dwarf you know the height to the shoulders ( i.e. the distance from the ground to the shoulders ) and the arms length. The dwarfs try to escape from the pit , so they climb one on each other and get out of the pit.

Every dwarfs stands on the shoulders of other. If one dwarf reaches the top of the pit , he can get out of the pit. We denote the shoulder height of the *i* - *th* dwarf with *h*_{i} and the arms length with *l*_{i}. A tower formed from *k* dwarfs *j*_{1}, *j*_{2}, ..., *j*_{k} has the height *h*_{j}_{1} + *h*_{j}_{2} + ... + *h*_{j}_{k} . The dwarf *h*_{j}_{k} can get out of the pit if *h*_{j}_{1} + *h*_{j}_{2} + ... + *h*_{j}_{k} + *l*_{j}_{k} ≥ *D*. A tower can be formed in any possible way.

Your task is to determine how many dwarfs can get out of the pit. (1 ≤ *N* ≤ 2000)

## Solution

Let's start with a simpler problem. Supose the length of the hands does not matter. ( i.e. *j*_{k} - *th* dwarf can get out if *h*_{j}_{1} + *h*_{j}_{2} + ... + *h*_{j}_{k} ≥ *D* ) In this case we can sort the dwarfs decrasingly by *h*_{i} and get out as many short dwarfs as possbile.

Note that a similar stategy would not work in our problem. An example would be *N* = 3 , *D* = 5 with ( *h*_{1} = 1 , *l*_{1} = 4 ) , ( *h*_{2} = 2 , *l*_{2} = 0 ) , ( *h*_{3} = 2 , *l*_{3} = 0 ).

With the previous strategy we would have the tower 2, 3, 1 and the dwarf 1 would be saved. But if the tower is 3, 1, 2 both 1 and 2 dwarfs can be saved.

We can conclude that a small dwarf with long hands can be placed closer to the base of the tower than other dwarfs. The order in wich the dwarfs will get out of the pit would rather be determined by the sum *h*_{i} + *l*_{i}. Also we need not to forget that a heigher dwarf ( with *h*_{i} bigger ) is more useful for the others than a small one.

Now , imagine we have already pulled out the optimum set of dwarfs. Let's now find how they came out. We can iterate through them and select the ones which we can put inside the hole and they still can get out. We will repeat that operation until all of them are in the hole.

From this reverse kind of thinking you got the idea that selecting a set of dwarfs who get out is a good one. We will sort the dwarfs decreasingly after *h*_{i} ( in case of equalty after *l*_{i} ). If all the dwarfs from some set of dwarfs can get out we need to choose the last wich can get out , than he can be added to the tower.

We keep a vector in wich we will mark if some dwarf is in the set of the ones witch can get out. At each step we will try to add the dwarf with the maximum *h*_{i} into the set.

```
for (int i=1;i<=N;++i)
{
int dwarf = oH[i]; // oH - order after height decreasingly
if ( good(dwarf) )
{
mark[ rev[dwarf] ] = 1; // put the dwarf in the set
// mark - the marking vector
// rev - the order in the original vector
h_init -= h[dwarf]; // h_init - the height of the tower
co++; // new dwarf added
}
else
mark[ rev[dwarf] ] = 0; // the dwarf is outside the set
}
```

Now we have to verify is we can add a dwarf in the set. For this we design a function wich says if a set of dwarfs is good or not. The last dwarf from the set wich will get out is the one with maximum *h*_{i} + *l*_{i}. Then we can get it out of the set and repeat the process. Of course , we do not need sorting because we can precompute the vector *oHL* ( order after *h*_{i} + *l*_{i} decreasingly ).

```
bool good(int dwarf)
{
int h_now = h_init - H[dwarf]; // h_now - acutal tower height
l[ rev[dwarf] ] = 1; // mark the dwarf
for (int i=N;i>=0;--i)
if ( l[i] == 1 )
{
if ( h_now + H[oHL[i]] + L[oHL[i]] >= D )
h_now += H[oHL[i]]; // if the dwarf can get out we put it in the tower
else
return 0; // else we have the guaranty that the actual set can't get out
}
return 1;
}
```

We verify in *O*(*N*) the introduction of some dwarf and we try to add every dwarf once. The final complexity is *O*(*N*^{2}). Here is my source.

BONUS: The problem can be also solved by DP. Take a look. ;)

This problem was given at Russian Olympiad in Informatics in 2006.)

I can solve this problem in O(nlogn) by converting this problem to another.

Dual Problem is about deadlines, we have

ntasks with deadlined_{i}, and takest_{i}minutes to complete the task. We need to complete maximum tasks.so, Let's think that we complete tasks in order 1, 2, ...

n, then for everyimust hold ≤d_{i}.In our problem, +

l_{i}>=D.≤

l_{i}-D.Let's denote S as

equals

So it is the same task as deadline, with

t_{i}=h_{i}, andd_{i}=l_{i}-D+S+h_{i}.And deadline task can be solved in O(nlogn) time.

Very nice solution. Thanks a lot !

This problem has NlogN version e-olimp

Sort all items by non-decreasing of

h_{i}+l_{i}.Lest

s— all dwarfs, which will get out. Initiallysis empty. If the dwarf with the lowesth_{i}+l_{i}can get out, let add it tos. Else, try to exchange it with the dwarf ins, whoseh_{i}is maximal possible.