@ http://comeoncodeon.wordpress.com/2010/08/29/the-z-algorithm

bool zAlgorithm(string pattern, string target)
{
    string s = pattern + '$' + target ;
    int n = s.length();
    vector<int> z(n,0);
     
    int goal = pattern.length();
    int r = 0, l = 0, i;
    for (int k = 1; k<n; k++)
    {
        if (k>r)
        {
            for (i = k; i<n && s[i]==s[i-k]; i++);
            if (i>k)
            {
                z[k] = i - k;
                l = k;
                r = i - 1;
            }
        }
        else
        {
            int kt = k - l, b = r - k + 1;
            if (z[kt]>b)
            {
                for (i = r + 1; i<n && s[i]==s[i-k]; i++);
                z[k] = i - k;
                l = k;
                r = i - 1;
            }
        }
        if (z[k]==goal)
            return true;
    }
    return false;
}

map → vector

map<string, int> M;
vector< pair<string, int> > V(all(M));

• sort order of vector elements same as map
• useful to access elements by their indices

copy

copy(from_begin, from_end, to_begin);

• copies elements from 1st interval to 2nd
• 2nd interval should have sufficient space
• from_{begin,end} can be .r{begin,end}()

vector<int> v1, v2;
v1.resize(v1.size() + v2.size());
// v1 = (original v1) + (v2)
copy(all(v2), v1.end() - v2.size());

+inserters

vector<int> v;
set<int> s;
// add some elements to set...
copy(all(v), inserter(s));
/* equivalent to:
	tr(v, it) {
		s.insert(*it);
	}
*/

• to insert elements to vector with push_back, use back_inserter
• front_inserter available for deque

Vector: []++

Declaration

• empty vector: vector<int> v;
• array of 10 vector<int>s: vector<int> v[10];
• vector with 10 int elements: vector<int> v(10);

Initialisation

vector<int> v1;
// …
vector<int> v2 = v1;   // make a copy?
vector<int> v3(v1);   // identical to v2's init
// …
vector<int> v4(1000);   // specific size: 1000 0's
// …
vector<int> v5(20, "Unknown");   // initial value
// …
vector<int> v6(v1.begin(), v1.end()); // [begin,end)
int data[] = { 1,2,3,…,8,9 };
vector<int> v7(data, data+(sizeof(data)/sizeof(data[0]))); // data+length=.end()
vector<int> v8(v1.begin(), v1.begin()+(v1.size()/2)); // 1st half of v1
// 1st half of v1, ordered back-to-front
vector<int> v9(v1.rbegin()+(v.size()/2), v.rend());

There are 10C2=45 ways to assign pairs (x,y) — note that order is not important here, because x,y together represent the 2 digits allowed in the number. Take special care when either one is 0.

If neither are 0, there are 2^k lucky numbers that are k digits containing those numbers. If x is 0, then it's 2^(k-1). But this double counts the numbers if x=y.

a=10^k (ie. k 9's): # =9x2^(k-1)-9+36x2^k-36 -9k =81x2^(k-1)-45-9k (*)

We subtract 9k because that is precisely the number of lucky numbers containing only 1 digit

Thereafter, the only necessary consideration left is the last segment of lucky numbers from a to n, all of which are k digits long.

For example, in the given test case, n=123, ans=113.

a=100=10^2=02 x 9's (as in '99') => k=3

By (*), k=2: #=99; k=3: #=252

There are 99 lucky numbers between 1 and 99 inclusive.

Between a=100 <= n=123, there are 3+9+2=14 more lucky numbers, specifically as follows:

• 100,101,110
• 111 — 119
• 121, 122

Ternary Search

This search finds the min or max in an array that is either strictly increasing and then decreasing or strictly decreasing then stricly increasing.

// array, left bound, right bound, abs(precision) value for array
int ternarySearch(int data[], int left, int right, int precval) {
  if (right - left < precval)
    return (left + right)/2;
   
  // Variable to store first 1/3 of array
  int first_third = (left * 2 + right) / 3;
  // Variable to store last 1/3 of array
  int last_third = (left + right * 2) / 3;
   
  if (data[first_third] < data[last_third])
    return ternarySearch(data, first_third, right, precval);
  else
    return ternarySearch(data, left, last_third, precval);    
}

250C. Movie Critics @ 2677682

• minimise sequence & eliminate consecutive duplicates in O(n), eg. 1 1 2 3 2 3 3 1 1 3 -> 1 2 3 2 3 1 3

	vector<int> as;
	vector<int>::const_iterator it;
	it = unique(as.begin(), as.end());
	as.resize(it - as.begin());

• For each number, if the two numbers beside it are the same, then excluding this number will get 2 fewer stress; otherwise, there will be only 1 fewer stress. For the first one and the last one, excluding these two numbers will always get 1 fewer stress.

	printf("%d",(int) (max_element(ks,ks+k)-ks+1));

_**Remember to consider 1-based and 0-based indexing schemes_

250D. Building Bridge @ 2680964

...
	int aid = lower_bound(A,A+n,ay) - A; // offset
...

250E. Mad Joe @ 2681020

...
            switch (getchar()) {
                case '.':break;
                case '+':a[i][j]=1;break;
                case '#':a[i][j]=2;break;
            }
...