• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Too much execution time

 
Yohan Weerasinghe
Ranch Hand
Posts: 507
Java Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

Following is a complete question I copied from a site

The purpose of this problem is to verify whether the method you are using to read input data is sufficiently fast to handle problems branded with the enormous Input/Output warning. You are expected to be able to process at least 2.5MB of input data per second at runtime.
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 109, 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


OK. For the question these are the restrictions

Time limit: 8s
Source limit: 50000


And the following is my code



Whenever I run this code in that site, it says "Time Limit Exceeded". Is there is a way to reduce the performance time and get rid of that problem? Please help..
 
John Jai
Rancher
Posts: 1776
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your code seems to contradict your statement of "Time Limit Exceeded" - where it is present at first place? Have you posted the wrong code.

One thing I find is that a single scanner can be used throughout.



Moderator - kindly move this to Beginning Java forum if its more appropriate
 
Joanne Neal
Rancher
Posts: 3742
16
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What is the purpose of lines 46 - 49 (or 37 - 40 in John's code) ? Getting rid of them will probably only save microseconds on each loop, but every little helps.

Also reducing the scope of the division variable may allow the compiler to optimise that bit of the code.
 
Winston Gutkowski
Bartender
Pie
Posts: 10422
63
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yohan Weerasinghe wrote:Whenever I run this code in that site, it says "Time Limit Exceeded". Is there is a way to reduce the performance time and get rid of that problem? Please help..

Well personally, I like your choice of a BufferedReader and readLine() for reading the lines; I suspect it's quite a bit quicker than Scanner.
And you certainly don't need to scan the String: I'd use String.split() for the header and a simple Integer.parseInt() for your 'ti' lines.

Winston
 
Yohan Weerasinghe
Ranch Hand
Posts: 507
Java Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi guys, Thanks a lot for all of your replies. I didn't get any email notification for this thread, that is why I got late to reply. I will check your suggestions, meanwhile, I am talking about this problem

http://www.codechef.com/problems/INTEST
 
Yohan Weerasinghe
Ranch Hand
Posts: 507
Java Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I tried John's code. But still the same. Now going to try Winstan's suggestion.
 
Yohan Weerasinghe
Ranch Hand
Posts: 507
Java Netbeans IDE Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Joanne Neal wrote:

Also reducing the scope of the division variable may allow the compiler to optimise that bit of the code.


errr..I didn't understand. You mean Class Cope Variables or something? Or reducing the Value of it? If it is value, I am afraid I can't because that what they have given
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic