SETDIFF - Editorial

editorial
, , ,
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.

23

what happen if Q is less than P then ans will become negative…
if u think Q never less than P than u r wrong because u r taking mod so it can happen so to avoid thid possibility be add mod in Q than subtract P from this…than take mode print ans u will get AC…

24

#prasadram126 …u r using int data type it is not enough to store big value like 10^9 so use long int or long long int …u will get AC for first subtask but u will TLE for remaining to get full point u have to use merge sort…here i have modified ur solution u can access from here CodeChef: Practical coding for everyone…

25

may be Q less than P in that case ans will become negative which not right…
if u think how it is possible …because we are taking mod in whole process it may become less than p think if Q= mod+1 at any stage because u take mod at every stage it will become 1 and P may be 2 than ans will become negative…hope u understood…