| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 144 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 136 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
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.