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.

If k is an odd number, then we can give this way: v1->v2->v1->v2->v1. And the back way is v1->v2->v1->v2->v1. It's the same way! So no matter what characters in v1->v2 and v2->v1 are.

If k is an even number, it's a little bit complex. For example, k=4. Assuming there is a solution, and the solution is: v1->v2->v3->v4. So the back way is: v4->v3->v2->v1. And the string is the same.
So we can found that v2->v3 and v3->v2 must be the same!
So string of v2->v3->v2->v3 must be same with string of v3->v2->v3->v2.

In summary, for k is an odd number, we find two vertices that can be directly connected. If k is an even number, find two vertices that can be directly connected and have the same letter.

Code:

Submission #114446213 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge