Weekly Contest 222
Question 1:
- Greedy choice
- 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<<21 means 2 power 21 (bit shift)
- 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,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:
- Binary Search Application
-
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
- 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()
- We could use normal approach of finding LCS using dp to get answer but it will result in TLE due to the length constraints.
- 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
- 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.
- 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
- Now, LIS would have the - LIS 😂
Good luck on your next contest!
Until next time,
@stratospher
Top comments (0)