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 = a₁, ..., a_n 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) = max_{1 ≤ j < i}f(j) + a_i 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 a_i. One can consider the elements in the order of their appearance. For element i, the algorithm finds the largest previous element v such that a_v < a_i (can be done using std::set::lower_bound) and we would have f(i) = f(v) + a_i. We then remove all elements f(k) where a_k > a_i, 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 :)

I participated in the codeforces educational round 4 and I liked problem E (Square Root of Permutation) that involves finding square root of a given permutation. The solution requires representing the permutation as a graph then decomposing this graph into cycles. Checking certain properties of these cycles such as the number of even cycles with the same length is the key point to finding a solution.

The idea of considering a permutation as a graph and mapping operations on the permutation to operations in the corresponding graph is very new and interesting to me. I tried to search in Google and Codeforces about other problems and explanations related to this concept but I was not able to find relevant stuff other than: Wikipedia article and a codechef problem. I wonder whether you can share some resources about this topic that you might have met during practice or suggest better keywords for finding relevant resources.