The Teleport Problem

Status
Live
Title
The Teleport Problem
Date
27 Sep, 2021 βΈ±
Excerpt
Published
Sep 27, 2021
Tags
lecturenotes
exposition
puzzles
exportober
Feature on homepage
This is an assignment problem from Getting Started with Competitive Programming.

The Problem.

You are given a string of length .
Each character of this string is a digit (that is, one of 0,1,…,9. )
You have to start from , and reach . To do so, you can make multiple teleports. From a particular , you can teleport to either or . You can also teleport to some , such that .
🎯 Find the minimum number of teleports needed to go from to .
Examples
  • If the string was 3953986745896309482303, then the answer would be 1.
  • If the string was 409583490585846, the answer would be 2.
  • If the string was 0123456789, the answer would be 9.

The Immediate Solution

A natural way to go about this is to setup a graph , where we have vertices , corresponding to the positions of the string, and the following edges:
  • for all
  • if and only if
It's not hard to check that a shortest path from to here corresponds to the smallest number of teleports required. However, can be as large as , which makes this untenable (in a CP context).
Here's why...
In particular, even if we use BFS to determine the shortest path here β€” note that the worst-case complexity of is , and there could be strings for which the corresponding graph does have edges, and so this nightmare scenario could actually manifest!
πŸ€” If you were writing the tests for this problem, what kind of strings would you include to rule out this first-cut BFS-based approach?

The Fix

With this realization β€” which could dawn upon us either from mulling things over or gentle TLE*-nudges β€” a natural next thought would perhaps be:
Perhaps we need to design a sparser graph that still has shortest paths in one-one correspondence with the teleporting mechanisms.
*Time Limit Exceeded βŒ›οΈ
Notice that the kind of situation that makes the previous construction dense, is, for example, a situation where all indices have the same digit β€” the graph in this case just turns out to be a complete graph! We want to model the idea that if two locations have the same index, then the graph makes note of that by providing some kind of a shortcut. A direct edge is the most natural kind of shortcut to provide, but as we see by now, it's kind of expensive.
Instead of this direct bridge, let's consider providing a passthrough via an intermediate vertex instead. So let's have ten designated fireplaces special vertices corresponding to the digits 0 to 9, and you probably see where this is going... your graph will now have the following edges:
  • for all
  • if and only if
It seems like a teeny change from the previous attempt, but it makes a massive difference. Ok, definitely a difference worth an order of magnitude! Notice that there are edges of the first kind and edges altogether of the second; and your graph now has edges altogether πŸŽ‰
notion image
But we're not quite done yet β€” with just this graph, you might be misguided by shortest paths from to . For example, think about what happens with the string 121. The direct hop is cheaper and involves one teleport, but the shortest path in our graph involves two edges and we'll end up reporting back a sub-optimal cost no matter which of the two shortest paths we pick.
The issue is that the passthrough isn't modelling cost of the teleport accurately β€” it is more expensive than it needs to be. To take the edge off of this, we need to discount traveling via the passthrough: a natural way to do this is to exercise the use of weights.
Have the edges of the second category cost half as much as those of the first, and then you'll truly be done. Any teleporting solution involving teleports now corresponds to a path of total cost , and conversely. And now you can use Dijkstra's algorithm, with a running time of combined with the fact that we are good to with respect to the constraint that .