DIGJUMP... Some test cases

Problem: https://www.codechef.com/problems/DIGJUMP/

It would be helpful if someone could come up with a test case to prove my following approach wrong…

  1. Create an array int dis[N] that stores for each position ‘i’ the shortest distances from i’th digit to last digit of the number.

  2. Start from last position of number. If you come across a new digit at position ‘i’ then update dis[i]=N-i and for all other position ‘j’ such that num[i]==num[j] you update dis[j]=dis[i]+1.

  3. Example: Let num = 0 1 2 3 2 1 8 (spaces for clarity)

  4. For above number following iteration takes place:

i . dis[] = x x x x x x 0 (‘x’ means dis[i] is yet to be calculated)

                       ^

ii . dis[]= x 2 x x x 1 0

                    ^

( Shortest distance from last ‘1’ is 1 and for other ‘1’ its 2 (ie. ‘1’ (index 2) → ‘1’ (index 6) → ‘8’ (index 7) )

iii. dis[]= x 2 3 x 2 1 0 (Same explanation applies for digit ‘2’)

                  ^

iv. dis[]= x 2 3 3 2 1 0

                ^

v. dis[]= 6 2 3 3 2 1 0 (skip already updated positions of ‘dis[]’ array)

        ^
  1. Now we keep updating the ‘dis[]’ array until convergence is reached (ie. no more update takes place)

  2. The above step is done as follows: Keep iterating through the array.If you find an index such that dis[i] > dis[i+1] + 1 or dis[i] > dis[i-1]+1 then update dis[i] with min(dis[i+1],dis[i-1]) + 1. Check if for the same digit at some other position ‘j’, that dis[j]+1 < min(dis[i+1],dis[i-1]) + 1. In other words if it is better to jump directly to same digit at some other position or move to either of the adjacent digit.

  3. Eg: Let num: 0 2 7 3 4 2 7 8 (for illustration purpose only)

                      ^
    

    Suppose we are at digit ‘7’ then check if its better to jump to another ‘7’ (index 7) or move to digit ‘2’ or ‘3’. Its just like iterative relaxation of the ‘dis[]’ array. In our main array dis1 will change to 3.

ie. dis[] = 3 2 3 3 2 1 0

          ^

This happened because it was a better option to move the next digit the cost dis(2) + 1.

We do this util convergence is achieved ie. no more update takes place. Our final answer would be dis[0].

Don’t worry about the complexity. I implemented this in a very efficient manner using a super node for all digits. I would appreciate if anyone could point out mistake in this approach.

Link to implementation: https://www.codechef.com/viewsolution/10813073