PROBLEM LINK:
Contest Problem
Practice Problem
Setter: Prasann Kumar Gupta
Tester1: Ashish Kumar
Tester2: Vishal Mahavar
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Binary Search, Segment Tree
PROBLEM
Given with two arrays a[] and cost[] of length N. cost[i] is the cost of incrementing/decrementing a[i] by 1. You will be provided with Q queries.
i x y → This updates value of a[i] with x and cost[i] with y.
After each query you have to output the minimum cost to make all elements in the array equal by performing the increment/decreament operation on any element any number of times.
As answer could be large output the answer modulo 10^9 + 7.
SOLUTION:
Hint 1
Think for the same problem, assuming cost of incrementing/decrementing is always 1.
Hint 2
Find if there is a specific point, such that cost of equalizing all its elements will be minimum every time.
Hint 3
Think of reducing this Problem to a problem where cost of incrementing/decrementing is always 1.
Solution
We can observe that, if cost of unit incrementing/decrementing values is always 1, then, we will get the total cost minimized if we make all elements equal to the median of the array.
Now, we have to reduce this problem, to a problem similar to the one where cost for unit incrementing/decrementing is always 1.
To achieve this, we can have cost[i] occurrences of a[i] in the array and make cost for every element as 1. This is equivalent to the original problem as it will ensure that cost of unit incrementing/decrementing a specific value x will be
(cost of unit incrementing/decrementing a single element) * (number of occurrences of x).
In the reduced problem, we know that, cost of incrementing/decrementing a single element by 1 is 1 and number of occurrences of x in the array is cost[i]. Therefore, the cost of unit incrementing/decrementing a specific value x will be cost[i] which is indeed same as the original problem.
Now, our problem is reduced to find the median of the modified array (which contains cost[i] occurrences of a[i]). But we can observe that the size of such modified array can be very large. Therefore, we cannot simply create a modified array and find the middle element.
So how to find the median of the modified array?
There are a couple of ways to do the same. We can use binary search with segment tree to find the median according to the number of occurrence of each a[i]. Let say sum is the total number of elements in the modified array. To find the median of the modified array we need to find an element a[i] such that the number of elements less than a[i] is equal to number of elements greater than a[i] in the sorted modified array. Therefore, if the number of elements which are less than a[i] (including a[i] in the sorted modifies array) is less than (sum+1)/2, then our median lies on the right side of a[i]. Else median lies on the left side of a[i]. To find the number of elements less than a[i] efficiently, we could use sum-segment tree or fenwick tree.
This median finding algorithm will take O(log ^2 n) per query.
But, we can also optimize it to O(logn) per query using only segment tree with extra computations.
After, finding the median by any of the algorithm, we can easily find the cost to make all elements equal to the median by quering on a sum-segment tree.
TIME COMPLEXITY:
If we use binary search with segment tree to find the median in the modified array. We need to query in the segment for every iteration of binary search. Therefore, the Total Complexity will be:
O(q\times log^2n)
Whereas, as discussed we can reduce this complexity to O(q\times logn) using extra computation on the segment tree (mentioned in the setter’s solution).
Though, we allowed log^2n per query to pass.
SETTER’S SOLUTION
https://www.codechef.com/viewsolution/62724395
TESTER’S SOLUTION
https://www.codechef.com/viewsolution/62724255
TESTER’S SOLUTION
https://www.codechef.com/viewsolution/62724314