## Tuesday, February 5, 2013

### 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() {
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.

1. amar jodio prothom problem ta implementation e bhul hoye geche..kintu prothom problem ta java r BigInteger class dieo implement kora jeto to??modular inverse na kore,straight forward nCk calculate kore??
ar tomar mail id ta ektu dile valo hoiii...

1. Nope, I don't think java BigInteger could do that. Welcome to my blog, thanks for visiting, and please join/subscribe :)

2. modular inverse nie khub i somosya i porechii..tumi bolo na nCk mod prime eta kivabe ber kora sobcheye better hobe??ami koyekta algorithm dekhlam sob i eki rkom oi modular inverse diye..kintu oigulo konotaii thikthak lagche na..karon dhoro 6C3(mod 3) =20(mod 3)=2 hoar kotha to?kintu oisob algo te output random aasche..tumii ekta thik algorithm bolo na amake...ar tomar blog dekhe ar tomar spoj rank dekhe ami tomar fan hoye gechii..:)

1. modular inverse is only applicable when both the numbers are co-prime. i.e. modinv(a, m) exists, only when gcd(a, m) == 1. if we can store nCr without overflowing, then there is no need for modular inverse. because, we can just mod it after the complete calculation. we need modular inverse in cases like:
(a / b) % m, which is actually (a * modinv(b, m) ) % m and this will work only when b,m are co-prime.

there is not "perfect" algorithm for finding nCr though, it depends on the size of n, r, how many times they are asked for, is there any consecutiveness among the queries and so on. for example, as you can see in problem A, I didnt find every nCr separately, I calculated it from the previous step.

if you only need it for once, you can also find it in terms of O(n) iterating through n! and dividing it at the same time.

there also this dp approach for smaller cases when n*r can be stored into memory, also, you do not need modular inverse here, cause the process is additive
http://zobayer.blogspot.com/2009/08/calculate-ncr-using-dp.html