Enormous Input Test

a small python script to generate a sample input to this program:

import os
import random

f = open("sample.txt","w")
lineno=random.randint(0,1000000)
divisor=random.randint(0,10000000)
f.write(str(lineno) " " str(divisor) "\n")
for i in range(0,lineno):
f.write(str(random.randint(0,1000000000)) "\n")
f.close()

This might help :)

Hi I need help on this problem. My Java program times out. As solutions of this problem are not available I am unable to find how to optimise my approach. Here is my code. Please tell me how to improvise. I think this is the main problem why my other programs are also getting timed out.

import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);//to read from input console
int n=sc.nextInt();
int k=sc.nextInt();
int res=0; //the result
for(int i=0;i

for(int i=0;i

Why is my comment getting truncated?

@Siddharth Saha

As no one has replied, I think whats happening is that your next term is '' sign. I think there might be a way to escape the same. Or use the main forums. They have [code][/code] tags I think.

Hehe, I did it too. I mean the (less than) sign. Being mistaken for html/xml tags

@Siddharth Saha: the problem has been solved, now u can post ur code without it getting truncated.

y i am getting time limit excedded?

@prasanna: that's the difference between scanf/printf and cin/cout.

My scala program given a test with n = 10^6 runs under 3 seconds on my laptop (Core 2 Duo, 1.6Ghz)

Why would it timeout on your servers?

i did at once ;)

can we not look at other people's solutions to this problem?

@siddharth This is under consideration.

Would love to see the optimized solutions to this problem.

solutions for this problem are now public...

my program works fine on vs 2005, but here it is giving compilation err...any ideas?

I must appreciate the effort MS has put into optimizing the performance of their Console IO classes. Its awesome how no one has come close to beating the straightforward C# code for this problem.

The fastest solutions in C/C use the fread( ) function.... But alas this function has known upstream bug and as such is not working properly in my specs OpenSuse 11.1, gcc 4.3.2, P4 2.8Ghz.... Though I know the gcc version is higher in my case than the Online judge system... but the code is perfectly ANSI compliant... Some are resorting to use fgets( ) and such string functions but they are not as fast as fread( )

LoL. I made it first try with 7.92 seconds. (8 second time limit.)

I am getting a compiler error on submission but I can run the same with the correct output on my desktop http://www.codechef.com/viewsolution/70027/
Any pointers?

Please don't use conio.h. Read the faq at http://blog.codechef.com/2009/06/29/frequently-asked-questions/ for more information and http://www.codechef.com/help for sample source code in your language.

Hi all I need help on this problem too, I can't figure out why I'm getting a runtime error for me code, it runs fine when i compile it, what am i missing?

10^7 > 1000000

if i size my array to 10^7 the program crashes, is there another way to size it besides just typing in 10000000

Your code crashes because you are declaring the entire array inside your main function, and as a result on the stack. Declare it as a global variable. It won't crash then.

Ok thanks, I changed the type to static and it runs and complies but now receive a "wrong answer" even though all of the test cases ive run seem to work? Does anyone see a case that would cause it to fail?

http://www.codechef.com/viewsolution/18435/ ..... successfully submitted code is same as mine .... it shows time exceeds ... any suggestions?

http://www.codechef.com/viewsolution/72328/ ... this is correct link ... sorry for the mistake.

@bob All submissions are available for this problem. You can test your code on random inputs and verify your results with an accepted solution.

It is surprising to see that the code written in c++ gave a time-limit exceeded reply, where as the same code, after changing cout and cin to printf and scanf gave the answer is correct. Any reliable reason?? Provide different cases with which the problem is tested against in examples. The programs can be tested with our compilers and then be submitted. This is particularly because for one problem i'v solved(not easy category) has output in tune with the output given for the example cases. But gave reply "wrong answer".

cin and cout are very slow, you should never use them.

cin and cout are on an average 3 times(personal opinion) slower compared to printf() and scanf(). You should avoid using cin and cout.

How do I find the score/time for my successful submission? The my submission page always shows an error.

If the submission page shows an error, then your solution is not successful.

#include int main(void) { int size,i=0,ans=0; long number; std::cin>>size; std::cin>>number; long p; while(size>0) { std::cin>>p; size--; if(p%number==0) ans++; } std::cout<

http://codepad.org/UFm6O4s1 getting time limit exceeded ....... help , please!

Don't use cin and cout. Read the comments above for more information.

Hi I am new to this.Please help me as to where to post the code and the language preference

For language preference, you need to make the change in your profile. For submitting code, click on the submit button on the top right corner of any problem and you will get a text box where you can submit the source code.

These people don't use Visual Studio 2008 for compiling C++ / C# programs I suppose. It somehow gave compilation error for scanf_s ! I changed it to scanf and then it worked. They need to use latest technology and also give support for Boost and other third party libraries like Google Code Jam etc.

I'm afraid it's you who needs to user proper technology :P scanf_s is NOT part of the ANSI standard; it is a Microsoft-only function which you should not be using.

is the source limit in problems denote memory limit in MB

It is in bytes.

I'm a bit confused -- I submitted a solution that was marked as correct within a few seconds of submitting. That means it worked within the 8 second confine. However, when I look at "My Submissions", the time shows up as 17.66. Why is there such a discrepancy?

Are you sure you were told correct answer within a few seconds of submitting? I doubt you would be able to get your solution done in only a few seconds, it would have taken the 17.66 seconds as stated.

I think you're right, it was probably longer than that. Nonetheless, 17.66 seconds is quite more than 8 seconds, and is even greater than twice 8 (http://blog.codechef.com/2009/04/01/announcing-time-limits-based-on-prog...). That's what confuses me.

That is what the FAQ is for ;)

Perfect, thanks!

 

can you plz explain as to why simple scanf() function wont work here ..

that we have to resort to fread() and make it complicated?

thnx..

and is there any way that i can subscribe to this thread so that i get notified when some one replies  ... so that i dont have to keep checking this thread..

thnx

 

 

can you plz explain as to why simple scanf() function wont work here ..

that we have to resort to fread() and make it complicated?

thnx..

and is there any way that i can subscribe to this thread so that i get notified when some one replies  ... so that i dont have to keep checking this thread..

thnx

 

scanf() and printf() work here. Take a look at http://www.codechef.com/viewsolution/112280

plz chk my solution

http://www.codechef.com/viewsolution/112948

see the point which i dont get is u dont have to do much in this prob take 2 int........

and thats i m doing ders no algo srt f thng in this prob then why my C++

solutionn takes time 5.43s and 2.6 M I am actually shocked to see the diff in best time and my time ......

kindly explain........

 

As the title suggests, this is a problem which tests th efficiency of your input / output routines. The difference between the time limits is mainly because the ones with a low time limit are using highly optimized I/O routines while you are using printf() and scanf()

very strange... allocating an int array the size of the expected inputs speeded up my program from 8 seconds to .14 seconds, almost 60 times faster, WITHOUT EVEN USING the allocated structure. that's using the c# compiler, not c#2.

well i saw the best c++ solution few thngs arent clearand have some queries

1) why SZ 30000 whynot 50k or 90k how did u approximate?

2)in my case what i was doing was reading 1 input at a time and displaying the output the other solution takes the entire input stores in a buffer and calculates how do you differentiate the 2 solutions in terms of runtime and resource usage

3)is sscanf faster than scanf

4)do we have sth in addition to fread to do the similar job

 

thanks!

tarzan keep getting result from nasm program "wrong answer". tarzan don't know why. tarzan want to throw laptop against nearest rock.

You could try read()

tarzan solve problem with tsort, and it also solve this problem. glad he not break computer. life is good.

Things are really easy in PHP for formatting text and casting from 1 data type to another...

I worked this problem in one trial. I had thought it will take me 10-20 trials, because I had bad track record regarding I/O format errors.

fscanf(STDIN,"%s %s",$linemax,$div);
$linemax = intval($linemax);
$div = intval($div);
$lineno = 0;
$total = 0;
while($lineno < $linemax)
{
$num = fgets(STDIN);
if($num % $div == 0)
{
$total++;
}
$lineno++;
}
echo $total."n";

See!! Isnt that easy??

well can any1 plz resolve my queries!!!!!!!!

Reading all input at once and then processing it would be faster. Especially if you are reading in memory in chunks. sscanf and scanf are used in different scenarios, you can't compare the two. You can use read() instead of fread()

#include <iostream>
#include <cstdio>
int main(void) {
unsigned int count=0,i=0;
long unsigned int k,n;
unsigned int temp;
fscanf(stdin,"%uld",&n);
fscanf(stdin,"%uld",&k);
if(k<=10000000){
                while(i<n && std::cin>>temp && temp<=1000000000){
                           if(temp%k==0)count++;
                           i++;
                }
               }
std::cout<<count;               
return 0;
}

CAN ANYONE PLEASE EXPLAIN ME.....WHATS WRONG WITH....THIS CODE......WHY..ITS....SHOWING.....TIME LIMIT EXCEEDED.....

PLZ EXPLAIN ME...........

#include <iostream>
#include <cstdio>
int main() {
unsigned count=0,i=0;
long unsigned k,n;
unsigned temp;
fscanf(stdin,"%ul",&n);
fscanf(stdin,"%ul",&k);
while(i<n && std::cin>>temp ){
            if(temp%k==0)count++;
            i++;
           }
std::cout<<count;               
return 0;
}

Y NO ONE IS REPLYING ME..................

N WHATS WRONG WITH THIS ONE ....STILL TIME LIMIT EXCEEDS...........

PLZ REPLY ME,,,,,,,,,,,,......////////

cin / cout are far too slow to solve this problem.

Man..., y this is so...........?

can i get the proper reason.........?

plz...............

What do you mean? That is the proper reason. cin and cout are very slow at reading/writing. You should use printf or scanf which are much faster, or write your own input routines using things like fread().

#include <iostream>
#include <cstdio>
int main() {
unsigned count=0,i=0;
long unsigned int k,n,temp;
char str[16];
fscanf(stdin,"%ul",&n);
fscanf(stdin,"%ul",&k);
while(i<n && std::cin.ignore() && std::cin.get(str,16)){
            temp = 0;
            for(int j=0;j<std::cin.gcount();j++)temp = temp*10+(str[j]-48);
            if(temp%k==0)count++;
            i++;
           }
std::cout<<count;               
return 0;
}

this code shows the same output for the test case given above n others too which i tried.....but..chef...telling..wrong.ans.....

 

Can any one eXplain..........................

@Stephen Merriman

thanks man....i got..it...bt..help..me...with..the..previous..comment

I keep getting the status message for a successful submission but am reported with the following error :( internal error occurred in the system. Also at the same time while I check the recent activities, I find my code submitted under somebody else's name. Just to verify, I gave some variables some name I choose often, and I found the same code under somebosy else's name.

can some why does this code give a time limit exceeded??

#include<stdio.h>
int main()
{ 
    long n,k,x; 
    int cnt; 
    scanf("%ld",&n); 
    scanf("%ld",&k); 
    while(n>0) 
    {  
         scanf("%ld",&x);  
         if(x%k==0)  
         {   
             cnt++;  
         } 
    } 
    printf("%d",cnt);  
}

Because your while loop will never end?

The fastest C solution (gauravgaba) is ripped various times by other contestants. I understand that this is not a competition problem but it still is plagiarism. Admins please take not and take appropriate action.

@Aniruddha...

 

 

can you tell me which case would be faster

processing the input as i get it or first get all inputs and then do calculations?? reason i m asking again is that i did same as in case-2 in some another problem and surprisinngly it was slower..Or it depends on the situation?? if yes then do elaborate..^_^

$n=<STDIN>;

$k=<STDIN>;

$cnt=0;

for ($i =0 ; $i< $n ; $i ++)

{

if(<STDIN>% $ k ==0)

{$cnt++;} }

print $cnt;

 

am getting wrong answer .....can anyone pls help?

I dont know the problem with my code. I checked other solutions and mine should work but it is timing out.... pls help.

#include <iostream>
using namespace std;
int main()
{
long n,k;
long t,count=0;
cin>>n>>k;
for(long i=0;i<n;i++)
{
cin>>t;
if(t%k==0)
count++;
}
cout<<count;
return 0;
}

Read the rest of the comments.

Am I not using the int_fast32_t types defined in stdint.h correctly?

My code is successful but very slow using regular printf/scanf and long, but the same code with int_fast32_t type gives wrong answer.

http://www.codechef.com/viewsolution/164482

Any ideas?

thanks guys, for telling me the practical application of space time trade off.although i read about it in theory but the fact that cin and cout are so slow as compared to scanf and printf has come as a shock to me.....

the general thinking is that latest is the best but this fact has told me that old can also be gold.

Hi,

 

Shouldn't k strictly greater than 0. i.e. (k>0)&&(k<=10000000)

a = int(raw_input('enter the value of a: '))
b = int(raw_input('enter the value of b: '))
c = []
for i in range(a):
d = int(raw_input('enter the value of d: '))
c.append(d)
for i in range(a):
if c[i] % b == 0:   
e = i + 1
print e

 

hey can anyone please tell me what is wrong in this program.I am getting run time error

hi' I try to write tis in java, and I  try to create a loop to read all the text from the screen (exept the first line). No matter what I do, the loop never finishes. I don't think it go's on all the time, It probobly just block waiting for more input, but I can't find a way to prevent it. Here is some of what I tryed.

 

do{
div = in.nextInt();
if (div % k == 0) count++;
}while (div > 0);

do{
div = in.nextInt();
if (div % k == 0) count++;
s = in.next();
}while (s != null);

while (in.hasNextLine()){
div = in.nextInt();
if (div % k == 0) count++;
}

About my last one - I was mistaking in understanding what should be done. nevermind.

 

I submitted these two solutions witch exceeded 1 sec. Now I can't see how much each one took to run, wich could probobly help me. Can anyone help me find out witch one is better and what else can I improve?

 

import java.util.Scanner;
/**
*
* @author zack
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Scanner in = new Scanner (System.in);
int n = in.nextInt(), k = in.nextInt(), count=0;
while (n > 0){
if (in.nextInt() % k == 0) count++;
n--;
}
System.out.println(count);
}
}

 

======================================================================================

 

import java.util.Scanner;
/**
*
* @author zack
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Scanner in = new Scanner (System.in);
int n = in.nextInt(), k = in.nextInt(), count=0;
for (int i=0; i<n; i++) if (in.nextInt() % k == 0) count++;
System.out.println(count);
}
}

Now I see that the time limit is 8 seconds. Is it true? My code did 1 sec on my laptop with netbeans. How come it does more than 8 seconds on the site?!

I highly doubt it takes 1 second on your laptop in the worst possible case. You are probably just testing your code on something simple. On a large input your code is taking 33 seconds on my computer.

Also, please read the FAQ before making comments.

Can anyone tell me that will i get the input from keyboard or from a text file?

Did you read the comment directly above yours?