practicener's blog

By practicener, history, 5 weeks ago, In English

I am referring to ->https://codeforces.com/contest/1012/problem/C I could come up with O(n^3) solution-> Let dp[i][j]= minimum cost to build j houses in the first i hills. We iterate over the continuous segments, at the end points of which , we build the houses. That is -> if we are considering a segment 1...........i we can break it as 1......k-1 [ k..........i] However this will not fit in the constraints. The editorial is a bit too hard to understand. Can someone please suggest some way to reduce the complexity to O(n^2) . Thank you

Tags dp, div1
 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

You can achieve n^2 by maintaining prefix minimum of previous state in dp .

Also , O(n^3) fits the constraints as well.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Correct!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your reply. I now understand how to achieve the required O(n^2) complexity. But I am not too sure if O(n^3) will pass, I mean n can be upto 5000 . If it were let say about 500, then yeah, it would have passed