ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1965. Pear Trees

hints
Posted by 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.
Re: hints
Posted by Abid29 13 Apr 2021 18:18
my solution is 0.14sec
if you are better plz email me s-2017915104@isrt.du.ac.bd