| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
[submission:78417751]I have formed the recursive solution for the problem Heaters https://mirror.codeforces.com/contest/1066/problem/B. In order to optimise the solution I am trying to use memoization approach but stuck in defining the state for dp.
My solution — https://mirror.codeforces.com/contest/1066/submission/78417751
Thanks in advance!
I myself don't know a DP solution but I know a greedy solution.
Explanation: I choose the heaters to turn on and off greedily. For the first heater, I choose the furthest heater I can choose that can heat from the first sector. Do the same for the second heater,third,etc... Complexity can vary from O(n^2) to O(n) according to how you implemented the solution. The solution above that I implemented is O(n).
Thank you brother for this greedy approach. At last I have came with a dp approach in which 3 states are required and which will give the time complexity of O(n^3). So the greedy approach is best fo this question.
Also, another solution that I came with is using kind of DP or edited Cumulative sum, I could use segment tree with it for more optimization, but no need for the given constraints, the idea is to turn off the lights that has a minimum of at least 2 in it's range depending on r value, I just solved the problem and I enjoyed it a lot Here is a link to my solution... Code
Suppose you are at position i. then you need to check from i+r-1 to i-r+1 if there exits a heater or not.if you don't found any heater between this range then answer is -1. otherwise, choose the farthest heater from i in range i+r-1 to i-r+1. if your founded heater's location is k then your new i is k+r. see my code for more understanding. variable naming in the code is a bit different from what I mentioned here. I am bad at explaining and English.
I've taken a look at your solution. You have defined a 2D dp array but you did not use it anywhere in your code. Actually you are not storing the solutions.
Yes, bcz it is unable to store solution in 2D array, we require 3D array in this case and as I already mentioned in one of the previous comment that 3 states are required which is not possible with the given constraints. So, I have used greedy approach.