Repository Transfer

Finally I have removed all of my github repositories. I have been getting request from a lot of people for removing the repositories or making them private. As github charges too much for maintaining private repositories, I have decided to switch to bitbucket, another wonderful free git server. All of my repositories are set as private. Sorry for the inconvenience. There are already plenty of sites where one can find solutions for online judge problems. My repositories were never intended to be known as a place where you get all the beautiful solutions and then just copy-paste them from your account. That is just meaning-less, stupid and of no good use of-course. Still if you want to see any of my noob-ish solutions, please send me an email.

Thanks for understanding and happy problem solving. I think I am now retired from all these beautiful little things. I will miss these programming contests forever...

SPOJ PRHYME

SPOJ Problem Set (classical) 2737. Perfect Rhyme

A perfect rhyme is not a crime,
it is something that exceeds time,
a bit of science, a piece of art,
soft as a pillow, sharp as a dart.

I really love this little rhyme.

Basically the problem is, you are given a dictionary of words, and some query words. For each query word q, you have to find a dictionary word u such that, u != q and the common suffix of q and u are of maximum length possible. In case there is a tie, the problem requires the lexicographically smallest such word.

This problem can be solved using STL maps and storing the suffixes along with their sorted id, but there is a more elegant solution using Trie data structure, i.e. prefix tree. As we are interested in maximizing common suffix length, we can store the strings in the Trie in reversed form, so now the suffixes will become prefixes in this tree. For each dictionary word, we also need to store its index number, when sorted, as a termination marker for that word, so that, we can find the id of an word easily during the query. On each node, we also need to keep two additional information, the ids of lexicographically smallest and second smallest strings passing through that node, which we call min1 and min2. Initially both should contain an infinite value.

Now for each query word, we also search the word in reversed form. If it is not found in the tree, i.e. a path may exist, but the end marker is not present, then the task is simple, we just return the lexicographically smallest id, which is min1, from the current node, i.e. the node which we reached while trying to match the query string.

But extra cares should be taken when the query string is found on the tree, because, then we have to look for another candidate, for which, we have kept min2, i.e. second lexicographically smallest index. If we can deduce that, going to node x from current node cur, if it evidently means we will end up finding the exact same word, then we can't follow that path, instead, we decide which index to return from current node cur, if its min1 index refers to the word itself, then we return min2, otherwise we return min1. And if we have no other choice but end up at the exact matching point, then we are also sure that there is at least another string which follows the same path, but does not end at our current node, i.e. at least two different words. Then depending on our query word, we select min1 or min2 from our current node.

So, if you know how to code a Trie, it is not really a hard one, but indeed a tricky one.

Hacker Cup 2013 Round 1

Facebook Hacker Cup 2013 Round 1

Facebook hacker cup 2013: Round 1 has been finished, and the results are out as well. The problem set will be found here.

Problem A: Card Game 20 pts problem. If you take a little bit time observing the results, you can easily see what is really happening here. Any number X can be maximum in a set if all the other numbers are less or equal to X, so if we have at least K-1 such numbers, we will be able to make K sized subset where X is the maximum. If we can make M such subsets, X will be added to result M times.

Now, say, for X, there are P numbers which are less or equal to X and P >= K-1. So, we can choose K-1 numbers from P numbers in C(P, K-1) ways, everyone knows that. So, first sort all the numbers, and start from the Kth number (it will be pointless to take previous items, as they will not be maximum for any other subset). So, the Kth number will be added C(K-1, K-1) times, (K+1)th number will be added C(K, K-1) times, next one for C(K+1, K-1) times and so on while the last number will be added C(N-1, K-1) times, consider N as total number of integers.

So the solution is simple (Note, you will need modular inverse to properly count combinations, and the overall complexity is O(n lg n) ):

typedef __int64 i64;

const i64 MOD = 1000000007;
const int MAX = 10009;

i64 a[MAX];
i64 fact[MAX];

class Euclid {
public:
    i64 x, y, d;
    Euclid() {}
    Euclid(i64 _x, i64 _y, i64 _d) : x(_x), y(_y), d(_d) {}
};

Euclid egcd(i64 a, i64 b) {
    if(!b) return Euclid(1, 0, a);
    Euclid r = egcd(b, a % b);
    return Euclid(r.y, r.x - a / b * r.y, r.d);
}

i64 modinv(i64 a, i64 n) {
    Euclid t = egcd(a, n); // here n is always prime, no check needed
    i64 r = t.x % n;
    return (r < 0 ? r + n : r);
}

int main() {
    //freopen("card_game.txt", "r", stdin);
    //freopen("card_game.out", "w", stdout);
    int test, cs, n, k, i;
    i64 sum, num, deno;
    for(fact[0] = i = 1; i < MAX; i++) fact[i] = (fact[i-1] * i) % MOD;
    scanf("%d", &test);
    for(cs = 1; cs <= test; cs++) {
        scanf("%d %d", &n, &k);
        for(i = 0; i < n; i++) scanf("%I64d", &a[i]);
        sort(a, a + n);
        for(sum = 0, num = deno = fact[k-1], i = k-1; i < n;) {
            sum = (sum + (((a[i] * num) % MOD) * modinv(deno, MOD)) % MOD) % MOD;
            i++; num = (num * i) % MOD; deno = (deno * (i-k+1)) % MOD;
        }
        printf("Case #%d: %I64d\n", cs, sum);
    }
    return 0;
}

Problem B: Security 35 pts. I got a cross here :( Will talk about it after describing the solution. Basically two forms of the same string is given, and each one has M segments, all the segments have equal length. As we know, string 1 is actually the real string while string 2 is the permuted string (only whole segments are permuted). So we can run a maximum bipartite matching among the segments of two strings. If they do not match, the the answer is obviously possible. While comparing, if the current character of both string is equal, or any of them is a ? mark, then we also consider them to be equal.

The tricky part of this solution is, we can have multiple matches, and in those case we need to choose the match which will give us lexicographically smallest string. (I failed in this part). It can be achieved in many ways, like putting weights in matching and taking minimum weighted match, or just trying bipartite matching cutting every edge once and see if we get a better match. We then need to copy the letters from string 2 segments to string 1 segments where there is a ? in string 1. Finally, on the remaining ?, just put 'a'. Not posting the code, because it was not fully correct, but the idea is ok (confirmed by others who were able to solve it correctly).

Problem C: Dead Pixels 45 pts. Looks tricky at a first glance. Here, notable thing is, each problem has only one query, i.e. there is not dynamic update + query. So, we don't really need to do anything like segment tree here. Although, segment tree can be used to solve this one as well.

The solution is actually simple, we just sort the points by X axis, and run sliding window of width equal to picture width. We maintain a set of Y values in current window. When we skip a X value, we remove (if available) corresponding y values from the set and update number of possible positions, and then we add the y values (if available) of new X that we've just touched by our window and update accordingly. Here is my solution, pretty simple I should say.

const double EPS = 1e-9;
const int INF = 0x7f7f7f7f;

const int MAX = 1000032;

pii p[MAX];
int W, H, P, Q, N, X, Y, a, b, c, d;
map< int, int > M;
map< int, int >::iterator it;
set< int > S;
set< int > :: iterator Curr, Prev, Next;

void generate() {
    p[0].ff = X, p[0].ss = Y;
    for(int i = 1; i < N; i++) {
        p[i].ff = (p[i - 1].ff * a + p[i - 1].ss * b + 1) % W;
        p[i].ss = (p[i - 1].ff * c + p[i - 1].ss * d + 1) % H;
    }
}

int lowerbound(pii *a, int st, int en, int val) {
    int idx, cnt, stp;
    cnt = en - st;
    while(cnt > 0) {
        stp = cnt >> 1; idx = st + stp;
        if(a[idx].ff < val) st = ++idx, cnt -= stp+1;
        else cnt = stp;
    }
    return st;
}

int upperbound(pii *a, int st, int en, int val) {
    int idx, cnt, stp;
    cnt = en - st;
    while(cnt > 0) {
        stp = cnt >> 1; idx = st + stp;
        if(a[idx].ff <= val) st = ++idx, cnt -= stp+1;
        else cnt = stp;
    }
    return st;
}

inline int span(int lt, int rt) {
    return (rt-Q)-(lt+1)+1;
}

void insert(int cv, int &zeros) {
    int lt, rt, gap;
    it = M.find(cv);
    if(it == M.end()) {
        M.insert(pii(cv, 1));
        S.insert(cv);
        Next = Prev = Curr = S.find(cv);
        Prev--; Next++;
        lt = (Curr == S.begin()) ? -1 : *Prev;
        rt = (Next == S.end()) ? H : *Next;
        gap = span(lt, rt); if(gap > 0) zeros -= gap;
        gap = span(lt, cv); if(gap > 0) zeros += gap;
        gap = span(cv, rt); if(gap > 0) zeros += gap;
    }
    else it->ss++;
}

void remove(int cv, int &zeros) {
    int lt, rt, gap;
    it = M.find(cv); if(it == M.end()) return;
    if(it->ss == 1) {
        Next = Prev = Curr = S.find(cv);
        Prev--; Next++;
        lt = (Curr == S.begin()) ? -1 : *Prev;
        rt = (Next == S.end()) ? H : *Next;
        gap = span(lt, cv); if(gap > 0) zeros -= gap;
        gap = span(cv, rt); if(gap > 0) zeros -= gap;
        gap = span(lt, rt); if(gap > 0) zeros += gap;
        S.erase(Curr);
        M.erase(it);
    }
    else it->ss--;
}


int main() {
    //READ("dead_pixels.txt");
    //WRITE("dead_pixels.out");
    int test, cs, i, j, zeros, tmp, total, st, en;
    scanf("%d", &test);
    for(cs = 1; cs <= test; cs++) {
        scanf("%d %d %d %d %d %d %d %d %d %d %d", &W, &H, &P, &Q, &N, &X, &Y, &a, &b, &c, &d);
        generate();
        sort(p, p + N);
        M.clear(); S.clear();
        zeros = H - Q + 1; total = 0;
        tmp = upperbound(p, 0, N, P-1);
        for(i = 0; i < tmp; i++) {
            insert(p[i].ss, zeros);
        }
        for(i = 0; i <= W - P; i++) {
            total += zeros;
            st = lowerbound(p, 0, N, i);
            en = upperbound(p, 0, N, i);
            for(j = st; j < en; j++) {
                remove(p[j].ss, zeros);
            }
            st = lowerbound(p, 0, N, i+P);
            en = upperbound(p, 0, N, i+P);
            for(j = st; j < en; j++) {
                insert(p[j].ss, zeros);
            }
        }
        printf("Case #%d: %d\n", cs, total);
    }
    return 0;
}

However, could not make it to top 500 because of the time penalty and the mistake in problem B. Overall, problems were nice. And again, 45 pts one was easier than the 35 pts.