I need help to solve this problem from an ICPC Regional Contest
It's easy to find the MEX difference of the subarray [l:r] in O(1), F(l, r). but what makes it hard is to find the maximum MEX difference among all subarrays inside range l:r
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I need help to solve this problem from an ICPC Regional Contest
It's easy to find the MEX difference of the subarray [l:r] in O(1), F(l, r). but what makes it hard is to find the maximum MEX difference among all subarrays inside range l:r
Name |
---|
can you provide the link of this problem ?
https://codeforces.me/group/Rilx5irOux/contest/530057/problem/J
here is my code
feel free to ask me anything !
Thank you
What can i do if i am not allowed to see the contest? Really wanna upsolve this now(
you need to join this group in order to see the contest
ty!
my approach: first, absolute values are hard to work with so let's remove them by calculating the max value of
MEX(P,a,b) - MEX(Q,a,b)
over all a,b for a query (and similarlyMEX(Q,a,b) - MEX(P,a,b)
) and answer is the max of these 2now to maximize
MEX(P,a,b) - MEX(Q,a,b)
, let's think of a naive solution first: let's loop over all valuesX
whichMEX(P,a,b)
can be, and try to minimizeMEX(Q,a,b)
. Well observe that as you extend a subarray by 1 ([a,b] -> [a-1,b] or [a,b+1]) the mex can only increase, so we want to find the smallest subarray whereMEX(P,a,b)
equalsX
well this can be done with a simple loop:
first calculate index:
then something like:
finally we can observe that these "minimal-mex" subarrays in a can only increase in length, so for a query, we can binary search the largest mex for which that corresponding "minimal-length" subarray is contained in the query. And also store
MEX(P,a,b) - MEX(Q,a,b)
in an array, prefix-maxedThank You