GStnt's blog

By GStnt, history, 3 weeks ago, In English

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.

D. Cyclic MEX.

The key points are that:

  1. We can easily calculate the prefix MEX from 0 to n — 1, so we can get the answer when the shift number is 0.

  2. 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

E. Geo Game

The key points are that:

  1. 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.

  2. 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.

  3. 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

E. Sofia and Strings

The key points are that:

  1. 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.

  2. 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

  • Vote: I like it
  • +17
  • Vote: I do not like it