PROBLEM LINK:Tester: Shiplu Hawlader DIFFICULTY:Easy PREREQUISITES:bfs, dijkstra PROBLEM:Given a string s of N. You have to go from start of the string(index 0) to the end of the string (index N  1). From position i, you can go to next (i + 1) or previous (i  1) position. You can also move from the current position to the indices where the character is same as current character s[i]. QUICK EXPLANATION
EXPLANATIONFew observations
Wrong greedy strategies From the current position, go to the rightmost index having same character/digit as the current character/digit. If this number does not occur again in the right part of array, then go to next position (ie. i + 1). Please see the following recursive implementation of this strategy. Pseudo Code
The above strategy will fail in these kind of cases:
010000561 Wrong dp algorithm Note that this kind of dp solutions are wrong because they don't consider the moves going backwards (from position i to i  1), they are only considering the forward moves. A simple test case where they will fail. Bfs Solution So we can simply do a bfs from our start node(index 0) to end node(index n  1). Number of nodes in the graph are n, but the number of edges could potentially go up to N ^{ 2 } (Consider the case of all 0's, entire graph is a complete graph.). Optimized bfs Solution For a reference implementation, see Vivek's solution. Another Easy solution Let dp[i] denote the number of steps required to go from position 0 to position i. Before starting all the iterations, we will set dp[1] = 0 and dp[i] = infinity for all other i > 1. We can update the dp by following method. Here the term dp[i  1] + 1 denotes that we have come from previous position ie (i  1). Pseudo code:
Proof Complexity: AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 16 Jun '14, 15:01
showing 5 of 12
show all

Well the test cases for this problem are still weak . Here is my accepted solution . My code fails on this 348117304825225015142699765169 . The expected output is 5 whereas my code gives 6 as the answer . I was almost half sure whether my solution would pass or not but luckily it passed . Its really difficult to make tricky test cases which can fail wrong solutions . I would request the setter to update the test cases for this problem in the practice section if possible . answered 17 Jun '14, 02:19
i think the expected output should also be 6 and not 5. correct me if i m wrong(plzz provide the steps).
(25 Jun '14, 09:58)
1
indexes > 0>6,6>5,5>24,24>23,23>29 i.e 3>3,3>7,7>7,7>9,9>9 These are the five steps.
(25 Jun '14, 18:36)

We can solve it using a Dijkstra too without relying on the fact that the solution would be bounded by 20. Instead of interconnecting all nodes with the same digit value resulting in potentially ~V^2 edges, we create one super node for each digit from 0 to 9, and connect each digit with its corresponding super node with an edge of weight 0.5. We can thus move to and from same digit nodes in distance 1, which was exactly what was required. This results in ~V edges and we can run Dijkstra on the first node in VlogV time. Finally we can double all edge lengths to avoid floating points and divide the required distance by 2 at the end. answered 16 Jun '14, 17:11

My solution was accepted and uses dynamic programming. However because the solution is based on my intuition I'm not sure if understand whether or why it's 100% correct. let let Now we have to scan the array from left to right and then from right to left as many times as needed in order to calculate the final value for Initialization
First we scan it from left to right.
then we scan the array from right to left:
then again from left to right, right to left etc, until nothing changes in the array Basically I assume that the convergence to a solution is fast, however I have yet to think of a proof to this. answered 16 Jun '14, 16:20
1
See "Another Easy Solution" section in the editorial.Your method is similar to what is described there.
(16 Jun '14, 17:36)
thanks a lot, I missed that part!
(16 Jun '14, 17:47)
2
@picpunk : I used the same algorithm as yours but I scanned it only thrice i.e. first from left to right and then from reverse and again finally from front . I got AC with this approach and did not scan multiple times as you said . I would like to get a test case for which my solution will get fail because the test cases are still weak IMHO. Here's the link to my solution : http://www.codechef.com/viewsolution/4100953
(16 Jun '14, 18:08)
1
@aayushagarwal, my solution gets AC if we scan the array 3 times as well. I'm also not sure if this AC is due to weak test cases though.
(16 Jun '14, 18:11)
@kmampent : But in the editorial it is mentioned that at most we have to do 20 iterations because the maximum value can be 20 , perhaps there can be a test case which I am not able to deduce now .
(16 Jun '14, 18:42)
indeed, it would be interesting to see if someone can find a test case where this method doesn't work.
(16 Jun '14, 19:11)
@aayushagarwal: your code gives incorrect output for 348117304825225015142699765169, expected output is 5 and your solution gives 6.
(17 Jun '14, 00:55)
@vaibhavatul47 : Thank you for the test case !
(17 Jun '14, 02:15)
showing 5 of 8
show all

If you are finding "Wrong Answer" then try following testcase : 0998887776665554443322223300885577 Correct Ans > 5 Directions : 0,0(last occurrence),8(next),8(index:5),7(next),7(last) answered 16 Jun '14, 17:17

i have checked all the test cases given here for each one my code is giving correct output. can any one tell me for which test case it got failed.@admin...I think for this problem it will be helpful for many of us if test cases used for evaluation be made public. thanks answered 17 Jun '14, 11:00

Can you explain what is wrong with my dp solution. It gave right answer for your test case. I have implemented the dp such that it considers going backwards. include <iostream>include <string>include <cstring>include <climits>include <algorithm>using namespace std; int main() { int dp[100005]; string s; cin>>s; int len = s.size(); //cout<<s.size()<<endl; int mini[10]; memset(mini,1,sizeof(mini)); for(int i=0;i<len;i++) dp[i] = 100005;
} Please it will be great if someone can explain to me my mistake here. My approach is similar to Sergey's approach. My mini array does the same thing that the Q array does in his code answered 16 Jun '14, 15:44
1
7711965557423006 ur o/p: 6, correct o/p: 5
(16 Jun '14, 17:12)
@vaibhavatul47 Why is ans 5..?? 7 to 7(last 7)  1 7 to 5(left)  2 5 to 5(left)  3 5 to 5(left)  4 5 to 6(left)  5 6 to 6(last)  6 It cannot make a jump from '5' at index 8 to '5' at index 6 in 1 step because the problem states only (i1) backwards. Can you please explain..??
(19 Jun '14, 16:18)
...But we can move to the same digit anywhere in the list. That is the main thing in this problem!
(27 Jun '14, 21:37)

Hi All I used the BFS and dijsktra approach to solve the problem . It is working fine for all cases mentined above .Please have a look at it and would be grateful to let me know whch testcases it failed . Thanks :) answered 16 Jun '14, 16:24
hi all my code seems to be working for all the below test cases , 94563214791026657896112 ans > 4 12345178905 ans > 3 112 ans > 2 1112 ans > 2 4589562452263697 ans > 5 14511236478115 ans > 2 0123456754360123457 ans > 5 still it showed WA . any help is appreciated
(17 Jun '14, 01:18)
hey for "348117304825225015142699765169 . The expected output is 5" i am getting 5 also for this . totally not sure why it is still saying WA
(17 Jun '14, 13:10)
@shiplu can you please check y my code is giving WA . thanks
(18 Jun '14, 23:35)
@Praveen Dhinwa , can you please have a look at my code , looks like it is working for eacha nd every tes cases .
(30 Jun '14, 14:34)
@anisdube, your method of taking input is problematic.
(04 Jul '14, 02:11)

Great Observations. Used BFS for this question. i wish, if i had thought of this bfs optimisation before. great question answered 16 Jun '14, 15:46

Shouldn't the maximum number of moves be 19?
my solution is below can i know for which test case/cases it went wrong please....
https://ideone.com/iWZLna
I'm unable to access Author's solution, It is saying access denied.
how could the value of i start from 0 during updating dp[i]?I think the value of i should start from 1 in sereja psudo code.
Author's solution link is broken
Nice problem and an amazing tutorial. Lately there's been a decline in the quality of editorials but this one was certainly one of the best.
For a reference implementation, see one of the solutions in the references. ???
Where are the references?? Or Can anyone point me the solution using bfs??
beautiful solution, one of the best implementation of bfs
@jony, I have updated the link. @rishavz_sagar, Yes, you are right, Updated.
nice tutorial by dpraveen followed by crisp and selfexplanatory implementation by vivek, makes it one of the bestest editorials.
Can someone explain me that in Sergey Nagin's solution why are we iterating the loop 20 times . for (int it = 0; it < 20; it++)
I can understand that in each loop dp[i] gets updated and after some iterations we will get correct result . but how 20?
@dpraveen
I am trying to make it using BFS but I am not getting how the adjacency list of the graph will be generated.