Statistics

Problem Statement for "Paths"

Problem Statement

Being second best usually warrants respect and some degree of popularity. Unfortunately, sometimes being second is worse than being last. This phenomenon can be seen in graph theory path-finding algorithms. No one ever seems to pay attention to second best paths! This is unfair and it leaves many almost optimal paths unseen. You wish to change all this by writing an algorithm that detects the second shortest path length in a directed graph, which is not equal to the optimal shortest path length. For the purpose of this problem, a path does not need to have distinct nodes and the length of a path is the sum of all edge weights from the starting node to the ending node. 
Write a class Paths that contains the method secondBest, which takes a String[] graph, int from and int to and returns the length of the second shortest path from the node from to the node to.  graph will contain digits that represent the weights of edges or 'X', which means there is no edge at all.  The jth character of the ith element in graph represents the weight of the edge from node i to node j (i and j are zero-indexed).  If no second best path exists, return -1.

Definition

Class:
Paths
Method:
secondBest
Parameters:
String[], int, int
Returns:
int
Method signature:
int secondBest(String[] graph, int from, int to)
(be sure your method is public)

Notes

  • The weight of an edge from node j to node i need not be the same as the weight of an edge from node i to node j.
  • Nodes may have an edge pointing to themselves with non-zero weights.

Constraints

  • graph will contain between 1 and 50 elements, inclusive.
  • Each element of graph will contain the same number of characters as the number of elements in graph.
  • Each element of graph may contain only digits or 'X'.
  • from will be between 0 and the number of elements in graph-1, inclusive.
  • to will be between 0 and the number of elements in graph-1, inclusive.

Examples

  1. {"01111", "10111", "11011", "11101", "11110"}

    0

    0

    Returns: 2

    In this case, the best path may be no path at all or any number of moves from node 0 back to itself. In either case, the best path is 0. The second best path has a length of 2 and can be achieved by moving from node 0 to any other node, and then back to node 0.

  2. {"1"}

    0

    0

    Returns: 1

    Since the starting node is the ending node, the best path is 0. The second best path is to move once from node 0 back to itself.

  3. {"X1119", "1X119", "11X19", "111X1", "9111X"}

    0

    4

    Returns: 3

  4. {"X1119", "1X111", "11111", "111X1", "9111X"}

    0

    4

    Returns: 3

  5. {"X1110", "1X111", "11111", "111X1", "0111X"}

    0

    4

    Returns: 2

  6. {"X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XX9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXX", "X999999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXX", "X9999999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXX", "X99999999999999999999999999X9XXXXXXXXXXXXXXXXXXXXX", "X999999999999999999999999999X9XXXXXXXXXXXXXXXXXXXX", "X9999999999999999999999999999X9XXXXXXXXXXXXXXXXXXX", "X99999999999999999999999999999X9XXXXXXXXXXXXXXXXXX", "X999999999999999999999999999999X9XXXXXXXXXXXXXXXXX", "X9999999999999999999999999999999X9XXXXXXXXXXXXXXXX", "X99999999999999999999999999999999X9XXXXXXXXXXXXXXX", "X999999999999999999999999999999999X9XXXXXXXXXXXXXX", "X9999999999999999999999999999999999X9XXXXXXXXXXXXX", "X99999999999999999999999999999999999X9XXXXXXXXXXXX", "X999999999999999999999999999999999999X9XXXXXXXXXXX", "X9999999999999999999999999999999999999X9XXXXXXXXXX", "X99999999999999999999999999999999999999X9XXXXXXXXX", "X999999999999999999999999999999999999999X9XXXXXXXX", "X9999999999999999999999999999999999999999X9XXXXXXX", "X99999999999999999999999999999999999999999X9XXXXXX", "X999999999999999999999999999999999999999999X9XXXXX", "X9999999999999999999999999999999999999999999X9XXXX", "X99999999999999999999999999999999999999999999X9XXX", "X999999999999999999999999999999999999999999999X9XX", "X9999999999999999999999999999999999999999999999X9X", "X99999999999999999999999999999999999999999999999X9", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}

    0

    49

    Returns: 459

  7. {"6X4XX50392", "95979050X4", "703X7X4218", "6602806624", "9828648374", "259507367X", "8810887807", "002378X847", "446X754724", "1128726659"}

    3

    3

    Returns: 1

    Random test case.

  8. {"19999", "99999", "99999", "99999", "99999"}

    0

    4

    Returns: 10

    The only way to get the 2nd best path is to move once from node 0 back to itself and then move directly to node 4.

  9. {"X11XX", "XXX1X", "XXXX1", "XXXX1", "XXXXX"}

    0

    4

    Returns: 3

  10. {"01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01XX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01X", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01", "1XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0"}

    2

    1

    Returns: 99

    A ring of 50 nodes, where every node also points back to itself with a weight of zero. The second best path is to go around the ring twice.

  11. {"X"}

    0

    0

    Returns: -1

    A second best path does not exist in this graph.

  12. {"09XXXXXXXX", "0099999999", "0009999999", "0000999999", "0000099999", "0000009999", "0000000999", "0000000099", "0000000009", "0000000000"}

    0

    9

    Returns: 27

    Cycles all over the place.

  13. {"0123456789", "9012345678", "8901234567", "7890123456", "6789012345", "5678901234", "4567890123", "3456789012", "2345678901", "1234567890"}

    0

    9

    Returns: 19

    At least 10 different optimal paths.

  14. {"01111111111111111111111111111111111111111111111111", "X0111111111111111111111111111111111111111111111111", "XX011111111111111111111111111111111111111111111111", "XXX01111111111111111111111111111111111111111111111", "XXXX0111111111111111111111111111111111111111111111", "XXXXX011111111111111111111111111111111111111111111", "XXXXXX01111111111111111111111111111111111111111111", "XXXXXXX0111111111111111111111111111111111111111111", "XXXXXXXX011111111111111111111111111111111111111111", "XXXXXXXXX01111111111111111111111111111111111111111", "XXXXXXXXXX0111111111111111111111111111111111111111", "XXXXXXXXXXX011111111111111111111111111111111111111", "XXXXXXXXXXXX01111111111111111111111111111111111111", "XXXXXXXXXXXXX0111111111111111111111111111111111111", "XXXXXXXXXXXXXX011111111111111111111111111111111111", "XXXXXXXXXXXXXXX01111111111111111111111111111111111", "XXXXXXXXXXXXXXXX0111111111111111111111111111111111", "XXXXXXXXXXXXXXXXX011111111111111111111111111111111", "XXXXXXXXXXXXXXXXXX01111111111111111111111111111111", "XXXXXXXXXXXXXXXXXXX0111111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXX011111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXX01111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXX0111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXX011111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXX01111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0"}

    0

    0

    Returns: -1

  15. {"01111111111111111111111111111111111111111111111111", "X0111111111111111111111111111111111111111111111111", "XX011111111111111111111111111111111111111111111111", "XXX01111111111111111111111111111111111111111111111", "XXXX0111111111111111111111111111111111111111111111", "XXXXX011111111111111111111111111111111111111111111", "XXXXXX01111111111111111111111111111111111111111111", "XXXXXXX0111111111111111111111111111111111111111111", "XXXXXXXX011111111111111111111111111111111111111111", "XXXXXXXXX01111111111111111111111111111111111111111", "XXXXXXXXXX0111111111111111111111111111111111111111", "XXXXXXXXXXX011111111111111111111111111111111111111", "XXXXXXXXXXXX01111111111111111111111111111111111111", "XXXXXXXXXXXXX0111111111111111111111111111111111111", "XXXXXXXXXXXXXX011111111111111111111111111111111111", "XXXXXXXXXXXXXXX01111111111111111111111111111111111", "XXXXXXXXXXXXXXXX0111111111111111111111111111111111", "XXXXXXXXXXXXXXXXX011111111111111111111111111111111", "XXXXXXXXXXXXXXXXXX01111111111111111111111111111111", "XXXXXXXXXXXXXXXXXXX0111111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXX011111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXX01111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXX0111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXX011111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXX01111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0"}

    0

    49

    Returns: 2

  16. {"01111111111111111111111111111111111111111111111111", "X0111111111111111111111111111111111111111111111111", "XX011111111111111111111111111111111111111111111111", "XXX01111111111111111111111111111111111111111111111", "XXXX0111111111111111111111111111111111111111111111", "XXXXX011111111111111111111111111111111111111111111", "XXXXXX01111111111111111111111111111111111111111111", "XXXXXXX0111111111111111111111111111111111111111111", "XXXXXXXX011111111111111111111111111111111111111111", "XXXXXXXXX01111111111111111111111111111111111111111", "XXXXXXXXXX0111111111111111111111111111111111111111", "XXXXXXXXXXX011111111111111111111111111111111111111", "XXXXXXXXXXXX01111111111111111111111111111111111111", "XXXXXXXXXXXXX0111111111111111111111111111111111111", "XXXXXXXXXXXXXX011111111111111111111111111111111111", "XXXXXXXXXXXXXXX01111111111111111111111111111111111", "XXXXXXXXXXXXXXXX0111111111111111111111111111111111", "XXXXXXXXXXXXXXXXX011111111111111111111111111111111", "XXXXXXXXXXXXXXXXXX01111111111111111111111111111111", "XXXXXXXXXXXXXXXXXXX0111111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXX011111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXX01111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXX0111111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXX011111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXX01111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0111", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX011", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX01", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0"}

    0

    1

    Returns: -1

  17. {"00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000"}

    0

    49

    Returns: -1

    Only optimal paths here.

  18. {"00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000001"}

    0

    0

    Returns: 1

  19. {"00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000009", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000008", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000006", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000005", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000004", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000003", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000002", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001", "00000000000000000000000000000000000000000000000001"}

    25

    25

    Returns: 1

  20. {"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}

    0

    49

    Returns: -1

  21. { "X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "XX9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXXX", "X999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXXX", "X9999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXXX", "X99999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXXX", "X999999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXXX", "X9999999999999999999999999X9XXXXXXXXXXXXXXXXXXXXXX", "X99999999999999999999999999X9XXXXXXXXXXXXXXXXXXXXX", "X999999999999999999999999999X9XXXXXXXXXXXXXXXXXXXX", "X9999999999999999999999999999X9XXXXXXXXXXXXXXXXXXX", "X99999999999999999999999999999X9XXXXXXXXXXXXXXXXXX", "X999999999999999999999999999999X9XXXXXXXXXXXXXXXXX", "X9999999999999999999999999999999X9XXXXXXXXXXXXXXXX", "X99999999999999999999999999999999X9XXXXXXXXXXXXXXX", "X999999999999999999999999999999999X9XXXXXXXXXXXXXX", "X9999999999999999999999999999999999X9XXXXXXXXXXXXX", "X99999999999999999999999999999999999X9XXXXXXXXXXXX", "X999999999999999999999999999999999999X9XXXXXXXXXXX", "X9999999999999999999999999999999999999X9XXXXXXXXXX", "X99999999999999999999999999999999999999X9XXXXXXXXX", "X999999999999999999999999999999999999999X9XXXXXXXX", "X9999999999999999999999999999999999999999X9XXXXXXX", "X99999999999999999999999999999999999999999X9XXXXXX", "X999999999999999999999999999999999999999999X9XXXXX", "X9999999999999999999999999999999999999999999X9XXXX", "X99999999999999999999999999999999999999999999X9XXX", "X999999999999999999999999999999999999999999999X9XX", "X9999999999999999999999999999999999999999999999X9X", "X99999999999999999999999999999999999999999999999X9", "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" }

    0

    49

    Returns: 459

  22. { "X1", "XX" }

    0

    1

    Returns: -1

  23. { "90X", "XX0", "5XX" }

    0

    0

    Returns: 5

  24. { "X1", "0X" }

    0

    0

    Returns: 1

  25. { "X1XXX", "XX13X", "XXX1X", "XXXX1", "XXXXX" }

    0

    4

    Returns: 5

  26. { "X13", "X2X", "XXX" }

    0

    2

    Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: