Help pls!

Before contest

Codeforces Round 940 (Div. 2) and CodeCraft-23

3 days

Register now »

Codeforces Round 940 (Div. 2) and CodeCraft-23

3 days

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | ecnerwala | 3648 |

2 | Benq | 3580 |

3 | orzdevinwang | 3570 |

4 | cnnfls_csy | 3569 |

5 | Geothermal | 3568 |

6 | tourist | 3565 |

7 | maroonrk | 3530 |

8 | Radewoosh | 3520 |

9 | Um_nik | 3481 |

10 | jiangly | 3467 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 164 |

2 | awoo | 164 |

4 | TheScrasse | 160 |

5 | nor | 159 |

6 | maroonrk | 156 |

7 | -is-this-fft- | 150 |

7 | SecondThread | 150 |

9 | orz | 146 |

10 | pajenegod | 145 |

Help pls!

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2024 20:40:55 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

You can keep an array of Boolean values, with each index representing whether or not you have seen this number in the array. It will be of size n+1, since mex of n elements is at most n+1. Fill this array in with a O(n) loop over the array, and then go over the Boolean array and find the first false value, that index will be your mex.

please provide him code you dumb assss

u can simply use lower bound on the array instead of iterating all over. With a complexity of O(logn) insetad of O(n).

`lower_bound`

won't work because the array will not be of the form`[1,1,1, 0, 0, 0, ...]`

it can be something like`[1, 0, 1, 1, 1, 1, 1]`

Oh yeah u are right :)) Thats why i am newbie.

You can use cycle sort to put elements to it's corresponding index. Then traverse again and first element not equal to index is your mex.

Remember to ignore elements out of bound.

Time: O(N)

Space: O(1)

If there are $$$Q$$$ mex queries of ranges in an array lengthened $$$N$$$, then it can be solved in $$$O(Q\sqrt N+N)$$$ with Mo's algorithm.

in case of the given array is sorted, you can binary search on the first index that is not equal to it's value in the array, the answer will be that index. time

`O(logN)`

.codeBesides being sorted, the array should only have unique values.

this can be easily handled while taking the initial array.

codeIf you want to just find out the mex of the whole array, write a simple loop.

If you want to query the mex of an interval for many times, this problem may help. https://www.luogu.com.cn/problem/P4137

Sorry I don't know "可持久化线段树"'s English translation.

It is a persistent segment tree.

I think this video may be helpful. It is about different ways to find MEX of an array. From the simplest one to the most efficient

https://youtu.be/JDuVLyKn7Yw?si=CRqVObXm7JGdCMmg

if array is permutation of lenght N, and one value is missing, you can just find total sum = n*(n+1)//2 and then subtract each element of array from sum. Final value of sum is going to be your MEX.

Construct a hash array. Use Binary search and range query data structure such as minimum Sparse Table, check if in given range the minimum value is zero and accordingly update pointers.