SETDIFF - Editorial

editorial
, , ,
3

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

4

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.

5
  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

6

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)

7

@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.

8

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

9

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.

10

@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.

11

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

12

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

13

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;
}
14

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…

15

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;
}

16

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

17

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

18

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

19

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.

20

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.

21

The reason we have to do this (+mod) trick is that many languages return (a % b) to be zero or the same sign as a, instead of b. Fortunately, python does it right, so you can safely write (Q-P) % mod .

22

your modular() function has exponential complexity.