| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
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
The editorial/analysis is out on the problem page.
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?
Sure. Assume a poor accuracy precision. $$$0.5+1^{-10}+1^{-10}+...+1^{-10}$$$ may gives you $$$0.5$$$ meanwhile $$$1^{-10}+1^{-10}+...+1^{-10} + 0.5$$$ may gives you something $$$>0.5$$$
A possible solution is to store a multiset, then every time pop the two smallest element, sum it and push into the multiset.