Record what I solve in 2024-11-06

Revision en2, by GStnt, 2024-11-06 23:08:22

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 depends 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] and 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 find it's wrong when I saw the last sample.

3 3 cba acb

I notice that I can deal with just one char, and the problem can be solved.

Solution: https://codeforces.net/contest/1898/submission/290294906

Tags record

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English GStnt 2024-11-06 23:12:00 5 Tiny change: '[l, r - 1] and t[i] <= t' -> '[l, r - 1], t[i] <= t'
en4 English GStnt 2024-11-06 23:11:02 0 (published)
en3 English GStnt 2024-11-06 23:10:45 52
en2 English GStnt 2024-11-06 23:08:22 1299
en1 English GStnt 2024-11-06 22:54:54 1354 Initial revision (saved to drafts)