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.