ghoshsai5000's blog

How to speed up input in scanf in C ?
By ghoshsai5000, history, 8 years ago, In English

I have been solving this problem and here's my code and my test cases — http://mirror.codeforces.com/contest/717/submission/25885501

I got a Time Limit Exceeded. And I'm not sure if it's because of the logic (because the processing is O(n^2) ) or if it's because the input is taking a lot of time. Can someone suggest ways on speedening up the code so that I don't get a TLE ?

Thanks

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

Comments Comments (14)
| Write comment?
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I can see that you are using selection sort in your code which works in O(n^2) not O(n)

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

    You're right. That was a typo. I meant to write O(n^2). Can you give me suggestions on getting past the TLE ?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      This is a simple greedy problem. Yes. You need to sort but you can use the c++ library sort instead of your own (unless you have strong reasons to). The complexity of the library implementation of sort is O(nlogn). The only thing you need to take care of is to use long long instead of int.

      I have posted a link to my approach below. Hope you won't mind the ugly indentation. I typed the entire code on my phone.

      My submission: here

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

        Wow! Thanks for the code. I'll try re-writing the code with quicksort now. I'm a beginner programmer so I don't want to use library functions and prefer implementing it on my own so that I can learn. Your indentation is fine. Thanks !

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

        Please help me. Can you explain why it needs to be long long because if it's mod 10007, int should be enough. I wrote it with quick sort but there appears to be an issue.

        This is a program I wrote where I used unsigned long along with quick sort. I didn't get a TLE but I got a wrong answer for some reason.

        This is basically the same code with the data type changed to long long with the %I64d format specifier. I'm get a TLE in this case. Please help.

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

          1) The reason why you got WA is indeed because of the lack of use of long long. You have to use long long as the laziness level and task difficulty may be large (i.e. up to 1e5). Yes. You mod the final answer by 10007. BUT, you will multiply the 2 large numbers first. What do you get if you multiply 1e5 and 1e5 (recall the addition of powers when you multiply real numbers)? Do you think that this can fit into an integer (max representation value is 2^32-1)? So, even before you can mod the result of this multiplication, there is already an overflow...

          2) Did you attend an algorithms class before? If you did you would know that the worse case complexity of quick sort depends upon its pivot selection. I can see that you are choosing the first element as pivot. Now what if you try to sort an array that is sorted in descending order? That said, this might not be the cause of your TLE. But, when I ran the code on my machine, it gave me segmentation fault. Using printf statements, I narrowed the fault to your sorting method. But it may be because of the values of variables as well.

          3) Do you know how to use a debugger? If you don't, it would be good to learn (I would recommend using the visual debugger in netbeans). Print the values of each of your variables to see if they are what you expect. That way, you would be able to pinpoint minor faults such as the one in 2).

          p.s. If you really want to code a O(nlogn) sort, I suggest that you use merge sort (even though I would just use the STL sort).

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

            1. Thanks for the explanation

            2. I didn't know that. I thought quick sort was the best sorting method. What was the reason for the segmentation fault here ? Was it because all the variables had the same value in Case 3 ?

            3. I don't know how to use a debugger. Is it like an IDE ? I use CodeBlocks. Does it have that feature ?

            I'll try it out with Merge Sort. Thanks for your help.

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

              Quicksort is not the best sorting method. It's easy to hack manually written quicksort with a lot of duplicated elements, even if the pivot is randomly selected.

              Just sort(a, a+n) is fine. STL sort would fallback to heapsort when quicksort would be slow.

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

                So, in competitive programming you're forced to use the inbuilt sort, because the test cases are too strong for any one sorting algorithm ?

                And I guess implementing a fallback would be difficult. I don't know how to do that.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it +13 Vote: I do not like it

                  no, you can spend some minutes to code your own mergesort or any N log N sort.

                  Or just spend 10 seconds to type sort(a, a+N).

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

    Hi there,

    How are you ?

    I just wanted to let you know that I finally got an acceptance on this problem. I gave up doing this trying to use my own sort. I learnt that the STL sort isn't a simple sorting algorithm like quick sort. It changes the algorithm if the level of recursion goes too deep. And, I don't know how to count for number of recursions and change the algorithm accordingly.

    Anyway, thanks for your help.

    One more thing. I'm not that experienced with C++ ...

    But, I noticed that when I didn't write

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

    I got acceptance in about 170 seconds, and when I put it in, I got acceptance in 40 seconds. Can you explain what these two lines do and why they speed the program up ?

    Thanks. Here and hereare my codes which got acceptance.

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

      Happy to hear that you managed to get your code accepted.

      As for your question, I think that the answer in this link explains it better than I would.

      On a side note, you can simply use your C-style I/O (i.e. scanf and printf) in C++ as they do not have this synching problem and are equally fast.

      As you get more familiar with Competitive Programming, you will realise that there is an even faster way to read and print input by using getchar and putchar. However, I/O speed is one thing and coding an optimal algorithm is another.

      If your algorithm is inefficient, then no amount of I/O optimisation will earn you the AC.

      Just my 2 cents.

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

        My experience is that getchar/putchar is sometimes slower than scanf/printf since normal I/O functions lock themselves to avoid reentering. Since most algorithm contests are single threaded, if we really want to maximize the I/O efficiency we should use getchar_unlocked (for POSIX).

        One of my teammates thought he was clever and used getchar everywhere. I changed his program to use scanf after 5 TLEs. Then we got AC.

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

Auto comment: topic has been updated by ghoshsai5000 (previous revision, new revision, compare).

→ Reply