CF #86

Failed all submissions,
http://codeforces.ru/contest/113/problem/A
problem A, WA. Passed A offline. Too many places went wrong. Need to be more careful. The problem is straightforward.

1. check each word to be valid
2. if only one word, return true
3. get type=0 (adj), then type=1(noun), then type=2(verb)
if there are words remaining, return false
if both genders appear, return false
if count of type[1] is not 1, return false

return true if none of above apply.!


problem B, hacked
The problem asks for all distinct substring that has a given prefix and a given suffix. SPOJ has a similar problem asks for the number of distinct substr, with n=1000.

One idea is to use suffix array, and count each l=1,2,...,n distinct prefix. However this seems too slow. My implementation accepted when using MSVC++, but TLE in GNU C++ 4.6. Shocking enough, there are solutions run in 10ms, while mine is 1.40s under MSVC++.

A faulty implementation of naive string matching. A correct one is:

n=len(text); m=len(patt)
vector<int> ans;
for i=0 to n-1
{
  for j=0 to m-1
    if (i+j >= n || text[i+j] != patt[j]) break;
  if (j>=m) ans.push_back(i); // found a match
}
return ans;

problem C, know will TLE and it did.
You want to use Sieve of Eratosthenes but memory is an issue because N is 3x10^8. However bitset or vector<bool> fits in memory limit. Also optimizations for the sieve helps, when at elem=p, start marking at p^2 instead of 2p, and take increment of 2p instead of p.

The following number theory result might also help.

Fermat's theorem on sums of two squares
From Wikipedia, the free encyclopedia

In additive number theory, Pierre de Fermat's theorem on sums of two squares states that an odd prime p is expressible as
p = x^2 + y^2
with x and y integers, if and only if
p = 1 mod 4.

For the prime sieve method, a recent result by
Jonathan P. Sorenson, The Pseudosquares Prime Sieve
might also be of interest.