I'm having trouble understanding the solution given for the problem here: http://www.codechef.com/DEC11/problems/MOVES/
Given a square table sized $N \times N$ ($3 ≤ N ≤ 5000$; rows and columns are indexed from $1$) with a robot on it. The robot has a mission of moving from cell $(1, 1)$ to cell $(N, N)$ using only the directions "right" or "down". You are requested to find the number of different ways for the robot using exactly $K$ turns (we define a "turn" as a right move followed immediately by a down move, or a down move followed immediately by a right move; $0 < K < 2N-2$).
I do not understand the intuition behind the answer http://discuss.codechef.com/questions/4045/moves-editorial
Suppose that the robot always takes the "right" move at first. We could easily see that a way of robot reaching cell $(N, N)$ is just a set of cells in which the robot takes "turns". This set is chosen by selecting a combination of $K/2$ column indices and $(K-1)/2$ row indices among $N-2$ indices each dimension. It is easily computed by formula: $$\binom{K/2}{N-2}\binom{(K-1)/2}{N-2}$$
Why is this the answer?
Best Answer
The robot’s path from $\langle 1,1\rangle$ to $\langle N,N\rangle$ must consist of $N-1$ down steps and $N-1$ right steps; ignoring the constraint on the number of turns, they can be made in any order, so a possible path is simply a sequence of $2N-2$ steps, half of which are down, and half of which are right. We can represent such a path by a sequence of $2N-2$ symbols, half of which are $D$ and half of which are $R$. There is a turn every time two unlike symbols are adjacent, and we want to have $K$ turns. This means that any path must consist of $K+1$ blocks of identical symbols: it’s $\mathscr{B}_0\mathscr{B}_1\ldots\mathscr{B}_K$, where the total length of the string $\mathscr{B}_0\mathscr{B}_1\ldots\mathscr{B}_K$ of $R$s and $D$s is $2N-2$, $N-1$ of the symbols are $R$, $N-1$ of the symbols are $D$, and either
Let’s look at the first case, in which $\mathscr{B}_0$ is a block of $R$s. Let $m=\left\lfloor\frac{K}2\right\rfloor$; each of the blocks $\mathscr{B}_{2k}$ for $k=0,\ldots,m$ consists of $R$s. Let $b_k$ be the length of $\mathscr{B}_k$ for $k=0,\ldots,K$; then any solution in positive integers to the equation
$$b_0+b_2+b_4+\ldots+b_{2m}=N-1\tag{1}$$
is a possible distribution of the right steps. Similarly, the blocks of $D$s are the blocks $\mathscr{B}_{2k+1}$ for $k=0,\ldots,m$ if $K$ is odd, and for $k=0,\ldots,m-1$ if $K$ is even. You can check that if $m'=\left\lfloor\frac{K-1}2\right\rfloor$, in both cases these are the blocks $\mathscr{B}_{2k+1}$ for $k=0,\ldots,m'$. Thus, any solution in positive integers of the equation
$$b_1+b_3+b_5+\ldots+b_{2m'+1}=N-1\tag{2}$$
is a possible distribution of the down steps.
Counting these solutions is a standard stars and bars problem; for reasons explained reasonably clearly at the link, there are $\binom{N-2}m$ solutions in positive integers to $(1)$ and $\binom{N-2}{m'}$ to $(2)$. Each distribution of the $R$s into their $m+1$ blocks can be combined with any distribution of $D$s into their $m'+1$ blocks, so there are altogether
$$\binom{N-2}m\binom{N-2}{m'}=\binom{N-2}{\lfloor K/2\rfloor}\binom{N-2}{\lfloor(K-1)/2\rfloor}$$
paths with $K$ turns that begin with a right step. By symmetry there are the same number beginning with a down step, so the total number of paths with $K$ turns is
$$2\binom{N-2}m\binom{N-2}{m'}=2\binom{N-2}{\lfloor K/2\rfloor}\binom{N-2}{\lfloor(K-1)/2\rfloor}\;.$$