i wish that anyone explains to me in simple way the algorithm of the Longest Increasing Subsequence in O(nlogn) time , cuz i actually read all online articles about it and found no one explain it well , thanks in advance :)

Before contest

2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

31:57:03

Register now »

2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

31:57:03

Register now »

*has extra registration

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

1 | Um_nik | 3459 |

2 | tourist | 3438 |

3 | maroonrk | 3359 |

4 | ecnerwala | 3347 |

5 | Benq | 3317 |

6 | ksun48 | 3309 |

7 | boboniu | 3300 |

8 | Petr | 3293 |

9 | Radewoosh | 3289 |

10 | TLE | 3223 |

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

1 | Errichto | 206 |

2 | Monogon | 196 |

3 | SecondThread | 191 |

4 | pikmike | 187 |

5 | antontrygubO_o | 186 |

6 | vovuh | 183 |

6 | Um_nik | 183 |

8 | Ashishgup | 182 |

9 | Radewoosh | 169 |

10 | pashka | 168 |

i wish that anyone explains to me in simple way the algorithm of the Longest Increasing Subsequence in O(nlogn) time , cuz i actually read all online articles about it and found no one explain it well , thanks in advance :)

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/26/2020 00:02:58 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

i learned LIS from here. it's pretty good :)

thanks buddy :)

the trick for the nlogn solution is to maintain, in addition to your dp table, an auxiliary table A so that A[ i ] holds the information "what is the minimum number in the array, such that an increasing subsequence of length i terminates at", it is easy to see that this array will be strictly increasing. Therefore, we can simply binary search the solution of every subproblem and update our array.

i got this thanks :)

I think we can also use AVL tree instead of the auxiliary table.

It is also worth mentioning that you can do LIS in O(n log n) time simply by improving the O(n^2) DP. Everything you need is coordinate compression and a Fenwick tree / interval tree. The code is longer than with the bsearching algorithm, but for many people the idea is simpler because it uses tools they already know.

I think it can be done without coordinate compression by processing in increasing order of value and using a segment tree in O(n log n).

Edit: sorry for necroposting, didn't realise this blog was from 5 years ago.

hahahahah

Those slides will help you to understand the algorithm idea. https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf

this explanation pretty good 10 / 10

Interesting!

Yes there is

Set implementationLIS1 LIS2

Well yeah,there are a lot of articles and finally I found a video which explains the NlogN algorithm with an example step by step and the actual idea/logic behind it.You can refer it : https://youtu.be/nf3YG4CnTbg