When the Jumps Chain For Ever
This is #2148 with the one forbidden thing allowed: jumps CHAIN.
A token starts on square 1 of a track of n squares. For each of the k rolls
r, in order:
if the current square plus r is GREATER than n:
the roll is wasted and the token does not move
otherwise:
the token moves to that square, and then keeps taking jumps for as long
as the square it is on starts one
That "keeps taking" can fail to stop. Two jumps pointing at each other, or any
cycle of jumps, send the token round for ever. If a roll ever starts a chain
that never ends, print -1 and nothing else, and stop: no final square, no
wasted count, and no later rolls.
Otherwise print the final square and the number of wasted rolls, as in
#2148.
``` n = 10, jumps 3 -> 7 and 7 -> 3, rolls 2 1 -> -1
the first roll lands on 3, which jumps to 7, which jumps to 3, for ever
n = 10, jumps 4 -> 9 and 9 -> 2, rolls 3 1 1 1 -> 3 0
roll 3: 1 + 3 = 4, then 4 -> 9 -> 2, and 2 starts nothing, so square 2 roll 1: 2 + 1 = 3, which starts nothing, so square 3 roll 1: 3 + 1 = 4, then 4 -> 9 -> 2 again, so square 2 roll 1: 2 + 1 = 3, so square 3, and nothing was ever wasted ```
## What most people try first
A while loop that follows jumps with no guard at all. On a cyclic input it
does not crash, it hangs, which in a judged run looks like a slow solution
rather than a wrong one. The second attempt is usually a step limit, say "give
up after a thousand jumps", which is a guess rather than a proof and answers
-1 on long legal chains.
## How many jumps a finite chain can have
There are at most m squares that start a jump, and a chain visits a square
that starts a jump at every step except the last. If the chain takes more than
m jumps, some jump-starting square has been visited twice, and from that
square the chain continues identically, so it is infinite. So:
follow at most m jumps; if an (m + 1)-th is needed, the chain is infinite
or, equivalently and more directly, mark the squares visited during THIS chain and declare an infinite chain the moment a marked square comes round again. Both are exact rather than a guess. The second is what the reference uses.
## The faster route, and why it is worth it
The chain starting at a square never changes, so resolving it once per square beats resolving it once per roll. Walk each square's chain, memoise the endpoint, and mark the squares whose chain is infinite:
end[s] = s if s starts no jump
end[s] = end[jump(s)] if that is already resolved
end[s] = INFINITE if s is reached again while resolving s
After one O(n + m) pass, each roll is one lookup. That is the second
implementation used to verify this problem, which also makes the two versions
genuinely different in shape rather than two spellings of the same walk.
## Why it is correct
Two claims.
That the infinite test is exact: a chain is a walk in the functional graph
whose nodes are squares and whose only edge out of s is the jump from s,
where squares with no jump have no outgoing edge. Such a walk either reaches a
square with no outgoing edge, and stops, or it never does, in which case it
visits infinitely many squares out of a finite set, so some square recurs.
Conversely if a square recurs, the walk from that square repeats what it did
before, so it never stops. Recurrence and non-termination are therefore the
same condition, which is why marking visited squares decides it exactly.
That memoising is sound: the chain from s is the chain from jump(s) with
one extra step at the front, so they have the same endpoint, and the same
infinite-or-not status. So a resolved value may be reused by every square that
jumps into it.
## The boundary that breaks a careless implementation
A roll that overshoots never starts a chain, so an input with a jump cycle on a
square the token can never land on is NOT -1. The -1 is decided by the
chains actually entered, not by whether the jump graph has a cycle anywhere.
One declared test has exactly that shape.
Clearing the visited marks between rolls matters: the same square may legally be the start of a finite chain on two different rolls.
## Cost
O(n + m) for the resolution pass and O(1) per roll, so O(n + m + k).
The per-roll walking version is O(k m) in the worst case, which also passes
at these limits.