How to improve time of proceeding for my programm?

Question

My program works correctly, but I have a limit of time 3020ms. how to improve my code?

https://www.e-olymp.com/uk/problems/3607

n- is a number of people, then there are n numbers of input which describe their height, the program should answer the question how much people have a height between a and b (which are also given in input)

 import java.io.PrintWriter;
 import java.util.Scanner;

 public class OlimpGames {
    public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      PrintWriter out = new PrintWriter(System.out, true);
       {
        while (in.hasNextInt()) {
            int n = in.nextInt();

            int heigh[] = new int[100];
            for (int i = 0; i < n; i++) {
                heigh[in.nextInt() - 150]++;
            }
            int a = in.nextInt();
            int b = in.nextInt();

            int an = 0;
            for (int i = a - 150; i <= b - 150; i++) {
                an = an + heigh[i];
            }
            System.out.println(an);
        }

    }
  }
}

Please don't post links to non-English content, this is an English-speaking site. Also what do you mean you have a "limit of time"? Please word your question more carefully. Also please read through: https://stackoverflow.com/help/asking — Maciej Jureczko, Sep 27 '17 at 10:25
You're on the wrong site for code improvements; try https://codereview.stackexchange.com/ — achAmháin, Sep 27 '17 at 10:28
It's a programming olympics problem. As far as I can read, the input set is a list of repeating 3 lines, first line specifies X persons, for which their heights follow on the next line, and you need to count the number of people with height beween Y and Z which are specified on the third line. OP - do you have a copy of the dataset used for judging the answer? — vikingsteve, Sep 28 '17 at 11:32

score 0 · Answer 1 · answered Sep 28 '17 at 11:50

Problem: the input set is a list of repeating 3 lines, first line specifies X persons (up to 20,000), for which their heights in centimetres follow on the next line (heights between 150 and 250cm), and you need to count the number of people with height beween Y and Z which are specified on the third line.

Firstly, these programming competitions can be notoriously difficult due to the crafty way they construct the datasets (which you dont always have access to).

I suggest you improve your program in 2 ways.

First, use a better parser than Scanner - it's slow compared to other parsers.

Why is Scanner slower than BufferedReader?

Second, you can avoid the use of array storage completely. You need to process the third line of your input before the second one, and read "min" and "max".

Then, you can scan through the second line of your input (which can have up to 20,000 items) and count the items between min and max (without array storage - get rid of heigh[] completely). This will free up a call to new int[100]; when processing every 3 lines of the input.

How to improve time of proceeding for my programm?

1 Answers1