We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Toll Cost Digits
  5. Discussions

Toll Cost Digits

  • ludovic_cleroux
     + 1 comment

    I have not yet found how to solve this within the time limit, but an interesting aside.

    Using DFS/BFS on a random start node, when the path reaches back to the start node, then interesting things happen.

    Any loop back to the starting node that ends with 

    loop with
- even number, will yield all possible even numbers
- odd number (except 5) will yield all possible odd numbers
- 5 will yield 0 and 5
- 0 yields 0

    So whenever a path circles back to the START, then you can mark all abovementioned paths as already visited. 

    Given START to START: [0,4]
# means that START->START can be reached on all even numbers [0,2,4,6,8]

Given START->NODE_A = [3]
# means that NODE_A can be reached from START_NODE with a path that end with [3]

# Because START can reach itself with paths ending with [0,2,4,6,8]
# Means we can reach START->NODE_A with [3] + [0,3,4,6,8] =  [3,5,7,9,11] = [ 3,5,7,9,1]

    Another interesting mechanic, is that

    - count of `1` paths = count of `9` paths
- count of `2` paths = count of `8` paths
- count of `3` paths = count of `7` paths
- count of `4` paths = count of `6` paths
- count of `5` paths NOT = count of `0` paths

    I'm trying this out right now, but i believe that you can calculate only the distances from a single node, then be able to infer the distances between all of the other nodes.

    (A,B) = [1]
(A,C) = [2]
then (BC) = (AC)+(BA) = [2] + [9] = [11] = [1]
-------
(A,B) = [1,2]
(A,C) = [3,4]
then (BC) = (AC)+(BA) = [3,4] + [1,2] = [3+1,3+4,4+1,4+2] = [4,7,5,6]
--------
(A,A) = [0,1]
(A,B) = [1,2]
(A,C) = [3,4]
(B,C) = (A,A)+(A,C)+(BA) = [0,1] + [1,2] + [3,4] = [0+1+3, 0+1+4, 0+2+3, 0+2+4, 1+1+3, 1+1+4, 1+2+3, 1+2+4]
= [4,5,5,6,5,6,6,7] = [4,5,6,7]