Today I participated in Facebook Hacker Cup Round 3. 100 people participated and top 25 will advance to the onsite round in California.

The contest has started. I glanced at titles of problems and samples, and decided to solve "Divisor Function Optimization" first. It was a number theory problem, so I was confident that I can solve this problem. However, after thinking for a while, I noticed that I need to calculate all primes <= 2^250000! (of course, it turned out to be wrong later.) It seemed to be impossible, so I read the other two problems.

"Trapezoids". My first implession was (I don't know whether it's correct or not): convert trapezoids to rectangles in 2D plane and do some sweep line algorithm. It looked hard to implement, so I decided to skip it.

"Unfriending". Try all local-maximal subsequences that can be removed? It's quite easy! I implemented and debugged... oh, I didn't read the problem correctly!

Meanwhile a few people solved "Trapezoids", but let's return to "Divisor Function Optimization". I missed one condition! b/a <= 25! Then it's quite easy, just solve for each prime independently and calculate the product. (there's some more details, e.g. precalculating product of primes, but I'll omit details here.)

I implemented, debugged, and passed all examples. I tested maximal case (actually it wasn't): (a = 250000, b = 10000) * 100000 times. It worked in 13s, which means 260s for 20 max data, so I decided to submit.

I downloaded the input file carefully, saved it on my computer, and executed my program: "./a < divisor_function_optimization.txt | tee divisor.out" But my program worked very slowly.

30 seconds left...

Case #19: 49898798639490 49944512088364...

Looks very dangerous.

Finally 8 seconds before the deadline,

Case #20: 49843150065040 49981240725189

I clicked "submit" button very quickly.

Then my sad story comes. I saved output file in D:/facebook folder, but the browser shows different folder! I don't have time to find D:/facebook!

...I got upset and immediately went to bed.

Two lessons:

1) When time limit is tight, use computer as quickly as possible.

2) Check current folder of the browser before the program terminates!