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
Fast IO
Max size of an array that can be declared(local and global)
Which stream to use for input
and any other thing which might be useful.
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 !
Iām using Java since quite a while for CP so Iāll share some things that I use.
My implementation of FastIO, (I call it BladeReader) can be seen here : https://dpaste.de/EdDc
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
Amazing and high quality implementations of most using algorithms and data structures : http://code-library.herokuapp.com/
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).
@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.
@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;
}
@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?
@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.
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 :-
(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.
(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
There is yet another fast way through the problem, I would say the
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!
Cheers.