Editorial for April Fools' Day Contest 2 P5 - Non-polynomial - Olympiads Online Judge

Editorial for April Fools' Day Contest 2 P5 - Non-polynomial

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: kevlu8

Notice that in the maximal case, $N = 5$ ~N = 5~ for all $10000$ ~10000~ cases. Since TSP can be solved in $O(n!)$ ~O(n!)~ naively, this gives us approximately $120$ ~120~ operations per test case. $120 \times 10000 = 1.2 \times 10^6$ ~120 \times 10000 = 1.2 \times 10^6~, which is feasible.

Comments

There are no comments at the moment.