PROBLEM LINK:
Author: Amit Kumar Pandey
Tester: Kevin Atienza
Editorialist: Ajay K. Verma
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng
DIFFICULTY:
Easy
PREREQUISITES:
Basic maths
PROBLEM:
Given a multiset consisting of N numbers, find the sum of difference between maximum and minimum element of each subset.
QUICK EXPLANATION:
Compute the sum of maximum element of each set, and the sum of minimum element of each set separately, and then subtract the latter from the former to get the answer. The sum of maximum (minimum) element of each subset can be computed easily by iterating through the elements of the multiset in sorted order (see explanation below).
EXPLANATION:
We are given a multiset S consisting of N numbers, and we need to compute the sum of difference between maximum and minimum element of each subset of S, i.e.,
T = \sum (max(s) - min(s)), where sum goes over all subsets s of S.
Equivalently,
T = (\sum max(s)) - (\sum min(s))
In other words, we can compute the sum of maximum element of each subset, and the sum of minimum element of each subset separately, and then compute their difference.
Sum of Minimum Elements of All Subsets:
Let us say that the elements of S in non-decreasing order are \{a_1, a_2, \cdots, a_N\}. Now, we can partition the subsets of S into following categories:
-
subsets containing element a_1:
These subsets can be obtained by taking any subset of \{a_2, a_3, \cdots, a_N\}, and then adding a_1 into it. Number of such subsets will be 2^{N - 1}, and they all have a_1 as their minimum element. -
subsets not containing element a_1, but containing a_2:
These subsets can be obtained by taking any subset of \{a_3, a_4, \cdots, a_N\}, and then adding a_2 into it. Number of such subsets will be 2^{N - 2}, and they all have a_2 as their minimum element.
\cdots
i) subsets not containing elements a_1, a_2, \cdots a_{i - 1}, but containing a_i:
These subsets can be obtained by taking any subset of \{a_{i + 1}, a_{i + 2}, \cdots, a_N\}, and then adding a_i into it. Number of such subsets will be 2^{N - i}, and they all have a_i as their minimum element.
\cdots
It can be seen that the above iteration is complete, i.e., it considers each subset exactly once. Hence, the sum of minimum element of all subsets will be:
P = a_1 2^{N - 1} + a_2 2^{N - 2} + \cdots + a_i 2^{N - i} + \cdots + a_N 2^0
P = a_N + 2 (a_{N - 1} + 2 (a_{N - 2} + 2 (\cdots 2 (a_2 + 2 a_1) \cdots))))
This sum can be computed easily in linear time.
In a similar way we can compute the sum Q of maximum element of all subsets of S. The only difference is that we need to iterate the elements of S in non-increasing order. Finally, the answer of our problem will be (Q - P). The following snippet shows how to compute P and Q
// sort the array in increasing order.
sort(S.begin(), S.end());
P = 0;
Q = 0;
for (int i = 0; i < N; ++i) {
P = (2 * P + A[i]) % mod;
Q = (2 * Q + A[N - 1 - i]) % mod;
}
return (Q + mod - P) % mod;
Time Complexity:
O (N \log N)
AUTHORâS AND TESTERâS SOLUTIONS:
Authorâs solution will be put up soon.
Testerâs solution will be put up soon.