Approach and Solution to MEXUM(April Lunchtime 2020)

general
1

Problem Link
Here is my approach to MEXUM, I hope it might help you.

Try to think in reverse, how many subsequences will be there with MEX = 1, 2, and so on.

So, let us try to analyze small cases and form a pattern.
Let n = Total number of elements and
cnt1 = Total elements with count = 1.
cnt2 = Total elements with count = 2.
ans so on.

Now for MEX = 1:
Num_of_subs = (Any of n - cnt1)
→ Num_of_subs = 2^(n - cnt1) .

for MEX = 2:
Num_of_subs = (Atleast 1 of cnt1) * (Any of n - cnt1 - cnt2) .
=> Num_of_subs = [ { 2^(cnt1) - 1 } * { 2^(n - cnt1 - cnt2) } ].

for MEX = 3:

Try to think on your own

Num_of_subs = (Atleast 1 of cnt1) * (Atleast1 of cnt2) * (Any of n - cnt1 - cnt2 - cnt3) .
=> Num_of_subs = [ { 2^(cnt1) - 1 } * { 2^(cnt2) - 1 } * { 2^(n - cnt1 - cnt2 - cnt3) } ].

And so on until you don’t get a break in consecutive numbers from 1 to Current_MEX.

Why?

Because the smallest positive integer, not present can be the maximum MEX we can achieve.

Submission Link
The solution is messy because I had to debug it for a long time.

5 Likes
2

I was struggling to in debugging.but I was failed can you take a quick look at my code and tell me what’s wrong.

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long int lt;
typedef vector vi;
typedef vector vin;
typedef pair<ll,ll> pll;
typedef pair<int,int> pin;
#define all(a) a.begin(),a.end()
#define rep(i,a,b) for(int i=a;i<b;++i)
#define f(i,b) for(int i=0;i<b;++i)
#define per(i,a,b) for(int i=a;i>=b;–i)
#define test(t) int t; cin>>t; while(t–) solve()
#define endl “\n”
#define p1 cout<<“YES”<<endl
#define p0 cout<<“NO”<<endl
#define fst ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

ll mod_pow(ll a,ll n,ll mod) //(a^n)%mod
{ ll res=1;
while(n){ if(n&1) res=(resa)%mod; n/=2; a=(aa)%mod; }
return res;
}

void solve();

int main()
{
fst;
test(t);
//solve();
}

/**********************<=“Actual code strats here”=>*****************************/
const int mod=998244353;
const int maxn=1e5+5;
int f[maxn];
void solve()
{
ll n;
cin>>n;

memset(f,0,sizeof f);
rep(i,0,n)
{
	ll x;
	cin>>x;
	if(x<maxn)
		f[x]++;
}



ll sum=1,sum2=1;
int i=1;
int cnt=1;
while(1)
{
	
	sum+=sum2*(i*(mod_pow(2,n-f[i],mod)-cnt));
	sum%=mod;
	sum2*=mod_pow(2,f[i],mod)-1;
	sum2%=mod;
	n-=f[i];
	if(f[i]==0)
	{
		break;
	}
	i++;
	cnt=0;
}

cout<<sum<<endl;

}

3

sum2*(i*(mod_pow(2,n-f[i],mod)-cnt)) probably overflows

3 Likes
4

sum+=sum2*(i*(mod_pow(2,n-f[i],mod)-cnt));

Better write each term sepeartely and take modulo then multiply.
and after subtracting add modulo before taking mod.

sum2*=mod_pow(2,f[i],mod)-1;
sum2%=mod;

Here also same After subtracting 1, You should
add mod before taking modulo.

sum2*=mod_pow(2,f[i],mod)-1; sum2 += mod;
sum2%=mod;

I think this should work.

2 Likes
5

that was it.
feeling stupid right now. :sweat_smile:

6

I followed same approach .Please help , where my code failed :

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

const ll N = 1e5+10;
ll a[N];
ll coun[N];
ll pref[N],mul[N],p2[N];

int main()
{

    ll t,n,i,j,ans,val,temp,res,sum,v,mx;

    p2[0]=1;
    for(i=1;i<N;++i)
        p2[i] = (p2[i-1]*2)%MOD;

    cin>>t;

    while(t--)
    {
        cin>>n;

        for(i=0;i<=(n+2);++i)
                coun[i]=pref[i]=mul[i]=0;
        for(i=1;i<=n;++i)
        {
                cin>>a[i];
                if(a[i]<=(n+1))
                    ++coun[a[i]];
        }
    


        sum = 0;
        res = 0;
        //cout<<n<<"\n";

        for(i=1;i<=(n+1);++i)
        {
            pref[i] = (pref[i-1] + coun[i])%MOD;
            

            v = ((n - pref[i])%MOD)%MOD;

            


            v = p2[v];


            if(i==1)
            {
                res = (res+v)%MOD;
                mul[i] = p2[coun[i]]-1;
            }
            else
            {
                res =  (res + (v*(mul[i-1]*i)%MOD)%MOD)%MOD ;
                v = p2[coun[i]]-1;
                mul[i] = (v*mul[i-1])%MOD;
            }


        }

        res = (res+MOD)%MOD;


        cout<<res<<"\n";


    }






    return 0;
}
7

why we should add mod before subtracting 1?
I mean to say what problems it can cause?

8

if(!done){
int temp = product * num; temp %= MOD;
ans += temp; ans %= MOD;
}

if(!mp.count(1))
    ans++, ans %= MOD;

What is the purpose of these two statements?

9

Consider a = 2, b = 4.
Now if you (2 - 4) % 4
We get output in negative. i.e -2.

So this might result in wrong answer.
So, its consider good practice to add modulo whenever subtracting to make answer positive.

1 Like
10

You can check it further here.
Link

11

I would say it was some debugging I had to do and added conditions as my code was giving the wrong answer.

12

if all the given numbers are in order 1 2 3 …n
we have consider n+1 which is ans for all subarrays which contains numbers from 1 to n

1 Like
13

consider
1 1 2 3 1 2
map will only contain numbers from 1 to 3
but we have to consider 4 as it could be the answer

So basic condition is that whenever you find number with frequency zero break

1 Like