"SpicyBitter" Sequence of Sauces

Question

“SpicyBitter” Some people can handle spicy.  Some people can tolerate bitter foods.  You have access to n different kinds of sauces, with different levels of “spicyness” and bitterness.  You are organizing a food festival and want to create a sequence of sauces such that each sauce is both SPICIER AND MORE BITTER than the sauce prior to that.  You want to create as long a sequence as possible using the given list of sauces.  Consider this kind of structure: “Sauce [spice: double, bitterness: double]”.  You are given an array a[1..] of Sauce objects.  Give an algorithm to create the longest possible sequence, and analyze the time complexity of your algorithm in terms of n.

Answer 1

This is an example of the Longest Increasing Subsequence problem. We can solve this by sorting the list of sauces by one of the two characteristics (i.e. Spicyness and Bitterness), then using the other characteristic in the LIS solution:

Suppose S[1...n] represents the sauce options, and L(i) represents the size of the longest strictly increasing subsequence that ends at position i. Such a sequence must include S[i], therefore each L(i) is at least 1. Therefore we can write the recurrence as

L(1)=1

L(i) = max {L(j)}+1, such that j<i and S[j] < S[i]

We observe that to calculate each L(i), we need O(n) time, to examine the S[j] values against S[i], for all j < 1.

Therefore we can calculate all L(i) values in O(n^2) time, then find the largest one in O(n) time. Therefore overall complexity is O(n^2).

We can improve this by using binary search to find the largest value when updating L(i) in the recurrence step.

Answer 2

This problem is similar with the LIS problem, but we only can use LIS to solve one sauce. ( spicy or bitterness)

So we have to sort the array before we we using LIS.  (Assume we use LIS to deal with the bitterness)

First, we can sort the array by increasing level of spicy. When there are several guests have the same level of spicy, we can sort these arrays by decreasing level of bitterness. 

        For example, the array will be : { (5, 7), (7, 5), (7, 0), (5, 8),(6, 9) }    sort(spicy, bitterness) = {(5, 8), (5, 7), (6, 9), (7, 5), (7, 0) }. Spicy level : 5 6 7 while the spicy level is same, like level 5, the bitterness will sort by decreasing: 8 7.

Second, find the longest increasing subsequence (LIS) by the bitterness level. 

        Like the example before, sort(spicy, bitterness) = {(5, 8), (5, 7), (6, 9), (7, 5), (7, 0)}. After sorting, the question will become the LIS of the array bitterness= (8,7,9,5,0)

        By using DP, the LIS of the bitterness is (7, 9)

Then the answser is (5, 7) (6, 9). 

Answer 3

Solution: First sort one of the attributes in ascending order, then make the longest ascending subsequence for another attribute, and finally DFS outputs the sequence. The time complexity should be O(N^2)

For the typical deformation of the longest ascending subsequence (LIS), I' m considering if we can change the time complexity from n ^ 2  to nlogn algorithm.

Definition d [k]: the last element of the ascending subsequence with a length of K. if there are multiple ascending subsequences with a length of K, record the smallest one.

Note that the elements in D are monotonically increasing. We will use this property next.

First, len = 1, d [1] = a [1], then for a [i]: if a [i] > d [len], then len + +, d [len] = a [i];

Otherwise, we need to find a j from D [1] to d [len-1], which satisfies the requirement of D [j-1] < a [i] < d [j]. According to the definition of D, we need to update the last element of the ascending subsequence with a length of J, that is, d [j] = a [i];

The final answer is len

Using the monotonicity of D, we can find j in two parts, so the time complexity is nlogn.

For example,

First, put d [1] in B in order, and make B [1] = 2, that is to say, when there is only one digit 2, the minimum end of LIS with length 1 is 2. At this time, len = 1

Then, put d [2] in B in order, make B [1] = 1, that is to say, the minimum end of LIS with length of 1 is 1, d [1] = 2 is useless, it's easy to understand. At this time, len = 1

Then, d [3] = 5, d [3] > b [1], so let B [1 + 1] = B [2] = D [3] = 5, that is to say, the minimum end of LIS with length of 2 is 5, which is easy to understand. In this case, B [1.. 2] = 1, 5, len = 2

Next, d [4] = 3, which is just added between 1 and 5, so it is obviously not appropriate to put it in the position of 1, because 1 is less than 3, and the minimum end of LIS with length of 1 should be 1, so it is easy to deduce that the minimum end of LIS with length of 2 is 3, so 5 can be eliminated. At this time, B [1.. 2] = 1, 3, len = 2

Continue, d [5] = 6, it's behind 3, because B [2] = 3, and 6 is behind 3, so it's easy to deduce that B [3] = 6, and then B [1.. 3] = 1, 3, 6, or it's easy to understand? Len = 3.

The sixth one, d [6] = 4, you see it's between 3 and 6, so we can replace 6 and get B [3] = 4. B [1.. 3] = 1, 3, 4, len continues to equal 3

The seventh one, d [7] = 8, it's big, bigger than 4, HMM. So B [4] = 8. Len becomes 4

The eighth one, d [8] = 9, gets B [5] = 9, HMM. Len continues to grow to 5.

The last one, d [9] = 7, is between B [3] = 4 and B [4] = 8, so we know that the latest B [4] = 7, B [1.. 5] = 1, 3, 4, 7, 9, len = 5.

So we know that the length of LIS is 5.

This 1,3,4,7,9 is not lis, it is just the minimum end of the corresponding length LIS stored. With this end, we can insert data one by one. Although the last d [9] = 7 update has no meaning for this group of data, if there are two more numbers 8 and 9, then you can update 8 to d [5], 9 to d [6], and get the length of LIS as 6.

Then it should be found that inserting data into B is orderly and can be replaced without moving - that is to say, we can use binary search to optimize the insertion time of each number to o (logn) ~ ~ ~ ~ so the time complexity of the algorithm is reduced to o (nlogn) ~!

  

Comments

int binary_search(int i){
    int left,right,mid;
    left=0,right=len;
    while(left<right){
        mid = left+(right-left)/2;
        if(ans[mid]>=arr[i]) right=mid;
        else left=mid+1;
    }
    return left;
}
 
int main()
{
      freopen("input.txt","r",stdin);
    int T,p,i,j,k;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&p);
        for(i=1; i<=p; ++i)
            scanf("%d",&arr[i]);
       
        ans[1] = arr[1];
        len=1;
        for(i=2; i<=p; ++i){
            if(arr[i]>ans[len])
                ans[++len]=arr[i];
            else{
                int pos=binary_search(i);   
pos=lower_bound(ans,ans+len,arr[i])-ans;
                ans[pos] = arr[i];
        }
        printf("%d\n",len);
    }
    return 0;
}

Answer 4

This question is an example of the LIS problem. So we can solve this question by use LIS.

We can get the answer by the following:

sort a by spice and store the new sorted sequence in a2

sort a2 by bitterness while the order of spice fixed

let e be an object where e.lenth is the lenth and e.seq is the corresponding sequence

let l be an empty list

let count be 0

for i in a2:

     bitterness = i.bitterness

     spice = i.spice

     if l is empty

        add i to l

     if bitterness > l[0].bitterness and spice > l[0].spice

        add i to l

return l

time complexity:

the sort part takes O(nlogn).

the loop part loops all elements in sorted sequence, that takes O(n).

Hence the total time cost is O(n).

Comments

The overall answer cannot be O(n), since it involves sorting.

Answer 5

Let us tackle it by sorting the list of sauces by the characteristics of Spiciness and Bitterness and apply the Longest increasing sub-sequence problem. We can consider a sauce to be greater when BOTH spiciness and bitterness is strictly greater than another sauce.

The LISA algorithm is as follows:

Let A[1...n] represents the sauce options and let B(i) represents the size of the longest strictly increasing subsequence that ends at position i.

That sequence must include A[i], thus, each B(i) is, at least, 1. We can conclude, we can

write the recurrence as:

B(1)=1
B(i) = max {B(j)}+1, such that j < i and A[j] < A[i]

We observe that to calculate each L(i), we need O(n) time, to examine the A[j] values against A[i], for all j < i.
Thus, we can calculate all B(i) values in O(n^2) time, then find the largest one in O(n) time. Therefore, overall complexity is O(n^2). Even though, we can try to make it better by finding the largest value by updating B (i) in the recurrence.