Hi Codeforces Community,

I recently learnt about segment trees and enjoyed it a lot. Right now, I am trying to solve a problem http://www.spoj.com/problems/MKTHNUM/.

The approach I used was to build the segment tree but maintain a sorted array at each segment. Afterwards, for each query [L, R], I got all the disjoint segments that form [L, R] and merged them recursively in order to answer query. I realize that there is a faster way to answer each query in lgn, (lgn)^2 times. I also think it is related with persistent segment tree.

I have tried to access Anudeep's tutorial on it but it is not loading. Please can someone help with an example or idea of how Persistent segment trees work?

Thank you.

Hi guys,

I am familiar with the Z algorithm for exact string matching.

However, is there a way to do this without using the sentinel

which is commonly #?

An idea i have is if m is the length of the pattern and n the length of the text, then we can do this

let S = P+T compute Z table

since the pattern is of length n, start iterating from i = m to i = n+m-1 if Z[i] >= m then we have a match at i. Is this correct?

i

Hi guys,

Is anyone aware of the songs that were playing in the background of the google code jam finals live stream.?

If you have it please share if not and you would like to, indicate so that i can send to you email once i do.

Hi guys,

I have done some thinking about how to solve 2nd best Minimum Spanning Tree. I want to hear your suggestions on if its correct and how you would solve it. Thanks.

Let G = (V,E) be a graph. Lets assume we know how to solve the MST using Kruskal as that is trivial. At each step of Kruskal, consider an edge e=<a,b>.

If e does not cause a cycle then it is in MST Otherwise It can cause a cycle. Now consider all edges in such a cycle and take the biggest edge in the cycle e1.

Claim : If we maintain the value (e-e1) and minimize it over all cases where adding an edge will introduce a cycle then we would have the 2nd best MST by simply replacing e1 with e.

Is this true ? How would you solve this problem ?

Thanks.

Hi guys,

Can anyone share their ideas over searching over a non-monotonic range. Is there a way that the basic binary search implementation can be modified to handle non-monotonic ranges?

Please assist with your ideas and thought/techniques.

Thank you