Do you know any site where one can practice with problems from the Balkan Olympiad in Informatics? I already know http://www.spoj.com/OI/, which has a few BOI problems.

I recently read the article from PEG Wiki about the convex hull trick, which can be applied to speed up dynamic programming algorithms (Link to the website) . This optimisation can only apply when certain conditions are met. Surprisingly, at the end of the article I read that we can achieve a fully dynamic variant of the trick (meaning that there are no conditions of applicability) if we store the lines in a std::set. Although I have understood the approach mentioned, I always fail when I try to implement it. Could someone point me to an implementation of the dynamic convex hull trick, and some problems where I can practice it? Thanks in advance.

I have been studying the Rabin-Karp algorithm for string matching lately, and I am impressed with its simplicity and average efficiency. I learned that its best-case complexity is O(n), and that its worst-case complexity is O(nm). I would like to find a way to eliminate this worst-case scenario, but have an error probability. If the error probability is low enough, then I will be able to use it and assume that the result will always be correct (unless I'm extremely unlucky). Below there is some pseudocode which implements the rabin-karp algorithm:

1| rabin-karp(text, pat) {
2|   n = size(text), m = size(pat);
3|   text_hash = hash(text[1..m]), pat_hash = hash(pat[1..m]);
4|   for i=1 to n-m+1 {
5|     if text_hash = pat_hash
6|       if text[i..i+m-1] = pat         // this step takes O(m) time
7|         print "Index: " i;
8|     text_hash = hash(text[i+1..i+m]); // this is computed in O(1)
9|   print "done";

To achieve my goal, I have to eliminate line six. To be able to do that, I need to be sure that this will not affect the correctness of the algorithm too much. In other words, I need to be sure that my hash function will be good enough to make the error probability low, but I can't come up with something clever. Could somebody help me? Thanks in advance.