Can anyone try to explain me how to solve this interesting problem.
http://www.spoj.com/SPOJ/problems/WALK1/
Thanks
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Can anyone try to explain me how to solve this interesting problem.
http://www.spoj.com/SPOJ/problems/WALK1/
Thanks
Name |
---|
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).