I prepared a problem similar to 851D - Arpa and a list of numbers 2 months ago and now I want share it with you :)

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 211 |

2 | awoo | 188 |

3 | rng_58 | 185 |

3 | Errichto | 185 |

5 | SecondThread | 182 |

6 | Ashishgup | 175 |

6 | Um_nik | 175 |

8 | maroonrk | 174 |

9 | antontrygubO_o | 170 |

10 | -is-this-fft- | 169 |

I saw MDOLLS problem in this list was in LIS part and I was wondered how it can solved using LIS?

The question is:

Dilworth is the world's most prominent collector of Russian nested dolls: he literally has thousands of them! You know, the wooden hollow dolls of different sizes of which the smallest doll is contained in the second smallest, and this doll is in turn contained in the next one and so forth. One day he wonders if there is another way of nesting them so he will end up with fewer nested dolls? After all, that would make his collection even more magnificent! He unpacks each nested doll and measures the width and height of each contained doll. A doll with width w1 and height h1 will fit in another doll of width w2 and height h= if and only if w1 < w2 and h1 < h2. Can you help him calculate the smallest number of nested dolls possible to assemble from his massive list of measurements?

I know this problem can be solved by maximum bipartite matching tecnique but I want to know is there any way to solve using LIS?

If we have `w1 <= w2`

and `h1 <= h2`

instead of `w1 < w2`

and `h1 < h2`

I have an *O*(*n*^{2}*logn*) solution using LIS as follow:

Initially we sort dolls by their `w`

values (and `h`

In the next priority) and then try to remove LIS from new order of dolls. number of times we can remove LIS from our dolls is the answer.

But it's obvious that my solution shouldn't work for original version of MDOLLS with `w1 < w2`

and `h1 < h2`

conditions.

Please help me to know is there a solution using LIS for MDOLLS?

I found russian version of acm.sgu

russian version: http://acm.sgu.ru/olimp/

now, we can use web cache tools for reading problems and use russian version for judge submissions but I cannot understand why they deleted English version :(

**UPD:** it's not russian version of acm.sgu.ru :( it's just a judge with similar visual theme and I was deceived.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/18/2021 04:46:42 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|