arman_ferdous's blog

By arman_ferdous, history, 7 years ago, In English

The problem link : 833B - Кондитерская 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

»
7 years 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.

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