When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

rum3r's blog

By rum3r, history, 3 years ago, In English

Just a small doubt regarding this problem.

Can anyone tell me why we are choosing m moves from a total of (n+m) moves to reach coordinate (x, y)?

  • Vote: I like it
  • +1
  • Vote: I do not like it

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

Suppose our coordinate is (x, y). Every time we move, we increase x + y by 3.

Thus, we will make (x + y) / 3 moves in order to reach (x, y).

Every time we move 1 tile right and 1 tile down. We don't choose that. What we choose is if we move 1 extra tile right or 1 extra tile down.

Suppose (x + y) / 3 = k. Then we need to choose to move extra tile down x — k times and extra tile right the rest of the times (which is equal to y — k times).

Now we're just left to choose which exactly times we will choose to go down. We can choose any set of x — k turns of total k turns. So the answer is either 0 or C_k_(x-k).