idonthatephy's blog

TLE using binary search
By idonthatephy, history, 21 month(s) ago, In English

I have seen people use binary search in this particular problem 1443C - The Delivery Dilemma but my submission is getting TLE in testcase 9 166040767 Can anyone explain why is that? for example this binary search solution passed 97454890

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

Comments Comments (4)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Here is your corrected submision. Reason for TLE is passing the whole vector to function (in brief: every time you pass vector to function, you make his copy, and it's ineffective) instead of passing only his reference.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    that's not entirely true. it takes O(n) to copy a vector, and the binary search runs in O(log(1e9)), which is essentially O(32*n) which should pass. See their testcase 8. There's something else that's wrong in their code.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But it passed when I passed the reference of the vectors.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That is an O(n) speedup, which is nevertheless a lot, and definitely enough to compensate for other problems. There is something else that is wrong here, not the vector copy (I've made plenty of Binary Searches which copy vectors).

        → Reply