Editorial for Europe Tour

Prerequisites:

Explanation:

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

For example, imagine two different routes XX and YY in a case where N=5N = 5:

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

The first and last country in the both route is 11. But the countries in between ({3,5,4,2}\{3, 5, 4, 2\} for route XX and {5,2,4,3}\{5, 2, 4, 3\} for route YY) are permutations of each other. There is exactly (N1)!(N-1)! different possible routes in total, since there are (N1)!(N - 1)! permutations of countries {2,3,4,...,N1,N}\{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 0cost<M0 \leq cost < M, because we are taking the cost modulo MM. Notice that the value of MM is quite small, M200M \leq 200. So if we check 201201 different routes, there must be at least two different routes which have the same cost modulo MM (according to the Pigeonhole Principle). If we want to have three different routes with the same cost modulo MM, we have to check at most 401401 different routes. For N7N \geq 7, the number of different routes is (71)!=720(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 MM, 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 N7N \geq 7, we will have to check at most 401401 different permutations for the routes.

Complexity:

O(401P)=O(P)O(401 * P) = O(P) where PP 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)O(n).

Code:

    Statistics


    75% Solution Ratio

    YouKnowWhoEarliest, 3M ago

    YouKnowWhoFastest, 0.0s

    nskybytskyiLightest, 2.4 MB

    Deshi_TouristShortest, 1003B

    Toph uses cookies. By continuing you agree to our Cookie Policy.