8
$\begingroup$

The following problem (I'm paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics:

Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. They start in city $1$ and wish to end in city $N$.

All of them love driving, so they move in the following fashion:

  • Each day, they start in the city they ended at the previous day (city $1$ on the first day) and follow a path consisting of exactly five roads (i.e. they visit six cities and the first visited city is the last visited city of the previous day).
  • They may visit a city multiple times across multiple days, but they may not visit a city multiple times in the same day.
  • They can't stop in the middle of the path: if they visit city $N$ after using $k < 5$ roads on some day, they can't end their trip.

Find the shortest path needed to complete this road trip, or determine that it isn't possible. In the case that there are multiple shortest paths, find the lexographically smallest one when looking at only the sequence formed by the ($5k+1$)-th cities visited on the path (i.e. city $1$, ..., city $N$)

$N \leq 10^5$ and $M \leq 5 \cdot 10^5$.

The official problem statement can be found on the contest website (day 2 problem 2).

I haven't been able to find an efficient solution to this problem (from both asking others and searching online), and nobody solved it in the contest. I currently have no idea how to even approach it.

Is there an efficient algorithm to solve this problem, perhaps even for $k$ friends instead of five friends? Since $N$ and $M$ are so large, the algorithm should be linear or linearithmic (when implemented in C++, the code should run for at most 1s in the worst case).

$\endgroup$
25
  • 1
    $\begingroup$ @j_random_hacker I believe that the resulting graph could potentially have $\mathcal O(N^2)$ edges, so that would be too slow. Also, I believe that finding those edges would take something like $\mathcal O(N^5)$ time in the worst case (something like a neural net with five layers) due to the restriction of each day's path not being allowed to cross itself. $\endgroup$
    – Andi Qu
    Dec 29 '20 at 19:13
  • 1
    $\begingroup$ I think it may be related to the property of being planar: when either $K_{33}$ or $K_5$ are induced subgraphs, then the solution should always exist. Otherwise, the graph is planar, and it may be simpler to work with its cycles. $\endgroup$
    – user114966
    Dec 30 '20 at 0:43
  • 1
    $\begingroup$ @Dmitry A planar graph don't have $K_5$ or $K_{3,3}$ as minors, not only induced subgraphs. It's also not enough to answer yes/no, you should give shortest solution. Third, there is nothing about the graph being planar in the problem, is there? $\endgroup$
    – Pål GD
    Dec 30 '20 at 9:51
  • 3
    $\begingroup$ So I've been in contact with one of the competitors who knows the problem author, and apparently: 1) The author actually originally proposed a solution that ran in $\mathcal O(NM)$ time (rip) using "a meet in the middle approach with a lot of casework", and 2) "The optimal solution is probably a BFS with some really clever pruning, with linear complexity". I haven't been able to find the person who proposed the linear solution though :( $\endgroup$
    – Andi Qu
    Jan 4 at 19:45
  • 3
    $\begingroup$ To be honest, I'm not sure we are talking about a solvable problem. I've seen problems where test cases were simply too weak and therefore even an obviously infeasible solution went through. I don't intend to offend the authors, but the words "some really clever pruning" make me feel that this is the case here. $\endgroup$
    – user114966
    Jan 6 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.