Here in this CF problem my observations are —

1) There cannot be more paths than n-1

2)If you start going right from any cell , you cannot go upward or downward after its next cell. If the grids are -

A B C D E F G H I J

You cannot go — A->B->G ....

or A->F->G->H->C...

But I do not know how to proceed further.

In the tutorial they said about calculating prefixes , suffixes . But how these gonna help in handling the time of visiting a cell?

Hey wait ! please help , I want to learn to solve 1600-1800 problems within contest time. So help me :p