maradonah's blog

By maradonah, history, 4 years ago, In English,

Hello,

During my practice, I wanted to solve the problem Div 2 343, D: Babaei and Birthday Cake. In summary, we are given a sequence A = a1, ..., an of n positive numbers and we should find a strictly increasing subsequence of this sequence with maximum sum. A straightforward dynamic programming solution defines a state f(i) as the maximum sum of an increasing subsequence ending at element i. f(0) = 0 and f(i) = max1 ≤ j < if(j) + ai for 1 ≤ i ≤ n. The editorial explains how to implement this dynamic programming solution using segment trees in O(n log n) time.

Another solution that is also well known is to use binary search with a little modified dp recurrence. One such recurrence is to define f(i) as the maximum sum of a strictly increasing subsequence whose end is at most ai. One can consider the elements in the order of their appearance. For element i, the algorithm finds the largest previous element v such that av < ai (can be done using std::set::lower_bound) and we would have f(i) = f(v) + ai. We then remove all elements f(k) where ak > ai, k < i and f(k) ≤ f(i).

I implemented the solution in C++ here. I tried to implement the solution in Java but I was not able to find a good equivalent of the std::set::lower_bound. The equivalent I know about is the ceiling method in TreeSet class however this method returns the value of the element other than an iterator to it. I wonder whether anybody knows an equivalent to std::set::lower_bound in Java.

Sorry for the long post :)

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

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

Auto comment: topic has been updated by maradonah (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    own implementation of lower_bound and upper_bound works faster and takes less memory

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

    That's really what I need.

    Thanks for highlighting it and sorry for missing it although being in the docs :)

    I tried this method and it works reasonably fast. The runtime of my new java submission is even slightly better than the one based in C++.