Weekly Contest 222

Question 1:

1. Greedy choice
2. Easy way to sort vectors:

Here the inputs are of the form [[2,5],[4,7],[3,9]] and we need to sort it based on the descending order of 2nd value in each pair. ie, it should become [[3,9],[4,7],[2,5]]

sort(a.begin(), a.end(),
            [](const auto& L, const auto& R){
                 return L[1] > R[1];
             }
     );

Question 2:

1. 1<<21 means 2 power 21 (bit shift)
2. Read the constraints properly. In this question deliciousness[i] can vary from 0 to 2^20 meaning -> sum of 2 elements in array can at max have value = 2^20+2^20 = 2^21.

ALGORITHM:
1. insert all elements of deliciousness into map[]
2. go to every element in deliciousness[]
        loop over all possible sums from 1 to 2^21
                if sum-element is present in map 
                        if element==sum-element
                               contribution=number of deliciousness[sum-element] in map - 1
                         else
                               contibution = number of deliciousness[sum-element] in map 
3. Answer will be contribution/2

1. [1,1,1,3,3,3,7] would be {1:3,3:3,7:1} in map. For a sum=8, (1,7) can form 3 pairs. Each time we encounter a 1 or a 7, we add it's pair's frequency = 1+1+1 + 3 = 6. We would have counted each (1,7) twice by then. So we need to divide by 2 in the end.

Question 3:

1. Binary Search Application

2. Construct a prefix sum array and we need to split it into 3 parts - left, mid and right

   prefix[left]<=prefix[right]-prefix[left]<=prefix[n-1]-prefix[right]
   2*prefix[right]<=prefix[n-1]+prefix[left]
   

ALGORITHM:
1. ans=0
2. For every index left in the prefix sum array
3.   leftsum=prefix[left]
4.   remainingsum=(prefix[n-1]-leftsum)/2
5.   we need to satisfy 2*prefix[left]<=prefix[right]
     we also need prefix[right]<=(prefix[n-1]+prefix[left])/2
     left+1 is starting index of mid part of array
     right is ending index of mid part of array
6.   For range in [left+1,n-1]
          it1=first index with prefix sum >= 2*prefix[left]
          it2=first index with prefix sum > (prefix[n-1]+prefix[left])/2
          so all indices between it1 and it2 will satisfy our conditions!!!
          ans+=(it2-it1)
7. return ans        

lower_bound and upper_bound are great functions which can help!
Iterator lower_bound (Iterator first, Iterator last, const val)

• lower_bound will return first index with value>=val
• upper_bound will return first index with value>val

Question 4

1. If we can find longest common subsequence between target[] and arr[]; we just need to add the elements in target to arr[] to make target[] a subsequence of arr[] Answer is target.size() - LCS.size()
2. We could use normal approach of finding LCS using dp to get answer but it will result in TLE due to the length constraints.
3. They have specified elements of target are distinct. This is a green light to convert problem into Longest Increasing Subsequence.

To convert LCS->LIS (since target[] are distinct);
    create a Map from target[i] to i
    if any element of arr[] is present in target[]
        push the index of element in target[](Map[arr[i]]) to a vector

1. Now the vector would contain indices - for it to be a longest common subsequence we would need to choose indices in the increasing order -> becomes a longest increasing subsequence problem.
2. This can be solved by creating a new vector - lets say vector LIS

     we traverse through all elements of the indices vector:
          we check if there exists any number in LIS which is just greater than/equal to current element
          if yes,
              replace that number with current element
          if no, 
              push current element into LIS

1. Now, LIS would have the - LIS 😂

Good luck on your next contest!

Until next time,
@stratospher