You're right, man. Submitted correct solution in a few minutes, then thought about 1*2k case, if'ed it (of course, incorrectly) and got an unsuccessful challenge too.

Here's a quick sketch. Only consider the vertices v such that 0, 1 can reach v and v can reach 0, 1. Now for all primes k in the range 2 to 2000, try to color the graph in k-colors such that the following condition is satisfied: if we let c(u) denote the color of vertex u, then if u -  > v, c(v) = (c(u) + 1)(modk).

(u -  > v means that there is an edge pointing from u to v)

If this coloring succeeds, then the answer is Chores. If for all k it fails, the answer is Freedom. The proof for this is if the coloring succeeds, then all cycles in the graph must have length multiple of k, and this is bad.

Note: I'm the only person I know of who did anything similar to this. Most other solutions I saw or heard about found gcd of cycle lengths.

If there is a k-route with any big length, then clearly you can make a cycle starting in 0 and ending in 0 with any big length (by summing a k-path from 0-1, then a k-path from 1-0). This also works the other way around: if 0 and 1 are reachable from each other and you can make a 0-0 cycle with any big length, then you can use that cycle to make a 0-1 path with any big length, so you have a k-route with any big length.

Checking connectedness is easy, so now we only need to test whether we can make 0-0 cycles with any big length. It's a known result from number theory that this happens if and only if you can find cycles with lengths such that gcd(lengths) = 1. I don't know how to prove this formally, but you don't need to look that far -- if such a set of cycles exists, you can find it by checking for cycles up to a certain smallish length (around 6000 or so, maybe smaller) using BFS.

Yet another (although similar) idea is to find some cycle containing 0 (say of length c), and then run a BFS on an augmented graph, where we record for each node u and 0 ≤ i < c whether there is a path of length from 0 to u as can(u, i).

Then we only have to check whether can(1, i) for all i.

In 250, you needed a Hamiltonian path, not a Hamiltonian cycle ("Liz can begin and end on any cell", and also explanation to Example 2).

I believe my solution is not optimal, but anyway, here's the idea: K has at most d=240 divisors, and thus something with complexity O(N·d²) should pass

When k ≥ n², to check existence of a k-walk, it suffices to calculate GCD of lengths of all accessible cycles and length of path from 0 to 1.

For k < n², there is a trivial a O(km) solution simulating all steps. It may be possible to squeeze in the time limit with n and m up to 2000, as in the given problem, perhaps as some O(km / 32).

Actually, very similar problem just appeared at Polish contest Algorithmic Engagements. We were given an automata up to 200 nodes and were asked for any k such that all runs of length k are accepted (or state that it does not exist).

(Don't ask me about solution.)

0 недостижим из 1