Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя duongtnhat

Автор duongtnhat, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :)