PROFDE EDITORIAL.
Problem Link:- PROFDE
SETTER : @arpitgupta16
Editorialist : @arpitgupta16
Difficulty : Medium
Pre-Requisites : Array, observation.
Solution: for 40 points.
Explanation :- The question was straight-forward. First we had to take an array of size N with initial value 10 then For M queries we had
to multiply every element in range i to j by k and finally we had to find floor value of average of elements of array;
Complexity: O(M*N)
Solution: for 100 points.
Explanation :- For 100 points MN = 10^10 hence O(MN) will give TLE. Let’s take two arrays (arr1 and arr2) of size (N+1) with initial values 1. Now for each query
we will multiply arr1[i] and arr2[j+1] by k
Now, multiply each element from index 1 in arr1 with its previous element and divide with its corresponding element in arr2
i.e. for(i : 1 to N-1){
arr1[i] = arr1[i]*arr1[i-1]/arr2[i]
}
after above operation multiply each element in arr1 with 10 and take average of elements from index 0 to index N in arr1. This average is required answer.
Example:
Sample Input:
1
5 3
1 3 5
2 5 2
3 4 7
Initially: arr1 = {1, 1, 1, 1, 1, 1}, arr2 = {1, 1, 1, 1, 1, 1}
after query 1. arr1 = {5, 1, 1, 1, 1, 1}, arr2 = {1, 1, 1, 5, 1, 1}
after query 2. arr1 = {5, 2, 1, 1, 1, 1}, arr2 = {1, 1, 1, 1, 1, 2}
after query 3. arr1 = {5, 2, 7, 1, 1, 1}, arr2 = {1, 1, 1, 5, 7, 2}
Now, after multiplying each elements in arr1 with its previous and dividing by corresponding element in arr2
arr1 = {5, 10, 70, 14, 2}
after multiplying by 10: arr1 = {50, 100, 700, 140, 20}
average of arr1 = 202
Complexity: O(M+N)
Observation: Here we can see that after multiplying by 10 array arr1 will be same as array obtained in approach 1 but here
complexity is O(N+M) which was O(M*N) in approch 1
Setter’s and Editorialist’s Solution:
Setters and Editorialists Solutions.
Hope you liked it and feel free to share any approach or ask any doubts in comments below. Other optimal solutions are encouraged too.