| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
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.