8

I recently found this site called codechef, where you can submit solutions to problems. I had submitted two answers for a question, one in C and the other in C++. Both codes are almost the same. But when the code I submitted in C was executed in 4.89s, the code I submitted in C++ was timed out (more than 8 seconds). How is this possible? Where does the time go?

The question was:

Input

The input begins with two positive integers n k (n, k<=107). The next n lines of input contain one positive integer ti, not greater than 10^9, each.

Output

Write a single integer to output, denoting how many integers ti are divisible by k.

Example

Input:
7 3
1
51
966369
7
9
999996
11

Output:
4

My code in C:

 #include<stdio.h>
   
 int main()  {
   
   int n,k,t;
   scanf("%d %d",&n,&k);
   int i,num=0;
   for(i=0;i<n;i++)  {
     scanf("%d",&t);
     if(t%k==0)  num++;
   }     
   
   printf("%d",num);
    
   return 0;
 }

My Code in C++:

 #include<iostream>
  
 using namespace std;
   
 int main()  {
  
   int n, k, t,num=0;
   cin>>n>>k;
   for(int i=0;i<n;i++)  {
     cin>>t;
     if(t%k==0)  num++;
   }
  
   cout<<num;
   return 0;
 }
Community
  • 1
  • 1
arry36
  • 142
  • 10
  • Sorry! That was 10^9. Copy paste error. :) – arry36 Mar 06 '14 at 13:04
  • 1
    First of all try C++ with cstdio. – jacekmigacz Mar 06 '14 at 13:04
  • 1
    @any36 - So your timing included how fast someone can type in the input?? I see calls to scanf() in the C code and cin in the C++ code. Is this included in the timing test? – PaulMcKenzie Mar 06 '14 at 13:18
  • @PaulMcKenzie : The site tests the code with preset cases. So, I guess it doesn't take up time to type in the input. – arry36 Mar 06 '14 at 13:20
  • @any36 - So you're not sure what they're doing with the I/O. If that's the case, then in my opinion, the timings are flawed. I could see if you're timing non I/O code, or even timing how long it takes to read and process a large file, but even that takes many test runs to coalesce around a firm result. – PaulMcKenzie Mar 06 '14 at 13:24
  • You are using different io calls? Is it possible to use same calls and see if looks similar? If yes, then its really cin/out vs scanf/printf. At the least you can just compile C code with Cpp compiler and see how it goes – aks Mar 06 '14 at 13:32
  • @PaulMcKenzie - From Codechef's FAQs: Codechef might test your code multiple times with different input files. Your program must read, process, and output the result for an input file within the specified time limit. If your code gives the correct answer within the time limit for each input file, the execution time displayed is the total of the time spent for each test case. – arry36 Mar 06 '14 at 13:34
  • @aks: Yes, I rewrote the C++ code using scanf and printf and it actually took 0.2s less than the code in C – arry36 Mar 06 '14 at 13:35

2 Answers2

28

The code is not really the same even though they do the same thing

The c++ version uses cin and streams which are slower than scanf etc by default.

By default, cin/cout waste time synchronizing themselves with the C library’s stdio buffers, so that you can freely intermix calls to scanf/printf with operations on cin/cout. You can turn this off with std::ios_base::sync_with_stdio(false);

By doing this the time taken will more or less be similar I would expect

const_ref
  • 4,016
  • 3
  • 23
  • 38
  • 1
    +1 for pointing out `sync_with_stdio` instead of the classy `iostreams are slow` which is just wrong. – Sebastian Mach Mar 06 '14 at 13:19
  • I added the sync_with_stdio and now the code runs in 4.78s. :) – arry36 Mar 06 '14 at 13:43
  • @arry36 As I thought it would ;) – const_ref Mar 06 '14 at 13:43
  • Is it a good programming practice to replace all the cin/cout with scanf/printf in cpp? – arry36 Mar 06 '14 at 13:49
  • 1
    @arry36 For type safety reasons I stick with using streams, but other people I know do do it. If I were you I wouldnt however, C++ should be written like C++ imo ;) – const_ref Mar 06 '14 at 13:51
  • without explicitly setting `std::ios_base::sync_with_stdio(false)` it doesn't only get synced with C's `stdio` but is also threadsafe which c doesn't guarantee afaik and needs extra time. – AliciaBytes Mar 06 '14 at 13:54
  • SO the 'sync_with_stdio' lets the streams to work independently of each other. But what is the trade-off? – arry36 Mar 06 '14 at 13:58
  • 1
    The trade off is that C++ streams are no longer synchronized to the standard C streams after each input/output operation, so ideally you need to choose either/or and cant mix both – const_ref Mar 06 '14 at 14:01
  • Oh, if the sync in turned on, you can mix scanf and cin and the buffer is always synchronized? Sorry for bothering you. I just don't understand what is being synchronized. – arry36 Mar 06 '14 at 14:04
  • 1
    Yes. See here for more info: http://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio – const_ref Mar 06 '14 at 14:05
  • 1
    Oh! I get it now. All the streams in C++ are in synchronization all the time. That is why using streams take more time. Thank you so much! :) – arry36 Mar 06 '14 at 14:06
1

I usually add these 3 lines in my code just after the main() for faster input output : 

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

So , Try this : 

int main()  
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   int n, k, t,num=0;
   cin>>n>>k;
   for(int i=0;i<n;i++)  {
     cin>>t;
     if(t%k==0)  num++;
   }

   cout<<num;
   return 0;
 }
Vishal Srivastav
  • 563
  • 6
  • 13