LIS O(nlogn) - Codeforces

→ Обратите внимание

До соревнования
Codeforces Round 941 (Div. 1)
22:54:34
Зарегистрироваться »

*есть доп. регистрация

До соревнования
Codeforces Round 941 (Div. 2)
22:54:34
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Atcoder ABC #351 Short Solution Discussion

aryanc403

До начала 21:59:34

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя madcannibal

LIS O(nlogn)

Автор madcannibal, история, 9 лет назад, По-английски

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 :)

-1

madcannibal
9 лет назад
35

Комментарии (16)

Показать архивные | Написать комментарий?

2360

9 лет назад, # |

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

→ Ответить

Apiram

3 года назад, # ^ |

-7

Is this possible to do binarysearch in an unsorted array?

→ Ответить

holden

9 лет назад, # |

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.

→ Ответить

misof

9 лет назад, # |

+11

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.

→ Ответить

shenxy13

4 года назад, # ^ |

← Rev. 2 →

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.

→ Ответить

SPyofgame

4 года назад, # |

← Rev. 3 →

Yes there is

Set implementation

#define itr iterator
...
typedef set<int> si;
...
si S;
for (int x : a) {
    S.insert(x);
    si::itr it = S.upper_bound(x);
    if(it != S.end()) S.erase(it);
}
/// LIS length = S.size();

→ Ответить

Elegy_No_Programmer

4 года назад, # ^ |

But how to retain the LIS? This is fine for calculating its length. But what about the LIS itself?

→ Ответить

TwentyOneHundredOrBust

4 года назад, # ^ |

It's not possible with the set method, just use segment tree.

→ Ответить

Elegy_No_Programmer

4 года назад, # ^ |

Could you tell me how to retain LIS(sequence itself not the length) using segment trees?

→ Ответить

TwentyOneHundredOrBust

4 года назад, # ^ |

Do the DP and find longest sequence with end value less than current value at index below us, augment the segment tree to return both max and index, then just step back the indices.

→ Ответить

Rezwan.Arefin01

4 года назад, # ^ |

It is possible with set. At each $$$i$$$, you should store the previous element's index in the LIS that contains $$$a_i$$$. For details see this comment.

→ Ответить

SPyofgame

3 года назад, # ^ |

Here it is

vector with binary search and finding LIS offline

const int INF = 1e9;
int lis(const vector<int> &a)
{
    int n = a.size();
    vector<int> f(n), b(n);

    /// F[i] is binary search position
    /// B[i] is unordered LIS
    int res = 0;
    for (int i = 0; i < n; ++i) {
        b[i] = +INF;
        f[i] = lower_bound(b.begin(), b.begin() + res + 1, a[i]) - b.begin();
        res = max(res, f[i] + 1);
        b[f[i]] = a[i];          
    }
    /// res is the size of LIS

    vector<int> LIS; /// Finding real LIS
    while (n--)
    {
       if (f[n] == res)
       {
            LIS.emplace_back(a[n]);
            --res;
       }
    }

    reverse(all(LIS);
    return LIS.size();
}

→ Ответить

TimeTraveler

3 года назад, # ^ |

It does not work if there are duplicates in a. e.g a = [1, 2, 3, 4, 1] It will give 3 but correct ans is 4

→ Ответить

SPyofgame

3 года назад, # ^ |

Yes it is, sorry for not writting the notice

Nondecreasing Longest Subsequence - With unique

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int &x : a) cin >> x;
    
    set<int> S;
    set<int>::iterator it;
    for (int x : a)
    {
        S.insert(x);
        it = S.upper_bound(x);
        if (it != S.end()) S.erase(x);
    }
    
    cout << S.size();
    return 0;
}

Nondecreasing Longest Subsequence - With duplicates

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int &x : a) cin >> x;
    
    multiset<int> S;
    multiset<int>::iterator it;
    for (int x : a)
    {
        S.insert(x);
        it = S.upper_bound(x);
        if (it != S.end()) S.erase(it);
    }
    
    cout << S.size();
    return 0;
}

Strict Increasing Longest Subsequence

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int &x : a) cin >> x;
    
    set<int> S;
    set<int>::iterator it;
    for (int x : a)
    {
        S.insert(x);
        it = S.upper_bound(x);
        if (it != S.end()) S.erase(it);
    }
    
    cout << S.size();
    return 0;
}

→ Ответить

TimeTraveler

3 года назад, # ^ |

Found this Implementation with vector

→ Ответить

calmachint

4 года назад, # |

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

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 26.04.2024 18:40:26 (g1).

Десктопная версия, переключиться на мобильную.

При поддержке