vinhhocptit's blog

Does scanf compared to cin really affects complexity that much ?
By vinhhocptit, history, 3 months ago, In English

Today, I had spent hours trying to solve problem : (https://codeforces.net/contest/1334/problem/C) and submitted several solutions with an O(n) complexity, but I kept getting a TLE. After some further inspection, I changed from using cin to scanf, and my solution was finally accepted. While it's well-known that scanf is slightly faster than cin, I was surprised by how much of a difference it actually made in this case.

TLE Code : 284211972 Accepted Code : 284212724

This blog may not be overly educational, but I just want to highlight that even a O(n) solution can lead to a TLE error. Understanding this can help you avoid the frustration and wasted time that I experienced.

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

»
3 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);

Use this if you want to use cin/cout

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

    what does cout.tie(nullptr) do?

    explanation

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -28 Vote: I do not like it

      cout = Output + cout.flush(). But if you use cout.tie(nullptr) it will untie the cin with cout. So cout = Output only. In interective problems if you don't use cout.tie(nullptr); you don't have to use flush manually as it will be done automatically.

      Using this will help a lot with time complexity specially when you have multiple test cases.

      And forgive my poor English

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

      Nothing because by default cout is not tied to anything.

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it -19 Vote: I do not like it

        I think cout is tied with cin. Everytime you use cin after a cout it flushes the output. Though I am not sure if cout.tie(nullptr) or cin.tie(nullptr); does the work of untie.

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

          Actually, not. You can double check this, just print the result of std::cout.tie(nullptr) (the method returns the current tied stream and if there is no tied stream, a null pointer is returned).

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

            Yeah, Got it.So, I am just using a line for no reason.I just need cin.tie(nullptr);. Thanks.

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

I thought everyone learns to put cin.tie(0) -> sync_with_stdio(0) in their code the first day they start cp.

Guess not :/

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

    I know thats a fundamental thing in CP but I never thought that it would matters that much but I guess im wrong lol.

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

      Will highly recommend you to watch this vid Here You will be able to visualise how fast it is and why does it happen ?

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

it does not affect complexity, QED.

→ Reply
»
2 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

std::cin is tied (or synchronized) with std::cout by default in C++, which means it will ensure that your stdout will always be flushed before the input operations. It makes your program slows due to the fact that you have to flush the output before you take the next input from stdin. If you provide those: 

ios::sync_with_stdio(false);
cin.tie(0);

Then they are untied, and the output will only be flushed when stdout is full, or your program has been terminated. That's why you see the whole output after reading and processing all test cases. And that's why it is said that using endl is not a good practice as it flush your output immediately, which means using those two lines of codes above are useless. This blog is quite nice and you should take a look.

(I thought I have remind you before but you didn't really care about that).

→ Reply