### hoco's blog

By hoco, 10 years ago,

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?

• +1

 » 10 years ago, # |   +3 Nested DollsYou'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...
•  » » 10 years ago, # ^ |   0 i think your first link has a problem.
•  » » » 10 years ago, # ^ |   0 At least for me it works, its a pdf file...
•  » » » » 10 years ago, # ^ |   0 mine doesn't
•  » » » » » 10 years ago, # ^ | ← Rev. 2 →   0 it's working on my machine well too. I uploaded the file in another host ... maybe it'll help you :)link
•  » » » » » » 10 years ago, # ^ |   +2 tnx
 » 9 years ago, # |   0 Can someone please explain the solution to this problem with an example??
 » 9 years ago, # |   0
•  » » 9 years ago, # ^ |   0 The solution in the editorial is easier. O(NlogK), where K is the length of largest antichain.
•  » » » 9 years ago, # ^ |   0 Can you please tell me in which editorial I will get it. I am stuck with the same problem.
•  » » » » 9 years ago, # ^ |   0 Its the one sparik1997 posted. Check the solution of problem G.
 » 9 years ago, # |   0 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
 » 9 years ago, # | ← Rev. 2 →   +6 It is my solution :Prerequisite : range treeMAXN = 1000 highest value of width and heightT[1000] is array and all elemnt of T is zeroquery(x, 1, MAXN, 1) = find the biggest number which is small or equal to xupd(x, y, 1, MAXN, 1) is T[x] = y;  scanf("%d",&n); for(int h=0; h
•  » » 8 years ago, # ^ |   0 WTF!!!! L
 » 8 years ago, # |   0
 » 8 years ago, # |   0 what is the level of this problem? easy,medium or hard?
•  » » 6 years ago, # ^ | ← Rev. 2 →   -8 it depends, but not easy for a newbie.