Algorithm Collection

// RecPermute("", "abcd") triggers calls to:

// RecPermute("a", "bcd"), RecPermute("b", "acd"), RecPermute("c", "abd"), RerPermute("d", "abc").

// Total: N!

//

void RecPermute(string soFar, string rest)

{

    if( rest == "" ) {

        cout << soFar << endl;

    }

    else {

        for( int i=0 ; i<rest.length() ; i++ ) {

            string next = soFar + rest[i];

            string remaining = rest.substr(0, i) + rest.substr(i+1);

            RecPermute(next, remaining);

        }

    }

}

void ListPermutations(string s)

{

    RecPermute("", s);

}

// RecSubsets("", "abcd") triggers call to:

// RecSubsets("a", "bcd") (subsets include "a") and RecSubsets("", "bcd") (subsets without "a").

// Total: 2^N (each element has 2 possibilities of INCLUDED or NOT-INCLUDED.)

//

void RecSubsets(string soFar, string rest)

{

    if( rest == "" ) {

        cout << soFar << endl;

    }

    else {

        RecSubsets(soFar+rest[0], rest.substr(1));

        RecSubsets(soFar, rest.substr(1));

    }

}

void ListSubsets(string s)

{

    RecSubsets("", s);

}

function [maxtab, mintab]=peakdet(v, delta, x)

%PEAKDET Detect peaks in a vector

%        [MAXTAB, MINTAB] = PEAKDET(V, DELTA) finds the local

%        maxima and minima ("peaks") in the vector V.

%        MAXTAB and MINTAB consists of two columns. Column 1

%        contains indices in V, and column 2 the found values.

%     

%        With [MAXTAB, MINTAB] = PEAKDET(V, DELTA, X) the indices

%        in MAXTAB and MINTAB are replaced with the corresponding

%        X-values.

%

%        A point is considered a maximum peak if it has the maximal

%        value, and was preceded (to the left) by a value lower by

%        DELTA.

% Eli Billauer, 3.4.05 (Explicitly not copyrighted).

% This function is released to the public domain; Any use is allowed.

maxtab = [];

mintab = [];

v = v(:); % Just in case this wasn't a proper vector

if nargin < 3

  x = (1:length(v))';

else

  x = x(:);

  if length(v)~= length(x)

    error('Input vectors v and x must have same length');

  end

end

if (length(delta(:)))>1

  error('Input argument DELTA must be a scalar');

end

if delta <= 0

  error('Input argument DELTA must be positive');

end

mn = Inf; mx = -Inf;

mnpos = NaN; mxpos = NaN;

lookformax = 1;

for i=1:length(v)

  this = v(i);

  if this > mx, mx = this; mxpos = x(i); end

  if this < mn, mn = this; mnpos = x(i); end

  if lookformax

    if this < mx-delta

      maxtab = [maxtab ; mxpos mx];

      mn = this; mnpos = x(i);

      lookformax = 0;

    end 

  else

    if this > mn+delta

      mintab = [mintab ; mnpos mn];

      mx = this; mxpos = x(i);

      lookformax = 1;

    end

  end

end

    private boolean isRowAllMatchExist(boolean[][] edgeTable)

    {

        final int NUMROW = edgeTable.length;

        final int NUMCOL = edgeTable[0].length;

        if(NUMROW>NUMCOL) return false;

        // SetA's nodeID is [0, NUMROW-1]. SetB's nodeID is [NUMROW, NUMROW+NUMCOL-1].

        int[] residual = new int[NUMROW+NUMCOL];

        final int UNMATCH = -1;

        for(int i=0 ; i<residual.length ; i++) residual[i] = UNMATCH;

        for(int srcID=0 ; srcID<NUMROW ; srcID++) {

            boolean[] visited = new boolean[residual.length];  // Initialized to false.

            // from[nodeID] stores the node ID from where we reach this nodeID.

            int[] from = new int[residual.length];

            Queue<Integer> idqu = new LinkedList<Integer>();

            visited[srcID] = true;

            for(int j=0 ; j<NUMCOL ; j++)

                if (edgeTable[srcID][j]) {

                    idqu.add(j+NUMROW);

                    from[j+NUMROW] = srcID;

                }

            while(!idqu.isEmpty()) {

                int where = idqu.remove();

                visited[where] = true;

                if(NUMROW<=where && where<(NUMROW+NUMCOL)) {

                    if(UNMATCH==residual[where]) {

                        // Trace back the path and update the residual network.

                        int fromID = from[where];

                        residual[where] = fromID;

                        residual[fromID] = where;

                        while(fromID!=srcID) {

                            where = fromID;

                            fromID = from[where];

                            if(where<NUMROW) continue;

                            residual[where] = fromID;

                            residual[fromID] = where;

                        }

                        break;

                    }

                    else {

                        // Keep finding augmenting path, using residual network.

                        int next = residual[where];

                        if(!visited[next]) {

                            idqu.add(next);

                            from[next] = where;

                        }

                    }

                }

                else {

                    // Keep finding augmenting path, using the relation matrix.

                    for(int j=0 ; j<NUMCOL ; j++) {

                        if (edgeTable[where][j]) {

                            int next = j+NUMROW;

                            if(!visited[next]) {

                                idqu.add(next);

                                from[next] = where;

                            }

                        }

                    }

                }

            }

            int matchCount = 0;

            for(int i=0 ; i<NUMROW ; i++)

                if(residual[i]!=UNMATCH) matchCount++;

            if(matchCount!=srcID+1) return false;

        }

        return true;

    }

typedef pair<double, double> dd; 

const double epsilon = 1e-6;

struct sort_by_polar_angle { 

       dd center; 

       // Constuctor of any type 

       // Just find and store the center 

       template<typename T> sort_by_polar_angle(T b, T e) { 

            int count = 0;

            center = dd(0,0); 

            while(b != e) { 

                        center.first += b->first;

                        center.second += b->second;

                   b++; 

                count++;

            } 

                   double k = count ? (1.0/count) : 0;

            center.first *= k;

                   center.second *= k;

       } 

 // Compare two points, return true if the first one is earlier 

 // than the second one looking by polar angle 

 // Remember, that when writing comparator, you should 

 // override not ‘operator <’ but ‘operator ()’ 

       bool operator () (const dd& a, const dd& b) const { 

            double p1 = atan2(a.second-center.second, a.first-center.first); 

            double p2 = atan2(b.second-center.second, b.first-center.first); 

            return p1 + epsilon < p2; 

       } 

 }; 

 // ... 

 vector<dd> points; 

 // ... 

       sort(all(points), sort_by_polar_angle(all(points))); 

public class PointInPolygon {

    public PointInPolygon() {}

    private final class coord {

        private final int x;

        private final int y;

        private coord(int x, int y) { this.x = x;  this.y = y; }

        @Override public String toString() {

            return "(" + x + "," + y + ")";

        }

    }

    public String testPoint(String[] vertices, int testPointX, int testPointY)

    {

        final int NUMVERT = vertices.length;

        coord[] vertcoord = new coord[NUMVERT];

        // Parse the vertices to get vertices' coordinates.

        for(int i=0 ; i<NUMVERT ; i++) {

            String[] vertstr = vertices[i].trim().split("\\s+");

            vertcoord[i] = new coord(Integer.parseInt(vertstr[0]), Integer.parseInt(vertstr[1]));

        }

        // Ray cast started from testPoint to the right (increase x).

        // If cross odd number of polygon, then it is inside. Else it is outside.

        int cn = 0;  // crossing number

        for(int i=0 ; i<NUMVERT ; i++) {

            coord v0 = new coord(vertcoord[i].x, vertcoord[i].y);

            coord v1 = new coord(vertcoord[(i+1)%NUMVERT].x, vertcoord[(i+1)%NUMVERT].y);

            // For horizontal edge, check whether on boundary only.

            if( (v0.y==v1.y)) {

                if( (testPointY==v0.y) &&

                        (((v0.x<=testPointX) && (testPointX<=v1.x)) || ((v0.x>=testPointX) && (testPointX>=v1.x))) )

                    return "BOUNDARY";

            }

            // For vertical edge, check whether on boundary and also count the crossing.

            else {

                // Here, be careful with the equality! This is to check the case where the rightward-horizontal ray touch the tip!

                if( (((v0.y<testPointY) && (testPointY<=v1.y)) || ((v0.y>=testPointY) && (testPointY>v1.y))) ) {

                    if(v0.x==testPointX) return "BOUNDARY";

                    if(testPointX < v0.x) cn++;

                }

            }

        }

        if(cn%2 == 1)

            return "INTERIOR";

        else

            return "EXTERIOR";

    }

}

        int combinationNum = 0;

        for(int aa=0 ; aa<6 ; aa++)

            for(int bb=aa+1 ; bb<6 ; bb++)

                for(int cc=bb+1 ; cc<6 ; cc++)

                    combinationNum++;

std::vector<int> PrimeFactorization(const int n) {

    std::vector<int> ret;

    int pn = n;

    int a = 2;

    while(pn >= a*a) {

        if(pn%a == 0){

            ret.push_back(a);

            pn = pn/a;

        }

        else

            a++;

    }

    ret.push_back(pn);

    return ret;

}

#include <iostream>

#include <vector>

#include <algorithm>

#include <numeric>

#include <time.h>

template <typename T>

class CHeapSorter {

private:

    std::vector<T>& data;  // In-place sort (so, use reference). Heap sort does NOT need additional storage.

    int n;

private:

    CHeapSorter(std::vector<T>& indata) : data(indata), n(static_cast<int>(indata.size())) {}

    virtual ~CHeapSorter() {}

    CHeapSorter();

    CHeapSorter(const CHeapSorter&);

    CHeapSorter& operator= (const CHeapSorter&);

private:

    void siftdown(int nodeidx) {

        T tmp;

        int parent = nodeidx;

        int child = 2*nodeidx + 1;  // left child

        while ( child < n ) {

            if ( child+1 < n) {

                if ( data[child] < data[child+1] )

                    child++;  // get bigger child.

            }

            if ( data[parent] >= data[child] )

                break;

            tmp=data[parent];  data[parent]=data[child];  data[child]=tmp;

            parent = child;

            child = 2*parent + 1;

        }

    }

    void buildheap() {  // When siftdown, build heap from the bottom to up.

        for (int idx=n/2-1 ; idx>=0 ; idx--)

            siftdown(idx);

    }

    void exchange(int nidx1, int nidx2) {

        T tmp;

        tmp=data[nidx1];  data[nidx1]=data[nidx2];  data[nidx2]=tmp;

    }

    void heapsort() {

        buildheap();

        while (n>0) {

            exchange(0, n-1);  // The heap root (0 index, biggest value) is swapped to the end.

            n--;  // Then separate the last member from the heap.

            siftdown(0);

        }

    }

public:

    static bool sort(std::vector<T>& indata) {

        if(indata.empty() || indata.size()==1) return false;

        CHeapSorter<T> hps(indata);

        hps.heapsort();

        return true;

    }

};

int op_sub (int i, int j) { return i-j; }

int main(int argc, char* argv[]) {

    const int NUMELEM = 1027;

    const int TESTNUM = 1234;

    srand( time(NULL) );

    for (int testcnt=0 ; testcnt<TESTNUM ; testcnt++) {

        std::vector<int> indata(NUMELEM);

        for (int i=0 ; i<NUMELEM ; i++)

            indata[i] = rand()-RAND_MAX/2;

        std::vector<int> cmpdata(indata);

        std::random_shuffle(cmpdata.begin(), cmpdata.end());

        {

            CHeapSorter<int>::sort(indata);

            std::sort(cmpdata.begin(), cmpdata.end());

            std::vector<int> diffvec(indata.size());

            std::transform (indata.begin(), indata.end(), cmpdata.begin(), diffvec.begin(), op_sub);

            int init=0;

            if ( accumulate(diffvec.begin(), diffvec.end(), init) != 0 )

                std::cerr << "ERROR in heapsort implementation!" << std::endl;

        }

    }

    std::cout << "SUCCESS in heapsort implementation. Well done!" << std::endl;

}

#include <iostream>

#include <vector>

// #include <boost/functional/hash.hpp>

class CListNode {

private:

    std::string mName;

    CListNode* mNext;

private:

    CListNode(const std::string& inName) : mName(inName) {

        std::cout << "Ctored" << std::endl;

        mNext = NULL;

    }

    ~CListNode() {

        std::cout << "Dtored" << std::endl;

    }

    CListNode();

    CListNode(const CListNode&);

    CListNode& operator= (const CListNode&);

public:

    static CListNode* createList(const std::string& inName) {  // Return head of list.

        std::cout << "A new list is created: " << inName << std::endl;

        return (CListNode*)(new CListNode(inName));

    }

    std::string getName() {

        return mName;

    }

    void insertNode(const std::string& inName) {

        std::cout << "insertNode: " << inName << std::endl;

        CListNode* prev(this);  // Initially is head.

        CListNode* next(this);

        while(next != NULL) {

            prev = next;

            next = next->mNext;

        }

        prev->mNext = (CListNode*)(new CListNode(inName));

    }

    // Find node with name findName

    CListNode* findNode(const std::string& findName) {

        CListNode* prev(this);  // Initially is head.

        CListNode* next(this);

        while(next != NULL) {

            if( (next->mName) == findName )

                return next;

            prev = next;

            next = next->mNext;

        }

        return NULL;

    }

    bool deleteNode(CListNode** head, const std::string& delName) {

        CListNode* prev(this);  // Initially is head.

        CListNode* next(this);

        while(next != NULL) {

            if( (next->mName) == delName ) {

                if(next == *head) {

                    *head = prev->mNext;

                }

                else {

                    prev->mNext = next->mNext;

                }

                delete next;

                return true;

            }

            prev = next;

            next = next->mNext;

        }

        return false;

    }

};

static const size_t HASH_BUCKET_LEN = 10000;

std::vector<CListNode*> hashBucketHead(HASH_BUCKET_LEN, NULL);  // Init with NULL.

unsigned long stringHash(const std::string& instr) {

    unsigned long result = 17;

    size_t len = instr.length();

    for(size_t i=0 ; i<len ; i++)

        result = 31*result + instr[i];

    return result;

}

unsigned long stringHashCol(const std::string& instr) {

    unsigned long result = 17;

    size_t len = instr.length();

    for(size_t i=0 ; i<len ; i+=2)

        result = 31*result + instr[i];

    return result;

}

void insertHashTable(const std::string& inName) {

    unsigned long hashName = stringHashCol(inName);

    // unsigned long hashName = stringHash(inName);

    size_t hashIdx = hashName % HASH_BUCKET_LEN;

    if(hashBucketHead[hashIdx] == NULL)

        hashBucketHead[hashIdx] = CListNode::createList(inName);

    else

        (hashBucketHead[hashIdx])->insertNode(inName);

}

bool deleteHashTable(const std::string& delName) {

    unsigned long hashName = stringHashCol(delName);

    // unsigned long hashName = stringHash(delName);

    size_t hashIdx = hashName % HASH_BUCKET_LEN;

    if(hashBucketHead[hashIdx] == NULL)

        return false;

    else

        return (hashBucketHead[hashIdx])->deleteNode(&(hashBucketHead[hashIdx]), delName);

}

bool findNameInHashTable(const std::string& findName) {

    unsigned long hashName = stringHashCol(findName);

    // unsigned long hashName = stringHash(findName);

    size_t hashIdx = hashName % HASH_BUCKET_LEN;

    if(hashBucketHead[hashIdx] == NULL)

        return false;

    CListNode* result = (hashBucketHead[hashIdx])->findNode(findName);

    if(result == NULL)

        return false;

    else

        return (result->getName() == findName);

}

int main() {

    insertHashTable("Hash me");

    insertHashTable("H2s2 2e");

    insertHashTable("H3s3 3e");

    std::cout << deleteHashTable("abcdef") << std::endl;

    std::cout << deleteHashTable("Hash me") << std::endl;

    std::cout << deleteHashTable("Hash me") << std::endl;

    std::cout << deleteHashTable("H2s2 2e") << std::endl;

    std::cout << deleteHashTable("H2s2 2e") << std::endl;

    std::cout << "Check find" << std::endl;

    std::cout << findNameInHashTable("abcdef") << std::endl;

    std::cout << findNameInHashTable("Hash me") << std::endl;

    std::cout << findNameInHashTable("H3s3 3e") << std::endl;

}

#include <boost/shared_ptr.hpp>

#include <boost/enable_shared_from_this.hpp>

class CListNode;

typedef boost::shared_ptr<CListNode> CListNodePtr;

class CListNode : public boost::enable_shared_from_this<CListNode>

{

private:

    std::string mName;

    CListNodePtr mNext;

private:

    CListNode(const std::string& inName) : mName(inName) {

        std::cout << "Ctored" << std::endl;

        mNext = CListNodePtr();

    }

    CListNode();

    CListNode(const CListNode&);

    CListNode& operator= (const CListNode&);

public:

    ~CListNode() {

        std::cout << "Dtored" << std::endl;

    }

    static CListNodePtr createList(const std::string& inName) {  // Return head of list.

        std::cout << "A new list is created: " << inName << std::endl;

        return (CListNodePtr)(new CListNode(inName));

    }

    std::string getName() {

        return mName;

    }

    void insertNode(const std::string& inName) {

        std::cout << "insertNode: " << inName << std::endl;

        CListNodePtr prev = shared_from_this();  // Initially is head.

        CListNodePtr next = shared_from_this();

        while(next != NULL) {

            prev = next;

            next = next->mNext;

        }

        prev->mNext = (CListNodePtr)(new CListNode(inName));

    }

    // Find node with name findName

    CListNodePtr findNode(const std::string& findName) {

        CListNodePtr prev = shared_from_this();  // Initially is head.

        CListNodePtr next = shared_from_this();

        while(next != NULL) {

            if( (next->mName) == findName )

                return next;

            prev = next;

            next = next->mNext;

        }

        return CListNodePtr();

    }

    bool deleteNode(CListNodePtr* head, const std::string& delName) {

        CListNodePtr prev = shared_from_this();  // Initially is head.

        CListNodePtr next = shared_from_this();

        while(next != NULL) {

            if( (next->mName) == delName ) {

                if(next == *head) {

                    *head = prev->mNext;

                }

                else {

                    prev->mNext = next->mNext;

                }

                // This is the equivalent with delete next; But, even without this, shared_ptr do the release etc.

                next.reset();

                return true;

            }

            prev = next;

            next = next->mNext;

        }

        return false;

    }

};

import java.util.PriorityQueue;

public class TrainRobber {

    public static double EPS = 1.0E-9;

    public TrainRobber() {}

    private final class A implements Comparable<A> {

        private final double offset;

        private final double period;

        private A(double offset, double period) {

            this.offset = offset;

            this.period = period;

        }

        @Override public boolean equals(Object obj) {

            if(obj == this)

                return true;

            if (!(obj instanceof A))

                return false;

            A a = (A) obj;

            if (a.offset == offset) {

                return true;

            }

            return false;

        }

        @Override public int hashCode() {

            return (int) offset;

        }

        public int compareTo(A a) {

            if (a.offset < offset) {

                return 1;

            }

            if (a.offset == offset) {

                return 0;

            }

            return -1;

        }

    }

    public double finalPosition(int length, int nCarriages, String[] offset, String[] period, int trainSpeed, int robberSpeed, int nBridges) {

        int noffset = 0;

        for(int i=0 ; i<offset.length ; i++) {

            String[] parts = offset[i].trim().split("\\s+");

            noffset += parts.length;

        }

        int[] offsets = new int[noffset];

        int[] periods = new int[noffset];

        {

            int cnt = 0;

            for(int i=0 ; i<offset.length ; i++) {

                String[] parts = offset[i].trim().split("\\s+");

                for(int j=0 ; j<parts.length ; j++) {

                    offsets[cnt] = Integer.parseInt(parts[j]);

                    cnt++;

                }

            }

            cnt = 0;

            for(int i=0 ; i<period.length ; i++) {

                String[] parts = period[i].trim().split("\\s+");

                for(int j=0 ; j<parts.length ; j++) {

                    periods[cnt] = Integer.parseInt(parts[j]);

                    cnt++;

                }

            }

        }

        double absolutePos = 0.0;  // absolute pos of the robber.

        long passedBridge = 0;

        long passedCar = 0;

        final double time1Car = (double)length/(double)robberSpeed;  // Time for robber to pass 1 carriage.

        PriorityQueue<A> pq = new PriorityQueue<A>();

        for (int i = 0; i < noffset; i++) {

            pq.add(new A( (double)(offsets[i]), (double)(periods[i])) );

        }

        while(passedBridge < nBridges) {

            A p = pq.poll();

            passedBridge++;

            pq.add(new A(p.offset+p.period, p.period));

            double nearestBridge = p.offset;

            double time2Bridge = (nearestBridge - absolutePos) / ((double)robberSpeed + trainSpeed);

            long passableCar = (long)(Math.floor( time2Bridge/time1Car + EPS));

            if( (passedCar+passableCar) < nCarriages ) {

                passedCar += passableCar;

                absolutePos = nearestBridge;

            }

            else {

                return absolutePos + (double)(nCarriages-passedCar)*time1Car*((double)robberSpeed + trainSpeed);

            }

        }

        return absolutePos;

    }

    public static void main(String[] args) {

        {

            String exNum = "0";

            int length = 1;

            int nCarriages = 4;

            String[] offset = {"3 4"};

            String[] period = {"4", "2"};

            int trainSpeed = 1;

            int robberSpeed = 1;

            int nBridges = 100;

            double expected = 14.0;

            long start = System.currentTimeMillis();

            validateExample(exNum, new TrainRobber().finalPosition(length, nCarriages, offset, period, trainSpeed, robberSpeed, nBridges), expected, start);

        }

}

#include <iostream>

#include <vector>

#include <string>

#include <stdlib.h>

#include <time.h>

#include <math.h>

#include <sstream>

#include <queue>

#include <sys/time.h>

#include <unistd.h>

using namespace std;

static const double EPS = 1E-9;

class TrainRobber {

private:

    vector<long long> offsets;

    vector<long long> periods;

    struct SCompare {

        bool operator() (const pair<double, double>& lhs, const pair<double, double>& rhs) const {

            return (lhs.first > rhs.first);

        }

    };

public:

    double finalPosition(int length, int nCarriages, vector<string> offset,

                         vector<string> period, int trainSpeed, int robberSpeed,

                         int nBridges) {

        priority_queue<pair<double, double>, vector<pair<double, double> >, SCompare> pq;

        offsets.clear();

        for(vector<string>::iterator itr=offset.begin() ; itr!=offset.end() ; itr++) {

            stringstream tokenizer(*itr);

            int n;

            while(tokenizer >> n)

                offsets.push_back(n);

        }

        periods.clear();

        for(vector<string>::iterator itr=period.begin() ; itr!=period.end() ; itr++) {

            stringstream tokenizer(*itr);

            int n;

            while(tokenizer >> n)

                periods.push_back(n);

        }

        for(int i=0 ; i<offsets.size() ; i++)

            pq.push(pair<double, double>(offsets[i], periods[i]));

        double absolutePos = 0.0;

        long passedBridge = 0;

        long passedCar = 0;

        const double time1Car = (double)length/(double)robberSpeed;  // Time for robber to pass 1 carriage.

        while(passedBridge < nBridges) {

            pair<double, double> toppq = pq.top();

            pq.pop();

            passedBridge++;

            pq.push(pair<double, double>(toppq.first+toppq.second, toppq.second));

            double nearestBridge = toppq.first;

            double time2Bridge = (nearestBridge - absolutePos) / ((double)robberSpeed + trainSpeed);

            long passableCar = (long)(floor( time2Bridge/time1Car + EPS));

            if( (passedCar+passableCar) < nCarriages ) {

                passedCar += passableCar;

                absolutePos = nearestBridge;

            }

            else {

                return absolutePos + (double)(nCarriages-passedCar)*time1Car*((double)robberSpeed + trainSpeed);

            }

        }

        return absolutePos;

    }

};

void validateExample(string exampleNum, double returned, double expected,

                     const timeval& startTime) {

    cout << exampleNum << "\t";

    if( fabs(expected-returned) < EPS )

        cout << "SUCCESS ";

    else

        cout << "FAIL ";

    cout << "\tGot:";

    cout << returned;

    cout << "\t";

    cout << "Expected:";

    cout << expected;

    cout << "\t";

    timeval finishTime;

    gettimeofday(&finishTime, NULL);

    long seconds  = finishTime.tv_sec  - startTime.tv_sec;

    long useconds = finishTime.tv_usec - startTime.tv_usec;

    long mtime = ((seconds) * 1000 + useconds/1000.0) + 0.5;

    cout << "Processing time:" << mtime << "msec" << endl;

}

int main(int argc, char* argv[]) {

    {

        string exNum = "0";

        int length = 1;

        int nCarriages = 4;

        string _offset[] = {"  \t \t    3 \t \t 4  \t   "};

        string _period[] = {"\t4 ", "  \t  2 "};

        int trainSpeed = 1;

        int robberSpeed = 1;

        int nBridges = 100;

        double expected = 14.0;

        vector<string> offset(_offset, _offset+(sizeof(_offset)/sizeof(string)));

        vector<string> period(_period, _period+(sizeof(_period)/sizeof(string)));

        timeval start;

        gettimeofday(&start, NULL);

        TrainRobber trobj;

        validateExample(exNum, trobj.finalPosition(length, nCarriages, offset, period, trainSpeed, robberSpeed, nBridges), expected, start);

    }

}

// Return the index of data in inputvec which is nearest to the query.

// How if it is just in the midpoint of a range? Return the smaller one.

// Precondition: inputvec is upsorted (also means the elements are comparable)

template <typename T>

const int nnSearch(const std::vector<T>& inputvec, const T query) {

    const int length = inputvec.size();

    int lo=0;

    int up=length-1;  // Be careful! This is the index, not the length.

    while(lo<=up) {

        int m=(lo+up)/2;

        if(inputvec[m]<query)

            lo = m+1;

        else if(inputvec[m]>query)

            up = m-1;

        else // inputvec[m]==query

            return m;

    }

    if( (lo-up)!= 1 ) {

        std::cerr << "Illegal nnSearch result" << std::endl;

        return -1;

    }

    // std::cout << "up = " << up << "; lo = " << lo << std::endl;

    if ( 0==lo ) {

        // std::cout << "-inf < " << query << " < " << inputvec[lo] << std::endl;

        if( !(query<inputvec[0]) ) {

            std::cerr << "Illegal nnSearch result" << std::endl;

            return -1;

        }

        return lo;

    }

    else if ( (length-1)==up ) {

        // std::cout << inputvec[up] << " < " << query << " < inf" << std::endl;

        if( !(query>inputvec[up]) ) {

            std::cerr << "Illegal nnSearch result" << std::endl;

            return -1;

        }

        return up;

    }

    else {

        // std::cout << inputvec[up] << " < " << query << " < " << inputvec[lo] << std::endl;

        if( query<inputvec[up] || query>inputvec[lo] ) {

            std::cerr << "Illegal nnSearch result" << std::endl;

            return -1;

        }

        if( (query-inputvec[up]) > (inputvec[lo]-query) )

            return lo;

        else

            return up;

    }

}

// Return the index where query FIRST exist in inputvec, else -1.

// Precondition: inputvec is upsorted (also means the elements are comparable)

template <typename T>

const int firstSearch(const std::vector<T>& inputvec, const T query) {

    int lo=-1;               // 1 BEFORE valid index.

    int up=inputvec.size();  // 1 AFTER valid index.

    while((lo+1)!=up) {

        // invariant: (lo+1)!=up&& vec[lo]<query && vec[up]>=query

        int m=(lo+up)/2;

        if(inputvec[m]<query)

            lo = m;

        else

            up = m;

    }

    // assert: (lo+1)==up && vec[lo]<query && vec[up]>=query

    if(up>=inputvec.size() || inputvec[up]!=query)

        return -1;

    else

        return up;

}

m = a-1;

for i = [a, b]

    if x[i] < t

        swap( ++m, i );

private static void sort(Comparable[] a, int lo, int hi) {

    if (hi <= lo) return;

    int lt = lo, gt = hi;

    Comparable v = a[lo];

    int i = lo;

    while (i <= gt) {

        int cmp = a[i].compareTo(v);

        if        (cmp < 0) exch(a, lt++, i++);

        else if (cmp > 0) exch(a, i, gt--);

        else                   i++;

    }

    sort(a, lo, lt-1);

    sort(a, gt+1, hi);

}

main() {

    shuffle(a);  // To guarantee N*lg(N)

    sort(a, 0, a.length());

}

// Finding kth-smallest element. Using recursion.

template <typename DT>

void select1(std::vector<DT>& x, const int lo, const int up, const int k) {

    // Pre: lo <= k <= up

    // Post: x[lo ... (k-1)] <= x[k] <= x[(k+1) ... up]

    if (lo>=up) return;

    srand( time(NULL) );

    swap(x, lo, randint(lo, up));

    int i=lo, j=up+1;

    const DT t=x[lo];

    for (;;) {

        do i++; while(i<=up && x[i]<t);

        do j--; while(x[j]>t);

        if (i>j) break;

        swap(x, i, j);

    }

    swap(x, lo, j);

    if (j<k) {

        select1(x, j+1, up, k);

    }

    else if (j>k) {

        select1(x, lo, j-1, k);

    }

}

// Finding kth-smallest element. WITHOUT recursion.

template <typename DT>

void select2(std::vector<DT>& x, int lo, int up, const int k) {

    // Pre: lo <= k <= up

    // Post: x[lo ... (k-1)] <= x[k] <= x[(k+1) ... up]

    while (1) {

        if (lo>=up) return;

        srand( time(NULL) );

        swap(x, lo, randint(lo, up));

        int i=lo, j=up+1;

        const DT t=x[lo];

        for (;;) {

            do i++; while(i<=up && x[i]<t);

            do j--; while(x[j]>t);

            if (i>j) break;

            swap(x, i, j);

        }

        swap(x, lo, j);

        if (j<k)

            lo = j+1;

        else if (j>k)

            up = j-1;

        else

            return;

    }

}

nonRecursizePreOrder(root) {

    // Must initialize all nodes to Unvisited.

    root.setAllNodesUnvisited();

    stack nodeStack;

    nodeStack.push(root);

    while (nodeStack not empty) {

        nodei = nodeStack.pop();

        if (nodei.isUnvisited()) {

            nodei.setVisited();

            cout << nodei;    // Pre-order processing.

            for (nodej in nodei.children())

                nodeStack.push(nodej);

        }

    }

}

bool ListContainsLoop(Node * head) {

  Node * slowPtr = head;

  Node * fastPtr = head;

  while(slowPtr  && fastPtr) {

    fastPtr = fastPtr->next; // advance the fast pointer

    if(fastPtr == slowPtr)   // and check if its equal to the slow pointer

      return true;         // loop detected

    if(fastPtr == NULL)

      return false;        // since fastPtr is NULL we reached the tail

    fastPtr = fastPtr->next; //advance and check again

    f(fastPtr == slowPtr)

      return true;

    slowPtr = slowPtr->next;  // advance the slow pointer only once

  }

  return false;                // we reach here if we reach the tail

}