| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 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 |
This problem appeared in a Hiring Challenge on Hackerrank and i couldn't solve it in better than $$$O(N^2)$$$ which was giving TLE. Here is the problem below:
I can't think of a solution better than $$$O(N^2)$$$. Any help/hints will be appreciated.
Consider, that you will never be able to make a jump larger than $$$O(\sqrt{n})$$$. Using that, you can solve in $$$O(n\sqrt{n})$$$
makes sense. but $$$d$$$ can be greater than $$$√n$$$ ? How to handle that?
Ok I somewhat misread, but the solution remains the same. You can only make $$$O(\sqrt{n})$$$ types of jumps. So you can let $$$dp_{i,j}$$$, be the maximum gold you can get if the last jump was $$$d - offset + j$$$. offset should be somewhere around $$$2\sqrt{n}$$$, and $$$j$$$ should be from $$$0$$$ to $$$4 \sqrt{n}$$$.
Also can anyone tell me why am i getting downvotes? i am just curious to know.