It_Wasnt_Me's blog

How to solve last problem in last google kickstart round
By It_Wasnt_Me, 4 years ago, In English

Can anyone explain the solution of last problem in kickstart round B link to problem

It is really too hard ? Beacuse a lot of people didnt solve it

I have solved first subtask when h and w is less than 500 with direct dp solution Time complexity of this solution is W*H

But how to solve when H and W can be upto 1e5

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

The editorial/analysis is out on the problem page.

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think the most difficult part is to handle with large numbers. As explained in tutorial, the ans is the sum of the probability of reaching the target partial diagonals.

There are two major issues:

(1) you cannot calculate the $$$_nC_r$$$/$$$2^n$$$ directly as it can be as small as $$$2^{-10^5}$$$, will round to 0. Note $$$_nC_r$$$/$$$2^n$$$ is just a product of something and it is possible to calculate its log value.

(2) how to calculate $$$e^a + e^b + e^c + ... $$$? (as every value takes log in(1)) Does the order of addition important?

Spoiler
Spoiler
→ Reply