Educational Codeforces Round #105 ABCDE ​Solutions

A. ABC String

Solution:

Obviously, a certain letter appears twice as often as the other two letters. But for the convenience of implementation, we only find the letter that appears the most and mark it as t.

Then, if this t itself is in the first place, then t is replaced with (; the other two letters are replaced with ).
Otherwise, the two letters are in the first place, which is (; t is ).
(Here we temporarily ignore the fact that t should be the last digit and it should be ), just pay attention to the above conclusion is correct.)

Based on the above conclusion, run a pair of brackets. Yes, if it matches, NO if it doesn’t match.

Code:

Submission #114375825 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Berland Crossword

Solution:

There are actually only two cases that will cause NO: one is to apply $n$, and the other is to apply $n-1$. We consider the number of grids that this side is forced to paint as $require[i]$, where $i=(0,1,2,3)$ represents the four directions of URDL.

So $(i+1) mod 4$ and $(i+3) mod 4$ can represent the sides on both sides of $i$.

Sort the four edges from largest to smallest.

If he wants to paint $n$, then $require[(i+1)%4]++$ and $require[(i+3)%4]++$ (the number of grids that are forced to be painted on the left and right sides) +1).

If you want to paint $n-1$, then $require[(i+1)%4]++$ and $require[(i+3)%4]++$ execute one of them. We execute our plan on the side with the more squares to be painted.

After that, check whether the planned number of paints meets the number of forced paints.

Code:

Submission #114377776 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. 1D Sokoban

Just a classic binary search problem. On the one hand, the implementation is a little complex. On the other hand, it needs binary search twice. So still funny.

Educational Codeforces Round #105 1D Sokoban - Binary Search
Solution:Classic binary search problem. We only consider the positive part. The negative part can be similar.

D. Dogeforces

Dynamic disjoint set is really funny. But not a complex problem.

Educational Codeforces Round #105 Dogeforces - Disjoint set + Construction
Solution:Sort the salary. We build a dynamic disjoint set. In the beginning, there only be n lower-level employees. And the father of these employees is empty.

E. A-Z Graph

This question may seem a very hard problem, but it is actually a simple one. Because the vertices can be repeated, it will quickly be equivalent to the simplest construction method.

Educational Codeforces Round #105 A-Z Graph - Graphs + Construction
Solution:It is obvious if the vertices can be repeated. Assuming there is a solution, there must be two edges v1->v2 and v2->v1.