hi everybody, about this problem + if any body solved it, plz share his code.
My algorithm is to use LIS and see how many distinct "Increasing sequences" there is. but I think it's hard to code. does any body have any easier algorithm?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
hi everybody, about this problem + if any body solved it, plz share his code.
My algorithm is to use LIS and see how many distinct "Increasing sequences" there is. but I think it's hard to code. does any body have any easier algorithm?
Name |
---|
Nested Dolls
You're gonna need to take a look here Online Algorithms for Dilworth's Chain Partition and here Dilworth's theorem, and I think you will get it...
i think your first link has a problem.
At least for me it works, its a pdf file...
mine doesn't
it's working on my machine well too. I uploaded the file in another host ... maybe it'll help you :)
link
tnx
http://ncpc.idi.ntnu.no/ncpc2007/ncpc2007solutions.pdf
The solution in the editorial is easier. O(NlogK), where K is the length of largest antichain.
Can you please tell me in which editorial I will get it. I am stuck with the same problem.
Its the one sparik1997 posted. Check the solution of problem G.
Find The Longest Decreasing Subsequence But keep in mind that you can take 2 equal values like 3 3 2 2 1 1 is a valid decreasing subsequence
It is my solution :
Prerequisite : range tree
MAXN = 1000 highest value of width and height
T[1000] is array and all elemnt of T is zero
query(x, 1, MAXN, 1) = find the biggest number which is small or equal to x
upd(x, y, 1, MAXN, 1) is T[x] = y;
WTF!!!! L
my greedy approach