ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1965. Pear Trees

Hint
Posted by pmartynov 17 Jan 2014 17:06
I spent a lot of time on this problem.
For those who want to fit the time limit I recommend reading A. Brandstƒadt, D. Kratsch "On partitions of permutations into increasing and decreasing subsequences".
Also M.D. Atkinson "Permutations which are the union of an increasing and a decreasing subsequence" is very interesting to read but not so helpful for this particular problem.
Re: Hint
Posted by Harkonnen 14 Aug 2022 08:18
My algo is O(N) DP which does not rely on input array being a permutation. Input can be anything - even floats or strings and may have repeating elements. Moreover, it's "online" DP, so if you don't need detailed result (just 'Possible' or 'Fail') it can be coded in O(1) memory.