I've seen two sources that claim Facebook Hacker Cup will begin with the qualification rounds Jan 8-11 this year, but it's getting awfully close to January 8th and I am somewhat skeptical given that the Facebook page hasn't been active since February 2014 (facebook.com/hackercup).

Anyone else planning to compete that knows some more information?

• Prove that the lower bound for any deterministic comparison-based sorting algorithm is (Well known) proof outline: model the comparisons as a binary decision tree; the bottom leaves are the n! permutations of the original sequence (one of which is the sorted). The height of the tree h satisfies 2^h >= n! so h >= log(n!) = Omega(n log n).

• Consider the following problems:

1. Given a sequence, determine if any two elements are equal.
2. Given two sets, determine if they are equal.
3. Given two sets, determine if they intersect.

Each has a simple solution by sorting and also a lower bound of Omega(n log n). Are there elementary proofs of this? (say, for a first-year algorithm analysis class)

The most similar to the one for sorting I found is this.

You are given a circle whose perimeter contains points p1, p2, ..., pn in clockwise order as well as points q1, q2, ..., qn (no order specified). For each i, a segment is drawn from pi to qi. Find the number of intersections in O(n log^2 n) time.

I considered that, with points pi, pj, qi, qj for some 1 <= i < j <= n:

1. There is no intersection when exactly one of qi, qj is between pi and pj and the other is not.

2. If the order is pi, pj, qi, qj or pi, qj, qi, pj then pi-qi and pj-qj intersect.

I solved a simpler problem (with n segments drawn between 2 horizontal lines) by counting inversions and tried to do something similar here, but it doesn't seem like the ordering in the circle problem is transitive. I also can't figure out how one would possibly get a runtime of O(n log^2 n). Could anyone give me some pointers on how to go about solving this?

The first two-hour 101 Hack of 2014 is taking place tomorrow on HackerRank from 11:30 am to 1:30 pm (U.S. Eastern time).

Excited for tomorrow's five challenges! I hope to see some others there.

So apparently there's no bfs tag on the Problemset, at least on the first two pages.

Could anyone recommend some less advanced BFS problems, either here or on Topcoder?

How well should one perform consistently in Division 2 contests to move from blue to purple, and how well should one perform from there in Division 1 to get to orange? I would like to gauge how I'm doing in comparison to others as I move along.

Normally I would do this myself, but it's too hard to find it out from the raw match results so I was wondering if someone could answer from experience. :)