Hello all,
Can you please share your thoughts on the following question:
Given an array of integers and some queries, you have to tell the length of the longest increasing subsequence for each query. The query is in the form such that you have to change the value at a given index to given value. Each query is independent of others. So the array gets backs to its original state after each query.
Example: Arr[]={1,6,2,4};
query: 1 4 : means: arr[1]=4, Now calculate the length of LIS.
Thanks in advance.
Limits? And link to the problem, please.
Actually this problem was from a hiring challenge on hackerearth and the challenge is over now but now the problem is not visible. There are 100000 queries and the size of array is 100000. So every query needs to answered in constant or atmost logN time.
Right!
There is one important thing you've never mentioned, are there any constraints on the values? Something like 0 ≤ arr[i] ≤ 100 or maybe something like this.
0 <= arr[i] <= 100000
Does the array return to it's original form after the query, or does 1 query affect the array for all the remaining queries?
The array remains unaffected. That means all the queries are performed on the orignal array
Solve the problem offline.Compute initial length of LIS, call it L. For each query, answer is L — 1, L, or L + 1.
The new LIS will be either a subsequence containing x, either one that doesn't contain x.
For sure answer will be at least L — 1. Let's check if it can be L or L + 1. We can reduce each query x y from input to: if we set arr[x] = y, what is LIS containing position x after this change. We also need to check if there was a LIS in original array not containing x, if so answer can be L. To check that, we need to check if x was in all LIS in original array. Can be done in O(n log n) when calculating LIS.
Split any LIS containing x in two: L1(x) one containing indexes in {1, 2, ... x — 1} and L2(x) containing indexes in {x + 1, x + 2.... n}. L1(x) and L2(x) are independent of each other, so we can calculate them separately.
If queries are of type (x, y), set arr[x] = y, let's keep list L for each x in {1, 2... n} with y from queries.
Now you can do the standard LIS algorithm to calculate L1 and L2. In standard lis, for position i, we wanted to find the longest increasing subsequence that ends in a value smaller than a[i], and we could find that in O(log n). Now modification is that we need to go through query list of i, and for each y in query list, we need to find longest increasing subsequence ending in a value smaller than y. We can do it in O(log n) for each. So total complexity (n + q) log n
Laiu How to check for LIS when we are not including element at index x?
I'll write pseudocode as it is easier to understand:
lis1[i] = lis ending at position i, cnt1[i] = number of such lis.
Similarly lis2[i] = lis starting at i, cnt2[i] = number of such lis.
for(i = 1 to n) {
lis1[i] = max(lis1[j] + 1 | j < i and a[j] < a[i])
cnt1[i] = sum(cnt1[j] | j < i, a[j] < a[i] and lis1[j] + 1 = lis1[i])
}
for(i = n to 1) {
lis2[i] = max(lis2[j] + 1 | j > i and a[j] > a[i])
cnt2[i] = sum(cnt2[j] | j > i, a[j] > a[i] and lis2[j] + 1 = lis1[i])
}
Now to check if x is included in all LIS, 2 conditions must be hold:
1) lis1[x] + lis2[x] — 1 is maximum among all x(so it was contained in a LIS in original array).
2) cnt1[x] * cnt2[x] = number of LIS .To calculate number of LIS in original array(not necessary containing x), find all positions i with maximum lis1[i](so lis ends at that position) and add cnt1[i] for each. The number of LIS can overflow, so you must use some MOD to calculate it.
Thanks @Florin29 for explaining. So after preprocessing the above, we will iterate through each query and will find the element smaller than new a[i]=y(as per the given query) having the max LIS?
Let's say x is the part of the LIS and now for x, how will we find whether the answer is L or L+1 or L-1?
I am not able to understand this part. Could you please explain it again?
Hey swordx,
My impression is that Laiu's original post, although as idea correct (and largely same as mine) is at least incomplete in terms of explaining it.
I think my latest comment below should be able to offer a more comprehensive, detailed explanation for THE problem you proposed.
Cheers!
Best, Mircea (sAca)
Isn't 650D - Zip-line same problem?
Yes
Hey folks,
I think one possible nice solution to this problem is using 2D RMQ, for a total of at most O(log n) per query [maybe even O(1) — I am not sure how fast 2D RMQ can be done, but for sure no more than O(log n) as with general 2D Range Queries, using Fractional Cascading], with O(n * log n) preprocessing.
Since each query applies only wrt the original array, then there will be at most a 1 element difference between each query's array and the original one.
Keep a set of
LIS_pref = {(i,x,r) | a LIS of length r was encountered, ending at position i, with last element x=Arr[i]}of potential LIS-es encountered during the traditional O(n*log n) LIS algorithm. So this set will have cardinality at most O(n) — one element for each i.Similarly keep a set of
LIS_suff = {((j,x,r) | a LIS of length r exists, starting at position i, with x=Arr[i]}. This is the same as computing the longest DECREASING sequence starting from the back of the array. So its the same problem. The cardinality of this set is again O(n).Now each time an element at position i changes into b, there are cases:
Case1: The element with the new value b at position i belongs to some LIS for the new array, thus such a LIS would have length
2DRMQ(LIS_pref,<=i-1,<=b-1) + 1 + 2DRMQ(LIS_suff, >=i+1, >=b+1).Case2: The element with new value b, at position i does NOT belong to some LIS for the new array, and also DID NOT belong the LIS we found for the original array [we can simply compute the LIS of the original array and tag all elements on it]. In this case the answer would be the answer for the original array.
Case3: The element at position i, (i) belonged to ALL LISes of the original array AND (ii) it is no longer belongs to ANY of them, given its new value b. Determining for some element of some found-out LIS (for the original array) if it is a critical element for all LIS-es, it suffices to do a "critical nodes" walk of the DAG represented the "is-parent" links implicitly considered during the classical O(n * log n) algorithm [which takes O(n*log n) — the size of the DAG]. In this case, the answer is the original value, minus 1. The situation where (i) is true, but (ii) is false, is covered by Case 1.
Case4: None of the three cases above apply. In this case, the answer is the original value.
So the answer to each query is MAX(Case1, original_value * (Case2_applies), (original_value-1)*(Case3_applies), original_value*(Case4_applies)). This can be further simplified to consider only Cases 1 and 3.
So the above solves the problem with
O(n * log n)preprocessing and O(log n) per query [I strongly think the O(log n) could be improved to O(1) even since these are just Range-Max queries, not any kind of Range Queries].By the classical O(n*log n) algorithm I mean, for example, this one: https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms.
Enjoy!
Best, Mircea (sAca) <<07>>.<<03>>.20<<20>> @ 12:31, laptop time, Nizhny Novogorod.