supermarine's blog

Not sure why I am getting TLE
By supermarine, history, 4 years ago, In English

I solved this question 1461D using a brute force method to find all valid sums in the array but one of my submission which seems correct to me doesnt seem to be working while another submission which is quite similar but just involves splitting and using it in a new vector gives a correct answer. Please help ?

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

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

Pass your vector by reference and that's all.

void rec(vt<int> a, int lo, int hi){

Correct one:

void rec(vt<int> &a, int lo, int hi){

I have resubmitted it here: 101179136

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

    Thanks for that can you pls explain why it works that way ?

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

      Every time the function is called, a separate copy of the vector is created. By passing it by reference, you can avoid that. That applies to strings too, or any other "large container"

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

      You should always pass vector by reference to a function.

      If a vector is passed by value, a new temporary vector will be copied. And copying a vector means dynamically allocating new memory for a new vector, copying all elements so it's much more slower.

      If the vector is small, there is no problem, but if it is large, then the parameter-passing itself could consume a lot of resources.

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

        Ok thanks for your help

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

        But if without reference it means that we are copying the vector repeatedly then this submission which creates new vector for every stage also shouldnt work . Can you pls explain why this one works correctly ?

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

          Because he's not passing the whole vector. He's dividing current vector into two halves, So in every recursion call vector size is reduced to half so space would be ONlogN.

          → Reply