rohit_1402's blog

Help needed to optimise the solution for Heaters (1066B)
By rohit_1402, history, 4 years ago, In English

[submission:78417751]I have formed the recursive solution for the problem Heaters https://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://codeforces.com/contest/1066/submission/78417751

Thanks in advance!

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply