Europe Tour

Prerequisites:

• Pigeonhole Principle

• knowing how to check permutations of an array

• how modular arithmetic works

Explanation:

Every route starts and ends at country $1$, and between the starting country $1$ and ending country $1$, we must visit every other country ($2,...,N$). Notice that every pair of different routes have the same starting and ending country (country $1$) and the order of countries in between are permutations of each other.

For example, imagine two different routes $X$ and $Y$ in a case where $N = 5$:

$X = \{1, 3, 5, 4, 2, 1\}$ and $Y = \{1, 5, 2, 4, 3, 1\}$

The first and last country in the both route is $1$. But the countries in between ($\{3, 5, 4, 2\}$ for route $X$ and $\{5, 2, 4, 3\}$ for route $Y$) are permutations of each other. There is exactly $(N-1)!$ different possible routes in total, since there are $(N - 1)!$ permutations of countries $\{2, 3, 4, ..., N - 1, N\}$ i.e. countries in between the first and last country in a route.

The cost of each route will be $0 \leq cost < M$, because we are taking the cost modulo $M$. Notice that the value of $M$ is quite small, $M \leq 200$. So if we check $201$ different routes, there must be at least two different routes which have the same cost modulo $M$ (according to the Pigeonhole Principle). If we want to have three different routes with the same cost modulo $M$, we have to check at most $401$ different routes. For $N \geq 7$, the number of different routes is $(7 - 1)! = 720$, so we will always find three such routes.

So, the solution is to keep checking the cost of each and every route. While doing this, if we already find three routes with the same cost modulo $M$, we can just print the routes and be done. If we don’t find any such routes, there isn’t and solution for this, so the answer is No. Since it is always guaranteed to find an answer for $N \geq 7$, we will have to check at most $401$ different permutations for the routes.

Complexity:

$O(401 * P) = O(P)$ where $P$ denotes the number of operations needed to find the next permutation of a list. If we use the C++ STL next_permutation, the complexity becomes $O(n)$.

Code:

• Setter’s Solution by RobinHood3082
• Alternate Solution by bi11a1