### rng_58's blog

By rng_58, 8 years ago, ,

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!

• +198

 » 8 years ago, # |   +5 I wonder if !'s are factorial or not.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 I think it's irreleveant in the context of magnitude of that number, with or without factorial :)
•  » » » 8 years ago, # ^ |   +6 ! is not factorial.
 » 8 years ago, # |   0 What a pity!
 » 8 years ago, # | ← Rev. 4 →   +10 It's part of the game. In 2011 GCJ meret didn't win because he used int instead of long long...
 » 8 years ago, # |   +15 Another lesson would be for facebook team to finally set up a command line interface akin to http://code.google.com/p/codejam-commandline/
•  » » 8 years ago, # ^ |   0 I think few OJs have command line submit tool because they are afraided that the users submit too fast.
 » 7 years ago, # |   -65 ok by
 » 7 years ago, # |   -6 good experiences, I had the same problem like your second lesson :-??
 » 7 years ago, # | ← Rev. 2 →   0 this blog is so old, I didn't noticed that! Nothing inteteresting in my message...