dario-dsa's blog

By dario-dsa, 10 years ago, In English

Can anyone try to explain me how to solve this interesting problem.
http://www.spoj.com/SPOJ/problems/WALK1/
Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

First, we can see that answer for (x, y) is same as answer to (abs(x), abs(y)).

Let's take H and V that H + V = N.

H — how many horizontal moves we will do (west and east). X <= H <= N.
We must reach point X in L left moves and R right moves, so
L + R = H
R — L = x
If we solve this equation, we get R = (H + X) / 2, L = (H — X) / 2.
Then, we need to count number of move-sequences (LR) of length H which have exactly L left moves and R right moves. It is C(H, L) = C(H, R).

V = how many vertical moves we will do (south and norh). Y <= V <= N.
There everything is same as above so U = (V + Y) / 2, D = (V — Y) / 2, and number of sequence is C(V, D)

So for every (H, V) we have a two sequences of lengths H and V. We should merge them and get the sequence of length N. But how? We have a sequence of length N, let's choose H of them and put there a first sequence. There will be N-H positions left which is equal to V.

I can't explain it more detaily because of my bad english, but I think code will do. My code.

UPD. C(N, K) can be found in O(log MOD).