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.
See “Another Easy Solution” section in the editorial.Your method is similar to what is described there.
thanks a lot, I missed that part!
@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 : CodeChef: Practical coding for everyone
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??
@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.
@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 .
indeed, it would be interesting to see if someone can find a test case where this method doesn’t work.
beautiful solution, one of the best implementation of bfs
Actually I don’t understand last test case
My code output for this one(0123456754360123457) is 7…
Can anyone help me to understand this test case?
Thanks in advance
can u explain the last one?how can it be 5??
for last case follow this path(indexes in bracket):
0(0) -> 0(12) -> 6(11) -> 6(6) -> 7(7) -> 7(18).
@aayushagarwal: your code gives incorrect output for 348117304825225015142699765169, expected output is 5 and your solution gives 6.
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
@vaibhavatul47 : Thank you for the test case !
hey for “348117304825225015142699765169 . The expected output is 5” i am getting 5 also for this .
totally not sure why it is still saying WA
see the updated pseudo code.
also see my accepted submission http://www.codechef.com/viewplaintext/4111204
nice tutorial by dpraveen followed by crisp and self-explanatory implementation by vivek, makes it one of the bestest editorials.