forgotter's blog

By forgotter, history, 21 month(s) ago, In English

My friend one_punch recently shared a Google foobar challenge referral with me. I've completed most levels of it and really liked few of those questions. (We can talk more on questions separately). Now, I myself have two more referrals to invite others.

I have come up with idea that interested people (cf users) can fill up a form, so I could have a list of interested peoples. I'd sort the list in decreasing order of rating and one by one invite most of them.

With only two referrals, how can I invite everyone? After I send a referral to someone (on list), that person would send me one (new) referral back and I will again be left with two referrals and this can keep going on until the list is exhausted or someone doesn't sends back a referral.

Something about challenge:
Total levels : 5
Total questions : 1+2+3+2+1
Language : Java/ Python 2.7 (yes,it sucks!)
A referral is given after completing of level 2 and level 4.
After completing level 3, you'll be asked for your details to share with a recruiter.

Estimated difficulty:
Level 1: Div 2A
Level 2: Div 2B
Level 3: Div 2D
Level 4: Div 2E
Level 5: Haven't solved it yet.
One might get easier or difficult questions depending upon their luck.

Please fill up this form before May 1, 12p.m. IST.

P.S. If anyone has any suggestion to make, you're welcome:)

P.P.S. I've started sending the invite as per above mentioned order. I'm sending it as codeforces message. (It might take some time for your turn to come, so please wait till then.)

Update: The list conatins 166 people. On average, the referral passes through 4 people in a day (So please try to be quick, when it's your turn). You also encouraged to try out ways to trigger the invitation (search google). Click here to generate a new invite. Thanks to temp481 for providing the link.

Re: Generator website is down. As suggested by hydro_lyte, Triggering it with known keywords can give you invitation. Search for "c++ move semantics" 2-3 times and you will receive an invitation.. "Java Arraylist" is also a known search keyword, you can try your luck. I hope most of you manage to get it without waiting for your turn in the queue.

Read more »

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

By forgotter, history, 3 years ago, In English

I have been trying to solve this question for a very long time: (29 digits), I have already solved the task with smaller constraints (19 digits).

My implementation

Prime_factorization (num):
    prime_factor = pollard_rho (num)
    while (miller_rabin( prime_factor) != true):
        prime_factor = miller_rabin( prime_factor )
    while num%prime_factor == 0:
        num /= prime_factor

Here pollard-rho guesses a suitable prime factor and miller-rabin checks if returned factor is a prime.

My implementation (Code, C++) :

Bugs in current implementation:

  1. The prime-numbers used in miller-rabin needs to be more, to check for higher constraints.

  2. Overflow (maybe)

I would like to know

  1. How to make my code more faster

  2. How to handle inputs larger than 10^18 (should I write one library for myself which can perform basic operations (+,-,*,/) on string.

Also, if someone can provide with a good tutorial on quadratic sieve. And with implementation would be too good to have.

Thanks for reading.

P.S: This is my first blog post. Please ignore minor mistakes.

Read more »

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