Spoj QTREE2 – CPP solution

Problem: http://www.spoj.com/problems/QTREE2/
Idea:
You have to traverse the tree and pre-process the needed data.
We need the have the sum of weights from the root to any node u and answer it in O(1), we should know the depth of each node and the 2^K th parent of any node for all possible K.

We use the weight augmentation to answers the distance. For example, if we want to answer
dist(A,B), then first we find the lowest common ancestor, namely the branching node which we have to pass to go from A to B. Obviously, we can use the weight array to find the weight of the path. If you do not understand how, just sketch the tree and see what the weight array gives you for weight[A] and weight[B].

The “KTH query” we can answer also easily using the LCA, depth and parent array. If we have the branching node W = LCA(A,B), then the KTH node is either to the left of W, to the right of W or W itself. We just have to check whether we should search on the left or right, and do it.

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;

typedef long long ll;
int n;
vector<pair<int,ll> > nb[100001];
int parent[100001][24];
int depth[100001];
ll weight[100001];

void cl() {
    for (int i = 1; i <=n; ++i) {
        nb[i].clear();
        weight[i] = 0;
        depth[i] = 0;
    }
}

void dfs(int u, int p) {
    parent[u][0] = p;
    depth[u] = depth[p]+1;
    for(size_t i = 0; i < nb[u].size(); ++i) {
        int v = nb[u][i].first;
        ll w = nb[u][i].second;
        if (v != p) {
            weight[v] = weight[u] + w;
            dfs(v, u);
        }
    }
}

void pre() {
    for (int i = 1; (1<<i) <= n; ++i) {
        for (int j = 1; j<=n; ++j) {
            parent[j][i] = parent[parent[j][i-1]][i-1];
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u,v);
    int LOG = 23;
    while(depth[u] != depth[v]) {
        if (depth[u]-(1<<LOG) >= depth[v]) {
            u = parent[u][LOG];
        }
        --LOG;
        if (LOG < 0) LOG = 0;
    }
    LOG = 23;
    while(u != v) {
        if (parent[u][LOG] != parent[v][LOG] || LOG == 0) {
            u = parent[u][LOG];
            v = parent[v][LOG];
        }
        --LOG;
        if (LOG < 0) LOG = 0;
    }
    return u;
}

int kth(int u, int v, int k) {
    int w = lca(u,v);
    int d1 = depth[u]-depth[w]+1;
    int d2 = depth[v]-depth[w]+1;
    int from;
    if (d1 < k) {
        from = v;
        k = d2+d1-k-1;
    } else if(k == d1) {
        return w;
    } else if (d1 > k) {
        from = u;
        k-=1;
    }
    int LOG = 23;
    while (k != 0) {
        if (1<<LOG <= k) {
            from = parent[from][LOG];
            k-= (1<<LOG);
        }
        --LOG;
        if (LOG < 0) LOG = 0;
    }
    return from;
}

ll dist(int u, int v) {
    int w = lca(u,v);
    return weight[u]+weight[v] - 2LL*weight[w];
}

int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        for(int i = 1; i<n; ++i) {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            nb[a].push_back(make_pair(b,c));
            nb[b].push_back(make_pair(a,c));
        }
        dfs(1, 0);
        pre();
        char opr[10];
        while(1) {
            scanf("%s", opr);
            if (opr[0] == 'D' && opr[1] == 'O') {
                break;
            } else if (opr[0] == 'K') {
                int u,v,k;
                scanf("%d%d%d",&u,&v,&k);
                printf("%dn", kth(u,v,k));
            } else if(opr[0] == 'D' && opr[1] == 'I') {
                int u,v;
                scanf("%d%d",&u,&v);
                printf("%lldn", dist(u,v));
            }
        }
        cl();
    }
    return 0;
}

Spoj ORDERSET – CPP solution

Problem: http://www.spoj.com/problems/ORDERSET/

The problem can be very easily solved using std::set. The problem is that std::set would be slow for this problem.
One can solve it with a custom implementation of a balanced binary search tree. I used Treap.

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <set>
#include <algorithm>
typedef long Key;
typedef long Priority;

struct Treap;
Treap * root;
Treap * nil;

struct Treap {
    Key key;
    Priority priority;
    Treap * left;
    Treap * right;
    int size;
    Treap() : size(0) {};
    Treap(Key _key, Priority _priority) :
        key(_key), priority(_priority), left(nil), right(nil), size(1) {};
    Treap(Key _key, Priority _priority, int _size) :
        key(_key), priority(_priority), left(nil), right(nil), size(_size) {};
};

void print(Treap * node, int lvl, bool l) {
    if(node == nil) return;
    if (l) printf("Left, Key: %ld, Priority: %ld, Level: %d, Size: %dn", node->key, node->priority, lvl, node->size);
    if (!l) printf("Right, Key: %ld, Priority: %ld, Level: %d, Size: %dn", node->key, node->priority, lvl, node->size);
    print(node->left, lvl+1, 1);
    print(node->right, lvl+1, 0);
}

void updateSize(Treap * cur) {
    cur->size = cur->right->size + cur->left->size + 1;
}

void rotateRight(Treap * cur, Treap * leftChild) {
    cur->left = leftChild->right;
    leftChild->right = cur;
    updateSize(cur);
    updateSize(leftChild);
}

void rotateLeft(Treap * cur, Treap * rightChild) {
    cur->right = rightChild->left;
    rightChild->left = cur;
    updateSize(cur);
    updateSize(rightChild);
}

Treap * add(Treap * cur, Treap * node) {
    if (cur->key < node->key) {
        // go right
        Treap * rht = cur->right;
        if (rht == nil) {
            rht = node;
        } else {
            rht = add(rht, node);
            if (rht == nil) return nil;
        }
        cur->right = rht;
        if (rht->priority > cur->priority) {
            // left rotation
            rotateLeft(cur, rht);
            return rht;
        }
        updateSize(cur);
        return cur;
    } else if (cur->key > node->key) {
        // go left
        Treap * lft = cur->left;
        if (lft == nil) {
           lft = node;
        } else {
            lft = add(lft, node);
            if (lft == nil) return nil;
        }
        cur->left = lft;
        if (lft->priority > cur->priority) {
            // right rotation
            rotateRight(cur, lft);
            return lft;
        }
        updateSize(cur);
        return cur;
    } else {
        return cur;
    }
}

void add(Key key) {
    Priority priority = rand();
    Treap * node = new Treap(key, priority);
    if (root == nil) {
        root = node;
    } else {
        root = add(root, node);
    }
}

Treap * rem(Treap * cur, Key key) {
    if (cur == nil) return nil;
    if (cur->key == key) {
        if (cur->left == nil && cur->right == nil) {
            // destroy
            delete cur;
            return nil;
        } else if (cur->left == nil || cur->right->priority > cur->left->priority) {
            // rotate left
            Treap * rht = cur->right;
            rotateLeft(cur, rht);
            rht->left = rem(cur, key);
            cur = rht;
        } else {
            // rotate right
            Treap * lft = cur->left;
            rotateRight(cur, lft);
            lft->right = rem(cur, key);
            cur = lft;
        }
    } else if (cur->key > key) {
        cur->left = rem(cur->left, key);
    } else {
        cur->right = rem(cur->right, key);
    }
    updateSize(cur);
    return cur;
}

void rem(Key key) {
    root = rem(root, key);
}

Treap * kth(Treap * cur, int k) {
    if (cur == nil) {
        return nil;
    }
    //printf("~%dn", k);
    int tmp = cur->left->size + 1;
    if (tmp == k) {
        return cur;
    } else if ( tmp < k) {
       // printf("right %dn", k-tmp);
        return kth(cur->right, k - tmp);
    } else {
        //printf("left %dn", k);
        return kth(cur->left, k);
    }
}

int cnt(Treap * cur, Key key) {
    if (cur == nil) return 0;
    if (cur->key == key) {
        return cur->left->size;
    } else if (cur->key < key) {
        return cur->left->size + 1 + cnt(cur->right, key);
    } else {
        return cnt(cur->left, key);
    }
}

void test(Treap * cur) {
    if (cur == nil) return;
    int sz = 1 + cur->left->size + cur->right->size;
    if (sz != cur->size) {
        printf("SIZE ERRORn");
        exit(1);
    }
    if (cur->left->priority > cur->priority) {
        printf("LEFT PRIORITY ERRORn");
        exit(1);
    }
    if (cur->right->priority > cur->priority) {
        printf("RIGHT PRIORITY ERRORn");
        exit(1);
    }
    if (cur->right != nil && cur->right->key < cur->key) {
        printf("RIGHT KEY ERRORn");
        exit(1);
    }
    if (cur->left != nil && cur->left->key > cur->key) {
        printf("LEFT KEY ERRORn");
        exit(1);
    }
    test(cur->left);
    test(cur->right);
}

std::set<int> ss;

void test() {
    if (root->size != ss.size()) {
        printf("SET SIZE ERRORn");
        exit(1);
    }
    test(root);
}

void gen() {
    using namespace std;
    FILE * out = fopen("orderset.test", "w+");
    FILE * ans = fopen("orderset.ans", "w+");
    int n = 50000;
    fprintf(out, "%dn", n);
    set<int> ss;
    set<int>::iterator it;
    for (int i = 0; i < n; ++i) {
        int op = rand()%100;
        if (op >= 0 && op < 15) {
            // delete
            if (ss.size() > 0) {
                it = ss.begin();
                advance(it, rand()%(ss.size()-1));
                int key = *it;
                fprintf(out, "D %dn", key);
                ss.erase(key);
            } else {
                --i;
            }
        } else if (op >= 15 && op < 60) {
            // insert
            int key = rand();
            ss.insert(key);
            fprintf(out, "I %dn", key);
        } else if (op >= 60 && op < 85) {
            // count
            int key = rand();
            fprintf(out, "C %dn", key);
            it = ss.lower_bound(key);
            fprintf(ans, "%dn", distance(ss.begin(),it));
        } else {
            // kth
            int num = rand() % (ss.size() + rand()%50) + 1;
            fprintf(out, "K %dn", num);
            if (num > ss.size()) {
                fprintf(ans, "invalidn");
            } else {
                it = ss.begin();
                num -= 1;
                advance(it, num);
                fprintf(ans, "%dn", *it);
            }
        }
    }
    fclose(out);
    fclose(ans);
}

//#define DEBUG

int main() {
    srand(time(NULL));
    #ifdef DEBUG
    gen();
    return 0;
    #endif
    nil = new Treap();
    root = nil;
    int q;
    scanf("%d", &q);
    while (q--) {
        char ch[2];
        Key key;
        scanf("%s%ld", ch, &key);
        if (ch[0] == 'I') {
            add(key);
            //print(root, 0, 0);
        } else if (ch[0] == 'D') {
            rem(key);
        } else if (ch[0] == 'C') {
            printf("%dn", cnt(root, key));
        } else if (ch[0] == 'K') {
            if (key > root->size) {
                printf("invalidn");
            } else {
                printf("%ldn", kth(root, key)->key);
            }
        }
        //printf("n");
        //print(root, 0, 0);
        //printf("n");
    }
    return 0;
}

Spoj QTREE – CPP solution

Problem: http://www.spoj.com/problems/QTREE/

The keys to solving this problem are:
– some basic graph theory (traversing graphs) (easy)
– LCA on a tree (medium)
– Heavy-light decomposition (medium-hard)
– Segment tree (medium)

In general, I had some bugs in my code and it took some time to debug. You can see some asserts and generating tests to see what’s going wrong with my solution. :)

Note that this is the O(nlogn + Qlogn * logn) where Q is the number of queries.
I could not get the O(nlogn + Q * logn) to work.

If you are willing to try, note that we are using the segment tree to check the maximum over a given chain. From one node to a given parent node somewhere in the tree, there are at most O(logn) chains. The thing is that possibly for expect the first and last chain, we are querying over the whole interval which means that for each chain we can just keep a maximum value so that we are able to retrieve it in O(1) and update it O(1) time. This will lead to a
O(logn) per query.

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;

struct Edge {
    int u;
    int v;
    int cost;
    Edge() {};
    Edge(int _u, int _v, int _cost) : u(_u), v(_v), cost(_cost) {};
    int getNb(int V) {
        return V == v ? u : v;
    }
};
int n;
vector<int> nb[10001];
int childSz[10001];
int parent[10001][32];
int depth[10001];
Edge edges[10001];
int LOG;
int numChains;
char isSpecial[10001];
int generatedArrayIDX;
int generatedArray[10001];
int chainHead[10001];
int chainSize[10001];
int vertexChain[10001];
int vertexPos[10001];
int tree[80001];

int slow(int u, int c, int p, int r) {
    if (u == r) {
        return c;
    }
    int res = 0;
    for (int i = 0; i < nb[u].size();i++) {
        int v = edges[nb[u][i]].getNb(u);
        if (p == v) continue;
        int q = slow(v, edges[nb[u][i]].cost, u, r);
        if (q) q = max(q, edges[nb[u][i]].cost);
        res = max(res, q);
    }
    return res;
}

void reset() {
    numChains = 0;
    generatedArrayIDX = 0;
    for (int i = 0; i<=n; i++) {
        nb[i].clear();
        childSz[0];
        parent[i][0] = 0;
        depth[i] = 0;
        isSpecial[i] = 0;
        chainHead[i] = 0;
        generatedArray[i] = 0;
        chainSize[i] = 0;
        vertexChain[i] = 0;
        vertexPos[i] = 0;
    }
}

void dfs(int u, int p) {
    childSz[u] = 1;
    parent[u][0] = p;
    depth[u] = depth[p]+1;
    for (int i = 0; i < nb[u].size(); i++) {
        int v = edges[nb[u][i]].getNb(u);
        if (v == p) continue;
        dfs(v,u);
        childSz[u] += childSz[v];
    }
}

void hld(int u,int e) {
    if (chainHead[numChains] == 0) {
        // create new chain
        chainHead[numChains] = u;
    }
    vertexChain[u] = numChains;
    vertexPos[u] = generatedArrayIDX;
    chainSize[numChains]+=1;
    if (u != 0) {
        generatedArray[generatedArrayIDX++] = e;
    }

    int special = 0;
    int edge;
    for (int i = 0; i < nb[u].size(); i++) {
        int v =edges[nb[u][i]].getNb(u);
        if (v == parent[u][0]) continue;
        if (childSz[special] < childSz[v]) {
            special = v;
            edge = edges[nb[u][i]].cost;
        }
    }
    if (special == 0) return;
    isSpecial[special] = 1;
    hld(special, edge);
    for (int i = 0; i < nb[u].size(); i++) {
        int v = edges[nb[u][i]].getNb(u);
        if (v == parent[u][0] || v == special) continue;
        ++numChains;
        hld(v,edges[nb[u][i]].cost);
    }
}


void build(int idx, int sfrom, int sto) {
    if (sfrom == sto) {
        tree[idx] = generatedArray[sfrom];
        return;
    }
    int mid = (sfrom+sto)>>1;
    int left = idx<<1;
    int right = left+1;
    build(left, sfrom, mid);
    build(right, mid+1, sto);
    tree[idx] = max(tree[left], tree[right]);
}

void init() {
    dfs(1,0);
    LOG = 0;
    while ((1<<LOG) <= n) ++LOG;
    for (int i = 1; i<=LOG; i++) {
        for (int u = 1; u<=n; u++) {
            parent[u][i] = parent[parent[u][i-1]][i-1];
        }
    }
    hld(1, 0);
    build(1, 0, generatedArrayIDX-1);
}

int lca(int u, int v) {
    int L = LOG;
    if (depth[u] < depth[v]) swap(u,v);
    while (depth[u] != depth[v]) {
        if (depth[u] - (1<<L) >= depth[v]) u = parent[u][L];
        --L;
        if (L < 0) L=0;
    }
    L = LOG;
    while (u != v) {
        if (parent[u][L] != parent[v][L] || L == 0) {
            u = parent[u][L];
            v = parent[v][L];
        }
        --L;
        if (L < 0) L = 0;
    }
    return u;
}

int query(int idx, int sfrom, int sto, int qfrom, int qto) {
    if (sfrom == qfrom && sto == qto) {
        return tree[idx];
    }
    int mid = (sfrom+sto)>>1;
    int left = idx<<1;
    int right = left+1;
    if (qto <= mid) {
        return query(left, sfrom, mid, qfrom, qto);
    } else if (qfrom > mid) {
        return query(right, mid+1, sto, qfrom, qto);
    } else {
        return max(query(left, sfrom, mid, qfrom, mid),
            query(right, mid+1, sto, mid+1, qto));
    }
}

void update(int idx, int sfrom, int sto, int pos) {
    if (sfrom == sto) {
        tree[idx] = generatedArray[pos];
        return;
    }
    int mid = (sfrom+sto)>>1;
    int left = idx<<1;
    int right = left+1;
    if (pos <= mid) {
        update(left, sfrom, mid, pos);
    } else {
        update(right, mid+1, sto, pos);
    }
    tree[idx] = max(tree[left], tree[right]);
}

int subquery(int TOP, int BOTTOM) {
    int ans = -1;
    if (TOP == BOTTOM) return 0;
    while (true) {
        if (vertexChain[TOP] == vertexChain[BOTTOM]) {
            int topPos = vertexPos[TOP];
            int botPos = vertexPos[BOTTOM];
            if (topPos == botPos) return ans;
            topPos += 1;
            return max(
                ans,
                query(1, 0, generatedArrayIDX-1, topPos, botPos)
            );
        } else {
            int botPos = vertexPos[BOTTOM];
            int topPos = vertexPos[chainHead[vertexChain[BOTTOM]]];

            ans = max(ans, query(1, 0, generatedArrayIDX-1, topPos, botPos));

            BOTTOM = parent[chainHead[vertexChain[BOTTOM]]][0];
        }
    }
}

int query(int u, int v) {
    int w = lca(u,v);
    return max(subquery(w, u), subquery(w,v));
}

int update(int u, int c) {
    Edge & e = edges[u-1];
    e.cost = c;
    int CHILD;
    if (e.u == parent[e.v][0]) {
        CHILD = e.v;
    } else {
        CHILD = e.u;
    }
    generatedArray[vertexPos[CHILD]] = c;
    update(1,0,generatedArrayIDX-1, vertexPos[CHILD]);
}

void genRandom() {
    int t = 1;
    ofstream out("qtree.in");
    out << t << endl;
    srand(time(NULL));
    int FROM = 4000, TO = 4001;
    for (int i = 0; i <t; i++) {
        int v = rand()%(TO-FROM) + FROM;
        out << v << endl;
        vector<int> used;
        used.reserve(v);
        used.push_back(1);
        for (int j = 2; j<=v; j++) {
            int cost = rand()%100 + 5;
            int u = used[rand()%used.size()];
            used.push_back(j);
            out << u << " " << j << " " << cost << endl;
        }
        int op = 2000;
        for (int j = 0; j < op; j++) {
            int M = rand()%2;
            if (M == 0) {
                // query
                int A = rand()%v + 1;
                int B = rand()%v + 1;
                out << "QUERY " << A << " " << B << endl;
            } else {
                // update
                int A = rand()%(v-1) + 1;
                int B = rand()%10000 + 5;
                out << "CHANGE " << A << " " << B << endl;
            }
        }
        out << "DONE" << endl;
    }
    out.close();
}

//#define DEBUG2

int main() {
    #ifdef DEBUG
        genRandom();
        return 0;
    #endif
    int t;
    scanf("%d",&t);
    while (t--) {
        scanf("%d",&n);
        for (int i = 1; i < n; i++) {
            int a,b;
            long c;
            scanf("%d%d%ld", &a,&b,&c);
            edges[i-1] = Edge(a,b,c);
            nb[a].push_back(i-1);
            nb[b].push_back(i-1);
        }
        init();
        int a,b,c;
        char buf[7];
        while (1) {
            scanf("%s",buf);
            if (buf[0] == 'D') break;
            if (buf[0] == 'Q') {
                scanf("%d%d",&a,&b);
                printf("%dn", query(a,b));
                #ifdef DEBUG2
                    assert(query(a,b) == slow(a,0,0,b));
                #endif
            } else if (buf[0] == 'C') {
                scanf("%d%d",&a,&c);
                update(a,c);
            }
        }
        reset();
    }
    return 0;
}

Spoj DSUBSEQ – CPP solution

Problem: http://www.spoj.com/problems/DSUBSEQ/

Say that so far you have generated so far N strings totally without using the letter A. Then you append the letter A and you generate N+N strings. Later, when you add the letter A again, you would like to know how many strings have been generated using the letter A. Obviously, if you add the letter A to those strings, you won’t get distinct.
Keep the number of totally string generated so far and the number of strings generated by using some letter. Later, when adding some letter (say K), then the strings you would generate is (TOTAL – NUM OF STRINGS GENERATED USING K).
Just update the invariant correctly.

#include <cstdio>

typedef long long ll;
#define MOD 1000000007LL
ll arr[30];
char str[100001];

inline ll mod(ll num) {
    num %= MOD;
    if (num < 0LL) num += MOD;
    return num;
}

int main() {
    int t;
    scanf("%d",&t);
    while (t--) {
        scanf("%s", str);
        int i = 0;
        ll sum = 1LL;
        while (str[i]) {
            ll tmp = mod(sum-arr[str[i]-'A']);
            arr[str[i]-'A'] = mod(arr[str[i]-'A']+tmp);
            sum = mod(sum+tmp);
            i++;
        }
        //sum = mod(sum+1LL);
        for (int i = 0; i < 30; i++) arr[i] = 0LL;
        printf("%lldn", sum);
    }
    return 0;
}

Spoj NAJPF – CPP solution

Problem: http://www.spoj.com/problems/NAJPF/

Here are 3 solutions:
– Morris-Pratt (0.04)
– Morris-Pratt automation (0.06 dew to size of alphabet)
– Hashing (0.10 due to false matches)

#include <cstdio>
#include <iostream>
using namespace std;

char T[1000001], P[1000001];
int fail[1000001];
int ans[1000001];
int ansSz;

int main() {
    int t;
    int sz = int('Z')-int('A')+1;
    scanf("%d",&t);
    while (t--) {
        ansSz=0;
        scanf("%s%s", T, P);

        fail[0] = 0;
        fail[1] = 0;
        int l = 2;
        int j = 0;
        while (P[l-1]) {
            if (P[l-1] != P[j]) {
                if (j == 0) {
                    fail[l++] = 0;
                }
                j = fail[j];
            } else {
                while(P[l-1] == P[j]) {
                    fail[l++] = ++j;
                }
            }
        }
        j=0;
        int i = 0;
        while(T[i]) {
            if (T[i] == P[j]) {
                i++;
                j++;
                if (j == l-1) {
                    ans[ansSz++] = i-l+2;
                }
            } else {
                if (j == 0) i++;
                j = fail[j];
            }

        }
        if (ansSz==0) {
            printf("Not Found");
        } else {
            printf("%dn", ansSz);
            for (int i = 0; i < ansSz; i++) printf("%d ", ans[i]);
        }
        printf("n");

    }
    return 0;
}
#include <iostream>
using namespace std;

char T[1000001], P[1000001];
int automata[1000001][30];
int ans[1000001];
int ansSz;

int main() {
    int t;
    int sz = int('Z')-int('A')+1;
    scanf("%d",&t);
    while (t--) {
        ansSz=0;
        scanf("%s%s", T, P);

        int l = 1;
        int link=0;
        for (int i = 0; i < sz; i++) automata[0][i] = 0;
        automata[0][P[0]-'a'] = 1;
        while(P[l]) {
            for (int i = 0; i < sz; i++) {
                automata[l][i] = automata[link][i];
            }
            automata[l][P[l]-'a'] = l+1;
            link = automata[link][P[l]-'a'];
            l++;
        }
        for (int i = 0; i < sz; i++) {
            automata[l][i] = automata[link][i];
        }
        int i = 0;
        int c = 0;
        while(T[i]) {
            if (c==l) {
                ans[ansSz++] = i-l+1;
            }
            c = automata[T[i]-'a'];
            i++;
        }
        if (c==l) {
            ans[ansSz++] = i-l+1;
        }
        if (ansSz==0) {
            printf("Not Found");
        } else {
            printf("%dn", ansSz);
            for (int i = 0; i < ansSz; i++) printf("%d ", ans[i]);
        }
        printf("n");

    }
    return 0;
}
#include <cstdio>
#include <iostream>
using namespace std;

#define MAX 1000009
char T[MAX], P[MAX];
int ans[MAX];
int ansSz;
#define MOD 1000000007LL
#define Z 33LL
long long dp[MAX];

inline long long mod(long long num) {
    if (num < 0LL) num += MOD;
    num %= MOD;
    return num;
}

inline bool ok(int s) {
    int k=0;
    while(P[k] && T[s+k] && P[k] == T[s+k]) k++;
    return !P[k];
}

int main() {
    int t;
    int sz = int('Z')-int('A')+1;
    dp[0] = 1LL;
    for (int i = 1; i< MAX; i++) dp[i] = mod(dp[i-1]*Z);
    scanf("%d",&t);
    while (t--) {
        ansSz=0;
        scanf("%s%s", T,P);
        int l = 0;
        long long h = 0LL;
        long long h2 = 0LL;
        while (P[l] && T[l]) {
            h = mod(h*Z + (P[l]-'a')*1LL);
            h2 = mod(h2*Z + (T[l]-'a')*1LL);
            l++;
        }
        int i = l;
        while(T[i]) {
            if (h == h2 && ok(i-l)) {
                ans[ansSz++] = i-l+1;
            }
            h2 = mod(mod((h2 - dp[l-1]*1LL*(T[i-l]-'a'))*Z) + (T[i]-'a')*1LL);
            i++;
        }
        if (h == h2 && ok(i-l)) {
            ans[ansSz++] = i-l+1;
        }

        if (ansSz==0) {
            printf("Not Found");
        } else {
            printf("%dn", ansSz);
            for (int i = 0; i < ansSz; i++) {
                printf("%d ", ans[i]);
            }
        }
        printf("n");

    }
    return 0;
}

I have 3 implementations since I got quite many segmentation fauls (didn’t read the input size properly) and quite many wrong answers.

Spoj SUB_PROB – CPP solution

Problem: http://www.spoj.com/problems/SUB_PROB/
The idea of the solution is pre-compute a data structure on the patterns we are going to search for. The data structure’s name is Aho-Corasick which is generally an NFA (non-deterministic finite automata) and the idea of its construction is very similar to the KMP automation. The difference is that the Aho-Corasick one is for multiple patterns. It follows the notion that if we have 2 strings:
PANAMATO and MAROCCO
and a text
ETOPANAMAROCCOTO
when searching, say that we are at ETOPANAMAROCCOTO and we are searching for PANAMATO. Obviously, we have a mismatch. On the other hand MA which is a prefix of MAROCCO is a suffix of PANAMA. => it makes sense to continue searching with MAROCCO starting at R since we have already found MA.

Code:

#include <cstdio>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;

class Node;
Node * ZERO;
Node * ROOT;

struct Node {
    Node * link;
    Node * child[256];
    vector<int> found;
    Node() {
        link = ROOT;
        for (int i = 0; i < 256; i++) {
            child[i] = NULL;
        }
    }
    void setChild(int childIdx, Node * id) {
        //cout << (int)this%99 << " " << char(childIdx) << " " << int(id)%99 << endl;
        child[childIdx] = id;
    }
    void setLink(Node * id) {
        //cout << (int)this%99 << " -> " << int(id)%99 << endl;
        link = id;
    }
};

void add(int id, char str[]) {
    Node * CUR = ROOT;
    int i = 0;
    while (str[i] != '\0') {
        char pos = str[i];
        if (CUR->child[pos] == NULL) {
            CUR->setChild(pos, new Node());
        }
        CUR = CUR->child[pos];
        i++;
    }
    CUR->found.push_back(id);
}

void initTrie() {
    ROOT = new Node();
    ZERO = new Node();
    ROOT->link = ZERO;
    for (int i = 0; i < 256; i++) {
        ZERO->child[i] = ROOT;
    }
}

void buildLinks() {
    queue<Node*> Q;
    Q.push(ROOT);
    while (!Q.empty()) {
        Node * CUR = Q.front();
        Q.pop();
        for (int i = 0; i < 256; i++) {
            if (CUR->child[i] == NULL) continue; // no such child, nothing to do here
            // CUR is parent
            Node * TMP = CUR;
            while (TMP->link->child[i] == NULL) TMP = TMP->link;
            CUR->child[i]->setLink(TMP->link->child[i]);
            Q.push(CUR->child[i]);
        }
    }
}

char ANS[2001];
int main() {
    initTrie();
    char TEXT[100001];
    scanf("%s",TEXT);
    int n;
    char PAT[2001];
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
        scanf("%s",PAT);
        add(i, PAT);
    }
    buildLinks();
    int i = 0;
    Node * CUR = ROOT;
    while (TEXT[i] != '\0') {
        char id = TEXT[i];
        if (CUR->child[id] == NULL) {
            CUR = CUR->link;
        } else {
            // check whether we have some occurences
            CUR = CUR->child[id];
            Node * TMP = CUR;
            while (TMP->found.size() > 0) {
                for (int j = 0; j < TMP->found.size(); j++) {
                    ANS[TMP->found[j]] = 1;
                }
                TMP = TMP->link;
            }
            i++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (ANS[i]) {
            printf("Yn");
        } else {
            printf("Nn");
        }
    }
    return 0;
}

Spoj Anttt – CPP solution

Link: http://www.spoj.com/problems/ANTTT/
Idea:
Create a graph of the intersecting lines and use dfs/bfs to find whether a path exists from one node to another. For the intersection part there are two possible ways I know:
1) write out equations for the lines and find the formula for the Y (or X) cordinate and then check whether the point is part of the segment. This is however harder and slower to right with some cases to consider. For example the line x=0.
2) just use standard vector operations. If you are given the lines A-B and C-D. Chech whether A is on one side of C-D and if B is on the other. Then check whether C and D are on opposite sides of A-B. In this case they collide. If we also consider the case where one of the points can lie on the segments, then we can to also consider the case: 1 1 3 3, 4 4 5 5. I.e. when they are parallel. Then you have to also check for the bounds.

When I was at high school, I used to write the first technique and it worked out well. I learned about the second while I was doing USACO.

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

struct Point {
    ll x,y;
    Point() {};
    Point(ll _x, ll _y) : x(_x), y(_y) {};
};

struct Line {
    Point from,to;
    Line() {};
    Line(const Point & _from, const Point & _to) : from(_from), to(_to) {};
};

Point operator -(const Point & A, const Point & B) {
    return Point(A.x-B.x, A.y-B.y);
}

ll cross(const Point & A, const Point & B) {
    return A.x*B.y - A.y*B.x;
}

bool onOneSide(const Line & A, const Line & B) {
    ll v1 = cross(B.from - A.from, A.to - B.from);
    ll v2 = cross(B.to - A.from, A.to - B.to);

    if(v1 == 0LL && v2 == 0LL) {
        if (A.to.x < B.from.x) return false;
        if (A.from.x > B.to.x) return false;
    }
    return (v1 <= 0LL && v2 >=0LL) || (v1 >=0LL && v2 <= 0LL);
}

bool intersect(const Line & A, const Line & B) {
    return onOneSide(A,B) && onOneSide(B,A);
}

int nb[1001][1001];
int nbSz[1001];
int used[1001];
Line lines[1001];
int destination;
int q;

void dfs(int u) {
    if (used[u]==q) return;
    if (destination==-1) return;
    if (u == destination) destination = -1;
    used[u] = q;
    for (int i = 0; i < nbSz[u]; ++i) {
        dfs(nb[u][i]);
    }
}

void cl(int n) {
    for (int i = 1; i<=n; ++i) nbSz[i]=0, used[i]=0;
}

void addNb(int A, int B) {
    nb[A][nbSz[A]++] = B;
    nb[B][nbSz[B]++] = A;
}

int main() {
    int t;
    scanf("%d",&t);
    while (t--) {
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i = 0; i < n; ++i) {
            ll x1,x2,y1,y2;
            scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
            if (x1 > x2) {
                swap(x1,x2);
                swap(y1,y2);
            }
            lines[i+1] = Line(Point(x1,y1),Point(x2,y2));
        }
        for (int i = 1; i<=n; ++i) {
            for (int j = i+1; j<=n; ++j) {
                if (intersect(lines[i], lines[j])) {
                        addNb(i,j);
                }
            }
        }
        for (q = 1; q <= m; ++q) {
            int a,b;
            scanf("%d%d",&a,&b);
            destination = b;
            dfs(a);
            if (destination == -1) {
                printf("YESn");
            } else {
                printf("NOn");
            }
        }
        cl(n);
    }
    return 0;
}

Spoj TFOSS – CPP solution

Problem: http://www.spoj.com/problems/TFOSS/
Given N points, find the longest distance between any two points.
There are two important things to realize when solving the problem:
1) The pairs of such points the distance of which is the maximum are parts of the convex hull. Therefore, it is important to find the convex hull.
2) The size of convex hull is O(N). => We cannot still find the maximum distance naively. There are fast algorithms to find the longest dinstace in a convex polygon (diameter of a convex polygon) – in fact, there are O(N) such algorithms. However, they might be difficult to undestand or hard to implement. O(N logN) is just fast enough.

The idea is to iterate over all points of the convex hull and for each point find the other point for which we maximum distance in O(logN) time. We can use binary search.
Suppose that we are looking at the start of the convex polygon and we calculate the distances to every other vertex of the polygon. It would look something like:
1 6 9 12 55 99 221 88 66 45 33
The 221 would be the maximum. In general, you should realize that we have an ascending sequence and then a descending sequence. You can do binary search to find the peek.

Code:

#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long ll;

struct Point
{
    ll first;
    ll second;
    Point() {};
    Point (ll x, ll y) : first(x), second(y) {};
};


Point points[100002];
Point hull[200005];
size_t hullSize;

ll cross(const Point & A, const Point & B)
{
    return A.first * B.second - A.second*B.first;
}

Point operator - (const Point & A, const Point & B)
{
    return Point(A.first - B.first, A.second - B.second);
}

Point operator + (const Point & A, const Point & B)
{
    return Point(A.first + B.first, A.second + B.second);
}

ll dist(const Point & A, const Point & B)
{
    return (A.first-B.first)*(A.first-B.first) + (A.second-B.second)*(A.second-B.second);
}

bool comp(const Point & A, const Point & B)
{
    ll v1 = cross(A-points[0],B-points[0]);
    if (v1 > 0LL)
    {
        return true;
    }
    else if (v1 < 0LL)
    {
        return false;
    }
    else
    {
        return dist(A,points[0]) < dist(B,points[0]);
    }
}

ll hullSearch(int idx, int to)
{
    int l = idx+1;
    int r = to;
    ll s = 0LL;
    while (l <= r)
    {
        int mid = (l+r)>>1;
        ll l1 = dist(hull[mid-1], hull[idx]);
        ll l2 = dist(hull[mid], hull[idx]);
        ll l3 = dist(hull[mid+1], hull[idx]);
        s = max(l1, max(l2,l3));
        if (l1 < l2 && l2 > l3)
        {
            break;
        }
        else if (l1 <= l2 && l2 <= l3)
        {
            l = mid+1;
        }
        else
        {
            r = mid-1;
        }
    }
    return s;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        int idx = 0;
        for (int i = 0; i < n; ++i)
        {
            ll a,b;
            scanf("%lld%lld",&a,&b);
            points[i] = Point(a,b);
            if (b < points[0].second)
            {
                idx = i;
            }
            else if (b == points[0].second && a < points[0].first)
            {
                idx=i;
            }
        }
        swap(points[0], points[idx]);
        sort(points+1, points+n, comp);
        for (int i = 0; i < n; ++i)
        {
            while (hullSize > 1 && cross(hull[hullSize-1]-hull[hullSize-2], points[i]-hull[hullSize-2]) <= 0LL)
            {
                hullSize -= 1;
            }
            hull[hullSize++] = points[i];
        }
        for (int i = 0; i < hullSize; ++i)
        {
            hull[hullSize+i] = hull[i];
        }
        ll ans = 0LL;
        if (n == 1) hullSize=0;
        for (int i = 0; i < hullSize; ++i)
        {
            ll tmp = hullSearch(i, i+hullSize);
            if ( tmp > ans) ans = tmp;
        }
        printf("%lldn", ans);
        hullSize=0;
    }
    return 0;
}

Spoj FACVSPOW – Cpp solution

Problem: http://www.spoj.com/problems/FACVSPOW/
Shortly, you are given a number A as input and you want to find such an N for which
N! > A^N
You must be able to calculate N! fast enough since O(N) would be too slow.
We can use Stirling’s approximation for which:
N! ~ sqrt(2*PI*N) * (N/e)^N
=> we are searching for such an N for which
sqrt(2*PI*N) * (N/e)^N > A^N
or
N * (2*PI*N)^(1/2N) >= A*e
We can do binary search on N and calculate the answer in log(N).

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;

int calc(int a) {
    int l = 0, r = 10000000000;
    int n=0;
    static double E = exp(1.0);
    static double PI = 3.14159265358979323846;
    double want = E * (double)a;
    while (l <= r) {

        int m = (l+r)/2;
        double val = pow(PI*2.0* ((double)m), 1.0 / (2.0 * (double)m))*(double)m;
        if (val <= want) {
            l = m+1;
        } else {
            r = m-1;
            n = m;
        }

    }

    return n;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int a;
        scanf("%d", &a);
        printf("%dn",calc(a));
    }
    return 0;
}

Spoj MOHIB1 – CPP solution

Problem: http://www.spoj.com/problems/MOHIB1/

Solution:
Let’s say that we want to answer for N. We first check the first ball, which will collide with balls 2,3,..N.
=> In the box we will then have the sum of the numbers from 2…N. Then we pick ball number 2 and it will collide with balls 3…N. => In the box we will then add sum(3…N) * 2.

=> answer for N is
answer(N) = sum (2…N) * 1 + sum(3…N) * 2 + sum(4..N) * 3 + … + sum(N…N)*(N-1)

We have to calculate this in a fast way. We can use dynamic programming for the sums and for the answers as well.
Precomputation should be done in O(N) time where N < = 10^4. Which will give us a O(1) time to answer a query (test). Let us say that we have the answer for all queries till K and we want to check for K+1. this means that the answer would be: sum (2...K) + (K+1) + (sum(3...K) + (K+1)) * 2 + (sum(4...K) + K+1) * 3 + ... + (sum(K...K) + K + 1) * (K-1) + sum(K+1 ... K+1) * K which is the same as answer(K+1) = answer(K) + sum(1...K) * (K+1). We have for sure precomputed already answer(K) and sum (1...K). => transition is very easy.

Code:

#include <cstdio>
#include <iostream>
using namespace std;

typedef unsigned long long ull;

ull dp[10001];
ull ans[10001];

void precompute() {
    for (ull i = 1; i<= 10000ULL; ++i) {
        dp[i] = dp[i-1]+i;
        if (i >= 2ULL) {
            ans[i] = ans[i-1] + dp[i-1]*i;
        }
    }
}

ull comp(int n) {
    return ans[n];
}

int main() {
    precompute();
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        ull ans = comp(n);
        printf("%llun", ans);
    }
    return 0;
}