# Approach and Solution to MEXUM(April Lunchtime 2020)

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.

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

5 Likes

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

}

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

3 Likes

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

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

I think this should work.

2 Likes

that was it.
feeling stupid right now.

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

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

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?

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

You can check it further here.

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

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

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