Java - Competitive Programming Tricks

Till date, I have been using C++ for contests and I would like to try Java for some of the contests from now on so that it will be a practice for me.

So, are there any Java tricks that can be used in contests like

  1. Fast IO

  2. Max size of an array that can be declared(local and global)

  3. Which stream to use for input

and any other thing which might be useful.

4 Likes

I would suggest you to use fast I/O in java. Since Scanner is too slow to take as input and in BufferedReader you have to type a lot (which is not helpful in short contest). User defined class for InputReader is most popular among competitive programmers. You can see solution of @uwi and here for @sumeet_varma , two of them who are great coders.

For Fast Output I would suggest you to use PrintWriter class

You can declare global array of maximum size around 10^7 (but try to not to use more than 10^6). You may have declared boolean array of size of 10^9 in C++ but in Java you cannot allocate such huge amount of memory(Correct me if I am wrong). However, there is BitSet class in Java which works same as boolean array and has lots of predefined functions.

Java has small stack size as compare to C++ so when you have to make recursive solution then chances are there it may lead to StackOverflow and give RE. So you can use mulithreading to allocate new stack to every threads. Implementation (See main function) (Though I would not suggest you not to follow my codes as they are not very clean to understand).

Happy Programming !

5 Likes

I’m using Java since quite a while for CP so I’ll share some things that I use.

  1. My implementation of FastIO, (I call it BladeReader) can be seen here : https://dpaste.de/EdDc

  2. CHelper plugin with IntelliJ. This one rocks, it automatically fetches testcases in the IDE and saves you a lot of time during the contest by automatically copying the external files you mentioned in the code, just one click and all the code is ready. Here: http://codeforces.com/blog/entry/3273

  3. Amazing and high quality implementations of most using algorithms and data structures : http://code-library.herokuapp.com/

2 Likes

how to code this in java?
Develop a command line based todo application using java programming language:

Features are:
· Add TODO (ex: todo add “learn design patterns”)
· View TODO list (ex: todo list)
· Search TODO list (ex: todo list “learn”)
· Mark TODO as done (ex: todo done 1 – where 1 is the identifier for a todo item displayed from todo list)

Apply any Object Oriented Programming Concepts and Design Patterns (ex MVC, Factory) you know.

@kay_kay Earlier, I used to code in java, and now I have switched to C++. You can refer to the fastIO that I have used earlier at this link, and a sample solution using this fastIO (link).

1 Like

Thanks for suggesting the Java tricks needed for competitive programming contests. Learning to build the assorted Java projects can help you learn the correct use of Java API along with best development practices.

I’ll discuss about Fast I/O in Java as it’s a very important factor.
People tend to stick to C++ instead of Java as it’s I/O is faster than the latter.

Some of the methods for Fast I/O in order of decreasing time or Increasing Efficiency are :-

  • 1.Scanner Class

(easy, less typing, but not recommended very slow, refer this for reasons of slowness):
In most of the cases we get TLE while using scanner class. It uses built-in nextInt(), nextLong(), nextDouble methods to read the desired object after initiating scanner object with input stream.(eg System.in).
Hence NOT RECOMMENDED!

**

- 2.BufferedReader –

(fast, but not recommended as it requires lot of typing):
The Java.io.BufferedReader class reads text from a character-input stream, buffering characters so as to provide for the efficient reading of characters, arrays, and lines. With this method we will have to parse the value every time for desired type. Reading multiple words from single line adds to its complexity because of the use of Stringtokenizer and hence this is NOT RECOMMENDED.

  • 3.Userdefined FastReader Class-

(which uses bufferedReader and StringTokenizer):
This method uses the time advantage of BufferedReader and StringTokenizer and the advantage of user defined methods for less typing and therefore a faster input altogether.
This gets accepted with a time of 1.23 s and this method is very much recommended as it is easy to remember and is fast enough to meet the needs of most of the question in competitive coding.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main
{
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
 
    public static void main(String[] args)
    {
        FastReader s=new FastReader();
        int n = s.nextInt();
        int k = s.nextInt();
        int count = 0;
        while (n-- > 0)
        {
            int x = s.nextInt();
            if (x%k == 0)
               count++;
        }
        System.out.println(count);
    }
}

And Finally

  • 4.Using Reader Class:

There is yet another fast way through the problem, I would say the

  • fastest way but is not recommended
  • since it requires very cumbersome methods in its implementation. It uses inputDataStream to read through the stream of data and uses read() method and nextInt() methods for taking inputs. This is by far the fastest ways of taking input but is difficult to remember and is cumbersome in its approach. Below is the sample program using this method.

A Program Using the Reader Class

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main
{
    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
 
    public static void main(String[] args) throws IOException
    {
        Reader s=new Reader();
        int n = s.nextInt();
        int k = s.nextInt();
        int count=0;
        while (n-- > 0)
        {
            int x = s.nextInt();
            if (x%k == 0)
               count++;
        }
        System.out.println(count);
    }

}

Hope That you like the answer and delve into the magic that coding and Java is!
:smiley:

Cheers.

@lawliet_yagami Your implementation of FastIO is not available. Can you send the correct link?

@srd091 Can you explain me the use of SpaceCharFilter and shouldn’t the class which has main() be named ‘Main’?

@kay_kay isSpaceChar method is used to avoid any whitespaces in the input. It returns true if the input character is a space character and false otherwise. At codechef and codeforces, it isn’t necessary to name your class containing main() method as Main, you can name them anything you want.

1 Like

@srd091 Yea, but why do we need the interface. Isn’t the below function sufficient to check that?

public boolean isSpaceChar(int c) {
return c == ’ ’ || c == ‘\n’ || c == ‘\r’ || c == ‘\t’ || c == -1;
}

@kay_kay I didn’t get your point, can you please explain what do you want to say?

@srd091 to check for whitespaces in input isn’t the isSpaceChar(int c) in my previous comment sufficient. Why is there an interface called SpaceCharFilter?

1 Like

@kay_kay you are right, the isSpaceChar method is sufficient alone. Actually, it’s present in the source from where I copied it, but you can edit the code before using it.

1 Like

@srd091 Okay, Thank you :slight_smile:

1 Like

@srd091 Any specific reason for switching to C++ from Java ? I have just started with cp, though I am Python developer i am confused between choosing Java or C++.

Any new update on Java tricks ?
Did anyone try NIO package classes ? i read they offer faster performance