Блог пользователя saifhaider0z

Автор saifhaider0z, история, 5 лет назад, По-английски

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).

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

oops!

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

I think the problem 1144G - Слияние двух последовательностей is almost the same as yours.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

»
5 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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.