Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

aopo's blog

By aopo, history, 7 weeks ago,

Hello connections!

Recently i tried my hands on this problem. I solved it using segment tree and fenwick tree but i don't know how to solve it using LIS concept. It would be very nice if some of you can share your approach for solving this.

Here is what i think regarding this!

We maintain a multiset and go on inserting elements from left to right adding elements one by one , finding the upper_bound of ai and removing it if its exists and then doing ans=max(ans,*st.rbegin()) if the size of my multiset is bigger than l.But this is giving me WA.I don't know where am i going wrong.It would be very helpful if someone can point out my mistake.

• 0

 » 7 weeks ago, # | ← Rev. 2 →   0 We maintain an array $E$, where $E_i$ is the smallest number that a LIS of length $i$ can $E$ nd with. At the start, $E_i = inf$ for all $1 \leq i \leq N$, and $E_0 = -inf$. Then, process the numbers of the input array $A$ from left to right. Let's say we're on $A_k$. We want to find the last index $i$ in $E$ such that $E_i < A_k$. What this means is that, using the numbers $A_0, \cdots, A_{k-1}$, we could build a LIS of length $i$ which ends with $E_i$, a number smaller than $A_k$. We can then append $A_k$ to this LIS, getting a LIS of length $i+1$ ending with $A_k$. This means $E_{i+1} = min(E_{i+1},A_k)$.This is the only improvement we can make, as we couldn't append $A_k$ to LIS's represented by $E_{i+1}, \cdots, E_N$ as their last elements are $\geq A_k$, so they wouldn't be LIS after appending $A_k$, and there is no point appending $A_k$ to LIS's represented by $E_0, \cdots, E_{i-1}$ as we already have LIS's longer than them ending in a number smaller than $A_k$.In each step, we have for every length $i$ the smallest number that a LIS of that length can end with, using the numbers we have processed so far. At the end, we have the answer for the whole array $A$: $E_L$. If it's $inf$, there is no LIS of length $L$ in $A$.The step 'find the last index $i$ in $E$ such that $E_i < A_k$' can be done using binary search, as $E_i$ is non-decreasing. The complexity is $O(NlogN)$.
•  » » 7 weeks ago, # ^ |   0 Really liked your idea. It's really an amazing solution. Possibly we can now answer the last element of an increasing sequence with any length!