Interestingly enough the problem can be solved with simple simulation. Just simulate the process, choosing random directions and random initial positions while you are within the time limit and you will get accepted. I really doubt this is the correct solution, so I was wondering what is the real one?
I've got WA#9. My algo is: first I generate the possible answers in both directions (strating from 1 and n) with algorithm from the previous problem, and with KMP I'm searching the input array for match, also I added special cases for 2 (1 1 and 2 2) and for 3 (2 2).
O(m) solution doesn't use them as well =) No, I was talking about general logic of my algorithm. Of course, it is incorrect to search for some predefined sequence in the answer. For example, for m=5 general algorithm gives sequence like 1 2 3 4 5 1 2 3 4 (or something like that), but possible answer is 2 2 4 4 4 4 3 2.
what if n = 10^5 and m = 10^5 sequence is like this 4 6 4 6 4 6 4 6 4 6 . . . I think at this test the length of failed pattern is 1 all the time and time is O(n, m) again. Or I didn't understand your previous massage rightly?