SETDIFF - Editorial

PROBLEM LINK:

Practice
Contest

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:

  1. 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.
  2. 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.

2 Likes

Hello,

I followed a similar approach and this was a fun problem for me:

http://www.codechef.com/viewsolution/6885298

I had some troubles with MOD though ^^

Best,

Bruno

How is this not passing any test case in python and giving TLE ?
Complexity is nlogn, that also because of sort(), rest is O(n).

http://www.codechef.com/viewsolution/6974845

We were required to calculate
(Q-P)%mod here
but (Q+mod-P)%mod
actually means ((Q-P)+mod)%mod=((Q-P)%mod+(mod%mod))%mod
=((Q-P)%mod)%mod
which is not same as (Q-P)%mod?

can someone explain. Thanks in advance.

  1. subsets containing element a1:
    These subsets can be obtained by taking any subset of {a2,a3,⋯,aN}, and then adding a1 into it. Number of such subsets will be 2^(N−1), and they all have a1 as their minimum element.
  2. subsets not containing element a1, but containing a2:
    These subsets can be obtained by taking any subset of {a3,a4,⋯,aN}, and then adding a2 into it. Number of such subsets will be 2^(N−2), and they all have a2 as their minimum element.

Hello sir,the sub sets of type 2 are already counted in step 1
Regards
Samuel

P = (2 * P + A[i]) % mod;
Q = (2 * Q + A[N - 1 - i]) % mod;

so answer is (Q + mod - P) % mod; because Q may be less than P. (Q < P)

@rahul18182212: P and Q are not the exact sums but they are sums%MOD. Suppose sum of maximum numbers is (10^9+8), and sum of minimum numbers is 5000. In this case, Q=1 and P=5000. If we do Q-P, we get negative number. Hence we add MOD to it. Hope this clarifies your question.

i tried somewhat same approach, but i got wrong answer…!! why…?
http://www.codechef.com/viewsolution/6960141

I think we have to consider the case when a[i] and a[i+1] are same so the set will not be different .
Because I think the subsets are pure set which does not contain duplicate .
Please correct me if I am wrong ?

taking care of this am still getting WA.

@mkkhedawat just use % operator instead of your modular function. If argument n of the function is around 10^18(as ip[i]<=10^9) then it gives TLE.

Hey,
Almost I followed the same manner, but instead of simplify the formula I wrote a customize function “bigMod” that calculates a (2^x % 1e9+7) but I got WA, couldn’t figure out where’s the mistake in my code,
here’s my code,
http://www.codechef.com/viewsolution/6982944
could anyone help me to recognize my fault, any response is highly appreciated

Hi can anyone please explain me why the answer is (Q + mod - P ) % mod instead of (Q - p) % mod??

Can anyone please tell me why I am getting wrong answer for task 7 and 9 using this code:

#include <bits/stdc++.h>
#include <iostream>

using namespace std;

const long long M = 1000000007;

int main()
{
    int t, n, i;
    long long a[100005];
    long long ans, toAdd, toSubtruct;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(i=0; i<n; ++i)
        {
            scanf("%I32d", &a[i]);
        }
        sort(a, a+n);
        toAdd = 0;
        toSubtruct = 0;
        for(i=0; i<n; ++i)
        {
            toAdd = (2*toAdd + a[n-1-i])%M;
            toSubtruct = (2*toSubtruct + a[i])%M;
        }
        ans = (toAdd + M - toSubtruct)%M;
        printf("%I64d\n",ans);
    }
    return 0;
}

i got the AC but it didn’t counted to my solved problems… i.e. my no of solved problems hasn’t increased… there must be some error in the system … admin pls. check…

why this code fails??
int main()
{
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
vi a;
REP(i,n)
{
int g;
cin>>g;
a.PUB(g);
}
sort(a.begin(),a.end());
int p = 0 , q = 0 ;
REP(i,n)
{
p = ((2 * p) + a[i] ) % MOD ;
q = ((2 * q) + a[n-i-1] ) % MOD ;
}
cout<<(q+MOD-p)%MOD<<endl;
}
return 0;
}

Hi ,
This is my solution which is giving WA ,so can any one please tell me where i have done wrong?
Thanks

Is it possible for (Q-P) to be less than zero.?

Hi All,
I think the explanation is not correct. when he says no.of subsets having element a1 is 2^(N-1) as this number of subset contains a subset which contains only {a1}. That is has no effect on the answer as it evaluates to 0.

But the code works because he is doing the same mistake again while calculating Q.So it cancels out.

Conclusion,you can say he purposely did it to make the code looks short and clear .I was expecting the explanation to be in the editorial.

Thank You

The formula (a + b)%m = (a%m + b%m)%m holds IFF both a and b are non-negative. And here its not necessary that (Q-P)>=0.

Note given in the problem statement says “Two subsets will be called different if there exists an index i such that S[i] occurs in one of the subset and not in another”. So u don’t have to care about a[i] and a[i+1] are same or different. Only different index matters.