http://codeforces.com/contest/346/problem/B classical longest common string problem(LCS), dp algorithm classical string matching problem, kmp algorithm

solution: First,for LCS, dp[n][m]= dp[n-1][m-1] ;if two char match max(dp[n-1][m],dp[n][m-1]) ;if two char not match then, there is virus dp[n][m][k]= dp[n-1][m-1][k-1] ;if all three char match dp[n-1][m-1][fk] ;if only two char match, fk start over max(dp[n-1][m][k],dp[n][m-1][k]); dp[n][m][k] means the virus after k is all matched, so if k <0 then all virus matched, which is invalid.

for the equation dp[n][m][k]=dp[n-1][m-1][fk] ;if only two char match, fk start over just two char match, so the virus must has to start from the beginning, but may not real beginning. strA: BCBC strB: BCBC virus:ACBC when matching from the right to left, and meets (B,B,A), although matching failed at A, but there is still has a matching string of 'BC', we just not need to start from the real begining. Where to find the place for rematching?

Finally, we came to kmp. 0...k....j...n nxt[j]=k: the substring from [0,k] is the same as substring [j-k,j] for one j, k<j and k is the max.

http://codeforces.com/contest/364/problem/D description: a set A of positive integers, if all integers in A are divisible by g, (the max of g), g is called gcd of the set A. Then, if just at least half integers in A are divisible by g, (the max of g), g is called ghd of the set A. problem: give the set A, find its ghd.

since the set size if hugh n=10^6, and the integers in set A is huge too, ai=10^12, we could only use some algorithm with O(n) or O(nlogn) time.

there is one solution, let's say an integer set fac(x):any integer in fac(x) could divide x. fac(x) is a divisor set of integer x. First we find all fac(ai), and if there exist ghd, ghd is the element of fac(ai), at least half ai. Then, we just count the appearance times of all the divisor of all ai, if some divisor appearance at least (n+1)/2 times, then this divisor could be ghd. However, the size of fac(ai) is about 10^3, which O( 10^6 * 10^3 ) is TLE.

The following in this blog is the thought of a big guy, although I did not know who is the real author, I just want to share his idea of this problem.

Solution: we randomly get some integers in set A, for each ai, we calculate fac(ai), O(sqrt(ai)) times, and we just check the possible element in fac(ai) that could be the ghd, that is, for each divisor in fac(ai), check if it could divide at least half integers in set A. For one ai we choose, check all its divisor, and we select about 10 ai to check, then print the max ghd we find.

Why is it right? we just randomly check 10 integers in set A. Yes, it is right!

if we just miss the real max ghd, then this real max ghd must exist in at least half of fac(ai). so each time we randomly choose the ai to check, we has a possibility of 0.5 to miss it. And if for 10 times, we just all miss it, the possibility is 1/2^10, how small it is, we could hardly miss it.

This is the magic!

http://codeforces.com/contest/363/problem/D b1, b2, ..., bn (1 ≤ bi ≤ 104), p1, p2, ..., pm (1 ≤ pj ≤ 109), strategy one:if r bikes rented, correspondingly, then r person with max b,say set B; r bikes with min p, say set P. two:max b in B corresponds to max p in P,second-max b in B corresponds to second-max p in P, and so on.

so, if there are r bikes rented, we can use this strategy to calculate the min cost of share money, since some people may have b<p. for one r, we need O(r) time, that is O(n)

then: first, we need to know how many people could get bikes, since if we know r(number of bikes rented), we know the min cost of share money. So we can use binary search to find the max r, with O(nlogn) time.

second, if we fixed the max r, then we just need the strategy above to calculate the cost of all bikes, and the min cost of share money. then we could give the rest share money back to these boys. O(n) time.

total: O(nlogn)