Codeforces Round #719 Solutions

A. Do Not Be Distracted!

Solution:

Scan the string. When we found a new letter, we skip the continually same letter. And mark this letter should not present again. If it presents again, then output "NO".

Code:

B. Ordinary Numbers

Solution:

Construct beautiful numbers within 9 digits from 1-9. Count the number if it less than n.

Code:

C. Not Adjacent Matrix

Solution:

Fill in the numbers along the diagonal. Take $ n = 5 $ as an example:

Code:

D. Same Differences

Solution:

Transform the equation, then we get $a_j - j = a_i - i$. So, scan the array, count the number of every $a_x - x$. And calculate the sum of $C_n^2$.

Code:

E. Arranging The Sheep

In fact, it depends on how many sheep go to the left and how many sheep go to the right.

F. Guess the K-th Zero (Easy/Hard Version)

Binary search. Query the range $[1,mid]$. But it will change the number in hard version. And we need plus one for some of our caches. So, of course, it's a segment tree problem.

G. To Go Or Not To Go?

I solved similar problem before. Do BFS from starting and ending point first. Then we consider if use the transport portal or not. I remember last time, I also get TLE by using Dijkstra.