Kuber's blog

TLE in O(n)???
By Kuber, history, 11 months ago, In English

Hi everyone, please consider the following submission:

https://mirror.codeforces.com/problemset/submission/1467/215118514

The code is in O(n), yet I'm getting TLE. I changed cin to scanf. In that I got my answer different on CF server and local machine. So, I changed it back to cin.

I don't think I'm calling too many functions. They all run in O(1) time.

Tags tle
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it +38 Vote: I do not like it

When you pass a vector by value, it gets copied over. So the complexity is $$$O(n^2)$$$ and not $$$O(n)$$$.

→ Reply
»
11 months ago, # |
  Vote: I like it +25 Vote: I do not like it

use vector<int>& v in next time!

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I passed it by value because I wanted to make changes to the vector and not reflect it in the main function.

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it 
      ll calc(int i, vector<ll> &v){ // use &v to pass by reference
	ll n;
	ll temp = v[i]; // save the current value
	v[i] = v[i-1];
	n = hov(i, v) + hov(i-1, v) + hov(i+1, v);
	v[i] = temp; // restore the value
	return n;
}

      You can save the current value and restore later then the original in the main function will not be changed.

      → Reply
»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

bool hov(int i, vector<ll> &v)

ll calc(int i, vector<ll> &v)

You can update the function signature like this and submit again.

→ Reply