arman_ferdous's blog

By arman_ferdous, history, 9 months ago, In English,

The problem link : 833B - The Bakery My TLE solution : 29511490

Definition of dp state: dp[s][p] means the maximum total value we can get from the p-th part by putting some amount of boxes starting from s.

And to calculate the number of distinct integers in a range I used a persistent segment tree. First I stored the previous occurance for each number. Then for any interval i to j I only need to see how many numbers in previous[i...j] are less than i. And that is where the persistent seg tree helped me.

So if I am not wrong then at the worst case the dp table will be fully filled so the complexity for the solve() function would be O(n*k*distinct_int_query) in this case it is O(n*k*log n). Building the segment tree at first will take O(n*log n). Afterwards updating for each element will take a total of O(n*log n)

So total complexity would be O(n*k*log n) right? Then why doesn't it pass? Why TLE???

P.S: Most likely I am wrong. So plz tell how to do the wrong thing right.

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

9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

You perform O(nlogn) operations on average to calculate a single dp value.

9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The total complexity isn't O(n*k*log n), it's O(n*n*k*log(n)).