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 | 3757 |

2 | jiangly | 3590 |

3 | ksun48 | 3582 |

4 | Um_nik | 3539 |

5 | maroonrk | 3533 |

6 | slime | 3498 |

7 | djq_cpp | 3486 |

8 | Radewoosh | 3442 |

9 | cnnfls_csy | 3427 |

10 | ko_osaga | 3355 |

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

1 | -is-this-fft- | 185 |

2 | awoo | 181 |

3 | dario2994 | 171 |

4 | SecondThread | 169 |

4 | maroonrk | 169 |

4 | Um_nik | 169 |

7 | adamant | 167 |

8 | YouKn0wWho | 165 |

8 | errorgorn | 165 |

10 | antontrygubO_o | 162 |

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?

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/03/2022 01:11:59 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

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

Can someone please explain the solution to this problem with an example??

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

what is the level of this problem? easy,medium or hard?

it depends, but not easy for a newbie.