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

TLE in O(n)???
Автор Kuber, история, 16 месяцев назад, По-английски

Hi everyone, please consider the following submission:

https://codeforces.net/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
  • Проголосовать: не нравится

»
16 месяцев назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

use vector<int>& v in next time!

→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится 
      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.

      → Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить