Hii guys today I took part in Google Online Challege for summer internship 2021 . The challenge was invitational . I got invite for it last week . I am sharing the questions for practise purpose of others . Enjoy and Share your answers on comment sections.
Constraints of Q1:-
1<=starting node,ending node<N
1<=weight of node<=1e9
Question 1 as said by @ssrivastava990 is available on hackerrank and you might find it on codechef/codeforces also.
In question 2, for each index i, we can do a binary search on K, using sparse table and prefix array you can calculate the value of objective function in O(1) time, therefore total time complexity would be O(N*log(N)).
Thanks buddy but still I have a doubt on 2nd one . I got that we can use prefix sum to get the second part of equation in O(1). But finding the subarray of K and then the maximum value of it using Binary search I didn’t fully got it . Can you code it with comments . It would be very helpful.
ans = 0
for i in range(1, n):
start = i, end = n, val = i - 1
while(start <= end):
mid = (start + end)/2
cost = max(B[i],.....B[mid]) + (mid-i+1)*(prefix[mid] - prefix[i-1])
if(cost <= c):
val = mid, start = mid + 1
end = mid - 1
ans = max(ans, val - i + 1)
Please note that to find max(B[i],.....B[mid]), you need to use sparse table O(1) approach.
I got the same problem. I guess i passed some test cases using basic permutations and combinations ig. It was like - 1. nCk ways to select k diff groups 2. find num of ways to select each group. 3 multiply 1 and 2