I dream of being a grandmaster and practice almost every day. I record what I think in my Google sheet and It can help me summarize some knowledge points. Now I want to share the problems I solve every day in the future here to practice my English writing skills.
My plan is to solve 3 problems every day and the score is between $$$[2000, 2200]$$$. Below are the problems I solved today.
The key points are that:
We can easily calculate the prefix MEX from 0 to n — 1, so we can get the answer when the shift number is 0.
Now we need to think when we move the first number to the end, how the prefix MEX changes, I notice that if the first number is $$$x$$$, if the prefix MEX is bigger than $$$x$$$, it will change to $$$x$$$, and the last MEX will become n. So It looks like an interval assignment. We can use a Segment tree to solve it and we can use binary search in Segment tree to find the first index that its MEX is not smaller than $$$x$$$.
Solutuon: https://codeforces.net/contest/1905/submission/290262287
The key points are that:
When I play the sample, I notice the parity will depend on the parity of $$$x$$$ and $$$y$$$. So we can just use (0, 0), (0, 1), (1, 0), (1, 1) to represent all data.
I draw a relationship graph of these four states and I find actually (0, 0) and (1, 1) can be seen as one state, and (0, 1), (1, 0) can be seen as a state. If I jump from two same states, the parity will not change. If I jump from two different states, the parity will change.
Think very long minutes, I find the winning and losing states depend on which state has more numbers.
Solution: https://codeforces.net/contest/1903/submission/290291263
The key points are that:
First I think maybe I should deal with one interval in the string $$$t$$$ at the same time, which means the interval $$$[l, r]$$$, if $$$i\in[l, r - 1], t[i] <= t[i + 1]$$$ We can find the index that contains all chars of $$$t[l:r+1]$$$ in s, and remove all no needs chars and sort them and get what we want.
But I found it was wrong when I saw the last sample.
3 3
cba
acb
I notice that I can deal with just one character, and the problem can be solved.
Solution: https://codeforces.net/contest/1898/submission/290294906
