Hello…
I am trying to solve this question…
Actually i am confused what this question is saying…
Could you see this please…
Thanks
Not able to understand this question
In this question it’s given that Alice is given an array of N integers. Now there are 2 players in this game one is alice and other is bob. When it’s Alice turn she picks a sub-array of the given array A.(you know what sub array are) In every turn, she picks a new subarray i.e. one with either different starting index or different ending index from the subarrays picked before.(by this it mean understand this with an example:
A = {1,2,3} Subarray will be
1,1
1,2
1,3
2,2
2,3
3,3
These are the subarrays we have formed when there’s different starting or ending point of that array.
Now its Bob turns he starts shouting the natural numbers from beginning i.e. he first says 1 then 2 … Alice stops him at the first integer which does not appear in the subarray(can be any integer not present in the selected subarray) that she has picked in this turn. Later on, she asks Bob to write the sum of all the values in which she stops him on a paper. We just have to calculate that only cause bob is weak at maths.
Hint: we have to visit each subset(continuous obviously), and try to find the smallest number which satisfies the condition.
Hii…
I have come up with n**3 approch … here …
https://www.hackerearth.com/submission/51655391/
It is showing TLE in 3 out of 5 test cases…
How should i optimise it…
Thanks…
int mex=1;
for(int j=i;j<n;j++){
if(arr[j] < n)
mp[arr[j]] = 1;
while(mp[mex])
mex ++;
ans += mex;
}
Try this, this will work for you.
Hii…
I understood what the trick you have used… You have increased maxx such that we don’t need to again run the third loop…\
I have coded like that…
But it is showing tle now for 2 test cases out of 5…
https://www.hackerearth.com/submission/51656267/
Hii…
I think map was creating problem…
This is the submission without using map…
https://www.hackerearth.com/submission/51656992/
But it is showing wrong answer on last test case…
Use unordered map and see if it gets accepted or not for this code
Or in this code declare size of map to 5E3 + 5
and bro declare map outside main cause it will take some time to reinitialize it every time. Save some time there
and also do this
int mex = 1;
memset(mp, 0, sizeof mp);
also to save some time
for(int i = 0; i < n; i ++) {
int mex = 1;
memset(mp, 0, sizeof (mp));
for(int j = i; j < n; j ++) {
if(a[j] < n)
mp[a[j]] = 1;
while(mp[mex])
mex ++;
ans += mex;
}
}
if(arr[j]<=n){
mp[arr[j]] = 1;
while(mp[maxx] and maxx<n+1){
maxx++;
}
ans+=maxx;
}
else{
ans+=maxx;
}
Instead of this do this
if(arr[j]<n){//updated
mp[arr[j]] = 1;
while(mp[maxx] ){//updated
maxx++;
}
ans+=maxx;
}
//remove else statement.
It won’t work…
Because if some number is greater than one… then also that can be a single subarray and for that subarray also… we have to calculate it’s contribution in final answer…
Look… Here…
https://www.hackerearth.com/submission/51657799/
It is showing wrong answer for all test cases.
Now submit this, its getting accepted
What i have found… is that if i am changing all int to long long int… then it is showing wrong answer… why is it so.
Even I don’t know cause int can be changed into long long int no issues in that. When we make long long int into it, that’s a problem. But what they are showing is wrong answer when we change int into long long int
Okay…
Thanks for all of this…
It means a lot for a begineer…
Thanks 
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.