Athreya1900's blog

Recent Div3 Contest Query
By Athreya1900, history, 4 years ago, In English

I was trying to code the problem Candies, yesterday and my logic was

In order to find a solution to

x + 2x + 4x ... = n

x(2^k — 1) = n

x = n / (2^k — 1 )

So I go through the factors of n in square root n time and check if they're of the same form as the denominator.

But apparently it times out, can someone shed some light on this?

Link to my submission

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why iterate over factors of n? You know that answer exists, so just iterate over k from 2 to 31 and if the modulo is 0, print x corresponding to the k value.

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

    Yes, I got that idea later but didn't change the code as I thought it would pass. My question was even though it isn't the most optimal complexity, it should squeeze through the TL ?

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

      I would recommend using __builtin_popcount(x) = 1 to check for power of 2. Also n goes to 1e9 so your factorization works in 1e4, and for 1e4 test cases , complexity goes to nearly 1e8 , which is hard to squeeze in 1 sec.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
hint
Solution spoil
→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Your program run in $$$O(\sqrt{N})$$$ each test case. Because maximum $$$T$$$ is $$$10^4$$$ and $$$N$$$ is $$$10^9$$$, so it will run about $$$3*10^8$$$ operation which it make TLE (1 second = $$$10^7$$$ and I never try make $$$10^8$$$ operation with Time Limit 1 second). One another solution is iterate all k from 1 to $$$log2(n+1)$$$ so $$$n mod 2^k-1 = 0$$$ and you will find $$$x$$$. This complexity worth $$$O(log(N))$$$ for find $$$k$$$ each test case and run about $$$3*10^5$$$ operation with worst case.

Hope it's useful. Sorry for my bad English.

→ Reply