zzzzsust19's blog

Comparing the given problem and time complexity of my solution, why is the time taken so high
By zzzzsust19, history, 2 years ago, In English

Problem link: https://codeforces.net/problemset/problem/1294/D

My submission: https://codeforces.net/contest/1294/submission/172332862

The problem I am trying to solve has constraints as given, 1 <= q, x <= 4 * 10^5 The time complexity of the solution I have submitted is around O(2 * q). It's basically a linear time solution.

My expectation was that the highest time it would take would be around 100-200 ms. But the solution took around 1200 ms at worst case. Which is far higher than I expected. What is the reason behind this high time complexity

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Try this code:

int n = 200000;
for (int i = 0; i < n; i++) {
    cin >> a[i];
    cout << a[i] << '\n';
}

This code will be not fast. Because every time between std::cin and std::cout there runs a buffer flush operation.

To answer your question faster, use cin.tie(0) right after ios_base::sync_with_stdio

https://codeforces.net/contest/1294/submission/172333686 (without cin.tie)

https://codeforces.net/contest/1294/submission/172333645 (with cin.tie)

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

    Thank you very much for the info, I have faced many cases like this where I get higher execution time than expected, I believe this explains it.

    → Reply