sudhanshu090's blog

By sudhanshu090, history, 6 weeks ago, In English

Problem 1676D : X-Sum

I solved the problem using brute force as the constrains were low. In my first try I used another function to do some iterations in a 2D matrix.

Looking at the editorial, they used the same logic but without using another function. So, I copy pasted my entire 'helper' function in my 'main-solver' function and the time difference was pretty huge. Should we avoid using functions in CP?

Using extra function : 168328426 Time taken : 1185ms

Without using another function : 168328365 Time taken : 46ms

Is this something we should take care of in contests?

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

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Nope, calling a function takes time only when you passes arguments without the "reference", as passing the arguments without the reference, function needs to copy the arguments in some temporary memory to use it which takes extra time. i.e. copying an array or vector takes $$$O(size)$$$.

So if you pass with a reference the function willn't take any extra time. To do this you just need to add & before variable name.

Like you may write your function as int calculate_for(vector<vector<int>> &board, int i, int j, int rows, int cols) instead of int calculate_for(vector<vector<int>> board, int i, int j, int rows, int cols).

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. I tried submitting again and it passed with 30ms.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually no. Here, you are passing by value a 2D vector which is taking O(N) time for each function calling where N = size of vector. you can declare the vector globally or use pass by reference.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

yes