Блог пользователя It_Wasnt_Me

How to solve last problem in last google kickstart round
Автор It_Wasnt_Me, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

The editorial/analysis is out on the problem page.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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
→ Ответить