TLE in O(n)??? - Codeforces

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

TLE in O(n)???

Автор Kuber, история, 10 месяцев назад, По-английски

Hi everyone, please consider the following submission:

https://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.

tle

-3

Kuber
10 месяцев назад
5

Комментарии (5)

Написать комментарий?

nor

10 месяцев назад, # |

+38

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

→ Ответить

Alesh

10 месяцев назад, # |

+25

use vector<int>& v in next time!

→ Ответить

Kuber

10 месяцев назад, # ^ |

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

→ Ответить

treasuryonly

10 месяцев назад, # ^ |

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.

→ Ответить