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