rng_58's blog

My sad story
By rng_58, 12 years ago, In English

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!

  • Vote: I like it
  • +198
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I wonder if !'s are factorial or not.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think it's irreleveant in the context of magnitude of that number, with or without factorial :)

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What a pity!

→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it +10 Vote: I do not like it

It's part of the game. In 2011 GCJ meret didn't win because he used int instead of long long...

→ Reply
»
12 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Another lesson would be for facebook team to finally set up a command line interface akin to http://code.google.com/p/codejam-commandline/

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think few OJs have command line submit tool because they are afraided that the users submit too fast.

    → Reply
»
11 years ago, # |
  Vote: I like it -65 Vote: I do not like it

ok by

→ Reply
»
11 years ago, # |
  Vote: I like it -6 Vote: I do not like it

good experiences, I had the same problem like your second lesson :-??

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

this blog is so old, I didn't noticed that! Nothing inteteresting in my message...

→ Reply