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<=t<=100
1<=N<=100000
1<=starting node,ending node<N
1<=weight of node<=1e9
Constraints of Q2:-
1<=t<=10
1<=N<=100000
1<=C<=1e15
1<=A[i]<=1e9
1<=B[i]<=1e9
Question 1 is on net ,( hackerrank) , dp on tree.
Also how many u solved?
partially solved both . For the second question I want to see efficient approach( something
like O(N log N) ) . I have seen similar type of question in past Hackerearth contest .
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
else:
end = mid - 1
ans = max(ans, val - i + 1)
return ans
Please note that to find max(B[i],.....B[mid]), you need to use sparse table O(1) approach.
Oh thanks mate I didn’t knew about sparse table can be used to find the max in O(1) time . My bad.
How to solve this question?? The best i could come up with was to emulate the process repeatedly by selecting k most frequent elements using a multiset.
One of my friend sent me this problem, wasn’t able to solve, @everule1 @ssjgz @carre could you please give some hints for this?? (1 \leq k \leq 10^5)
Thanks
I can not see the constraint for k
could this work?:
sort the elements by c[i] value (non-decreasing)
then:
for i=0 to n-k:
add(c[i])
substract c[i] for k-1 elements greater than i (segment tree to do this)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
1 \leq k \leq 10^5
I edited the post, could that approach work?
Taking the sample:
N = 4, K = 2, c = [7, 7, 8, 17]
Then the answer we will get from your algo is 7 + 8 = 15(if I understood correctly). But answer is 19.
That algorithm does give 19, and I can show it to be optimal for k=2.
It is in fact min(2*mx, 2*(sum-mx)) for k=2.
How?? Please explain…
Look up stoned game on cf.
I am Assuming mx is maximum element, assume only 2 elements in array [1, 100] and K = 2, the best you can get is only 1 group.
N=6, K = 4
2 3 4 7 9 9 13
Ans is 11.