duongtnhat's blog

Problem with python??
By duongtnhat, history, 8 years ago, In English

17754492 Here is my solution for 670D1 - Magic Powder - 1

I dont know why it catch time limit exceeded on test 148. And then, I try g = l + (r-l+1) / 2, it is accepted? (g is midle in binary search), Im a newbie in python, and sorry for my bad in English

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

Comments Comments (3)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There have been a few posts here and elsewhere on improving Python performance that I'd search for, but one solution that often works is to use PyPy. See 17765365.

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

I think that the reason is integer overflow.

Since you uses l, r = 0, 2000000010, the g = (l + r) / 2 instruction can overflow the max integer value 231 - 1.

In C/C++, this would mean Wrong answer. In Python, this only means that the integer will be upgraded internally (without you noticing) to a more expensive integer type, which has arbitrary precision. Of course, the arbitrary precision integer has some overhead, which in your case led to Time limit exceeded.

If you use g = l + (r - l) / 2, you always stay inside the standard integer range, so Python has no need to upgrade to arbitrary precision integer.

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

For this sort of Binary Search problems i.e. you need to find the maximum value you can get under the constraint you should always use mid = ( low + high + 1 ) / 2.

Why the added 1 ? Look at your implementation and see that there is a scope for infinite loop . If you are stuck you can see the Topcoder tutorial . Hope this helps :)

→ Reply