Need help with the following problem please; don't even know where/how to begin.

After the trauma of Dr. Boolean's lab, the rabbits are eager to get back to their normal lives in a well-connected community, where they can visit each other frequently. Fortunately, the rabbits learned something about engineering as part of their escape from the lab. To get around their new warren fast, they built an elaborate subway system to connect their holes. Each station has the same number of outgoing subway lines (outgoing tracks), which are numbered.

Unfortunately, sections of warrens are very similar, so they can't tell where they are in the subway system. Their stations have system maps, but not an indicator showing which station the map is in. Needless to say, rabbits get lost in the subway system often. The rabbits adopted an interesting custom to account for this: Whenever they are lost, they take the subway lines in a particular order, and end up at a known station.

For example, say there were three stations A, B, and C, with two outgoing directions, and the stations were connected as follows

Line 1 from A, goes to B. Line 2 from A goes to C.
Line 1 from B, goes to A. Line 2 from B goes to C.
Line 1 from C, goes to B. Line 2 from C goes to A.

Now, suppose you are lost at one of the stations A, B, or C. Independent of where you are, if you take line 2, and then line 1, you always end up at station B. Having a path that takes everyone to the same place is called a meeting path.

We are interested in finding a meeting path which consists of a fixed set of instructions like, 'take line 1, then line 2,' etc. It is possible that you might visit a station multiple times. It is also possible that such a path might not exist. However, subway stations periodically close for maintenance. If a station is closed, then the paths that would normally go to that station, go to the next station in the same direction. As a special case, if the track still goes to the closed station after that rule, then it comes back to the originating station. Closing a station might allow for a meeting path where previously none existed. That is, if you have

A -> B -> C

and station B closes, then you'll have

A -> C

Alternately, if it was

A -> B -> B

then closing station B yields

A -> A

Write a function answer(subway) that returns one of:

-1 (minus one): If there is a meeting path without closing a station

The least index of the station to close that allows for a meeting path or

-2 (minus two): If even with closing 1 station, there is no meeting path.
subway will be a list of lists of integers such that subway[station][direction] = destination_station.

That is, the subway stations are numbered 0, 1, 2, and so on. The k^th element of subway (counting from 0) will give the list of stations directly reachable from station k.

The outgoing lines are numbered 0, 1, 2... The r^th element of the list for station k, gives the number of the station directly reachable by taking line r from station k.

Each element of subway will have the same number of elements (so, each station has the same number of outgoing lines), which will be between 1 and 5.

There will be at least 1 and no more than 50 stations.

For example, if subway = [[2, 1], [2, 0], [3, 1], [1, 0]] Then one could take the path [1, 0]. That is, from the starting station, take the second direction, then the first. If the first direction was the red line, and the second was the green line, you could phrase this as: if you are lost, take the green line for 1 stop, then the red line for 1 stop. So, consider following the directions starting at each station.

0 -> 1 -> 2.
1 -> 0 -> 2.
2 -> 1 -> 2.
3 -> 0 -> 2.

So, no matter the starting station, the path leads to station 2. Thus, for this subway, answer should return -1.

If

subway = [[1], [0]]

then no matter what path you take, you will always be at a different station than if you started elsewhere. If station 0 closed, that would leave you with

subway = [[0]]

So, in this case, answer would return 0 because there is no meeting path until you close station 0.

To illustrate closing stations,

subway = [[1,1],[2,2],[0,2]]

If station 2 is closed, then station 1 direction 0 will follow station 2 direction 0 to station 0, which will then be its new destination. station 1 direction 1 will follow station 2 direction 1 to station 2, but that station is closed, so it will get routed back to station 1, which will be its new destination. This yields

subway = [[1,1],[0,1]]

Test cases

Inputs:
    (int) subway = [[2, 1], [2, 0], [3, 1], [1, 0]]
Output:
    (int) -1

Inputs:
    (int) subway = [[1, 2], [1, 1], [2, 2]]
Output:
    (int) 1

@ 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;
}

Real algorithms using STL

Depth-first search (DFS)

/** Is it a tree?
Sample input:
    3 2
    1 2
    2 3
*/
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

#define MAX 100000
#define all(v) (v).begin(),(v).end()
typedef vector<int> vi;
typedef vector<vi> vvi;

vvi W; //W stores the graph(Adjacency List)
vi V;  //Array for storing whether a node is visited or not
// A set to store all the vertices.It is used to check if all
// vertices are visited or not
set<int> s;
int v,e,v1,v2,temp;

void dfs(int i) {
    if(!V[i]) {
        V[i] = true;
        for_each(all(W[i]), dfs);
    }
}

bool check_graph_connected_dfs(int start_vertex) {
    V = vi(v+1, false);
    dfs(start_vertex);
    return find(V.begin()+1, V.end(), 0) == V.end();
}

void mprintf(int i)
{
    printf("%d ", i);
}

int main()
{
    scanf("%d%d", &v,&e);

    vi::iterator it[MAX];
    if(e!=v-1)
    {
        printf("NO\n");
        return 0;
    }

    W.resize(MAX);
    for(int i=0; i<MAX; i++)
    {
        it[i]=W[i].begin();
    }

    for(int i=0; i<e; i++)
    {
        scanf("%d%d", &v1, &v2);
        s.insert(v1);
        s.insert(v2);
        temp = v1;
        it[v1] = W[v1].insert(it[v1], v2);
        it[v2] = W[v2].insert(it[v2], v1);
    }

    if(check_graph_connected_dfs(temp))
        printf("YES\n");
    else
        printf("NO\n");

//    for_each(V.begin()+1, V.end(), mprintf);
    return 0;
}

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;
            }
...