|
|
Show all threads Hide all threads Show all messages Hide all messages | For who get WA#26 or WA#30 | hyman00 | 1965. Pear Trees | 2 Jul 2023 13:53 | 1 | Try the test 8 1 7 4 6 3 5 2 8 and 8 8 2 5 3 6 4 7 1 . Both tests have solutions. | Hint | pmartynov | 1965. Pear Trees | 14 Aug 2022 08:18 | 2 | Hint 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. 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. | IF WA 4 | zwqzwq | 1965. Pear Trees | 25 Aug 2021 13:58 | 1 | 5 1 2 3 4 5 shold be 4 1 1 2 3 4 5 (or others) but can't be 5 0 1 2 3 4 5 | hints | Abid29 | 1965. Pear Trees | 13 Apr 2021 18:18 | 2 | hints Abid29 13 Apr 2021 18:16 its a greedy+dp according to me you should analyze the four scenario like 1. two increasing sequence :
take two array . two array initially have only one value zero. then iterate over 2nd to nth element. if element > 1st and 2nd arrays last element then, 1st sequence last element > 2nd arrays last element then: (add element to the 1st array) otherwise (add element to the 1st array) otherwise add it to the array whose last element < element
(this is optimal ). 2. two decreasing sequence: approach greedily like 1st one 3. one increasing and one decreasing(1st element included in the increasing array):(try yourself) 4. one increasing and one decreasing(1st element included in the decreasing array):(try yourself) for 3rd and 4th criteria , think greedily also. my solution is 0.14sec if you are better plz email me s-2017915104@isrt.du.ac.bd | Problem 1965. Pear Trees has been rejudged | Kurpilyansky Eugene (USU) | 1965. Pear Trees | 28 Oct 2013 19:22 | 2 | New tests have been added. 13 authors have lost AC after rejudge. Edited by author 05.08.2013 10:00 |
|
|
|