I wanna ask is there any why by which we can check that a given array can be split int two subsequence such that both are Strictly increasing. If not Possible Output is "NO" else "YES".

Better approach than O(2^n).

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | wxhtxdy | 3276 |

7 | LHiC | 3276 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

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

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | Vovuh | 165 |

4 | PikMike | 165 |

4 | antontrygubO_o | 165 |

7 | rng_58 | 160 |

8 | majk | 156 |

8 | Um_nik | 156 |

10 | 300iq | 155 |

I wanna ask is there any why by which we can check that a given array can be split int two subsequence such that both are Strictly increasing. If not Possible Output is "NO" else "YES".

Better approach than O(2^n).

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2019 18:23:09 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

oops!

NANI??

Answer Should be "NO"

Don't read the previous version of this comment.

Solution: let's notice that if there are i, j such that i < j and a[i] >= a[j], then i and j belong to different SIS. Then, if there are such i, j, k such that i < j < k and a[i] >= a[j] >= a[k], all of them belong to different SIS, so there is no answer in this case. There is always an answer if there are no such i, j, k, because in this case: for every i, j such that i < j and a[i] >= a[j], every k from j + 1 to n will be such that a[k] > a[i] and a[k] > a[j], ==> we can add k to the SIS of i or j. So all you need to do is check if there is non-increasing subsequence of length more than 2. In this and only in this case there is no answer.

I thought of that thing but was unable to prove

I edited the comment, new solution seems right to me.

Auto comment: topic has been updated by saifhaider0z (previous revision, new revision, compare).I think the problem 1144G - Слияние двух последовательностей is almost the same as yours.

Check this comment for a really good solution (but for a one increasing and a one decreasing subsequence):

Two merged subsequences greedy idea

You can adapt it easily to your situation with the following main modification:

If an element can be put in both arrays, but it in the array that has a larger last element (To give a chance for smaller elements to be put in the other array later).

We can do DP using the fact that the previous element must belong to increasing or decreasing subsequence. If we know to which it belongs, then we know whether we should minimize or maximize the last element of the other subsequence.

Go from left to right and store two variables: $$$smallest$$$ and $$$biggest$$$. When you are at position $$$i$$$, the variable $$$smallest$$$ is the smallest possible last element of the increasing subsequence, assuming that position $$$i-1$$$ was taken to the decreasing subsequence. And the same opposite thing for $$$biggest$$$ and assumption that $$$i-1$$$ is in the increasing subsequence.