Download Our Beta Android App And Help Us Build Awesome Stuff!  Download Now.

Competitive Programming in Java - Beginner Part 1

Created by inventionsbyhamid

inventionsbyhamid

inventionsbyhamid,

Most of the people use C or C++ for competitive programming because that's what they teach in Indian colleges. This tutorial is for those who want to use Java for solving problems. Java is a very powerful language and if you have a nice grasp of the language features you already have an edge over the c/c++ users.

Fast IO

There are many articles about fast IO using Java so i'll skip this and add references to those amazing articles already out there. For the sake of writing , always use BufferedReader for input instead of Scanner. Also use PrintWriter for output.
Fast I/O in Java in Competitive Programming - Geeksforgeeks

Array sorting

Most languages have built in array sorting methods and java has them too in the Arrays class of the java.util package.

To sort an array of primitives in ascending order

int a[] = { 4, 10 , 54, 23, 97, 0, -10 };
System.out.println("Original array = " + Arrays.toString(a));
Arrays.sort(a);
// Java 8 also provides parallelSort() method that uses multithreading and can speed things up.
//Arrays.toString() is useful to print arrays quickly while debugging
System.out.println("After sorting array(ascending) = " + Arrays.toString(a));

Using Comparator interface to define our compare function
For example we have a Point type array a and we need to sort the points first by x then by y coordinates.

Arrays.sort(a,new Comparator<Point>() {
            //overriding compare function in Comparator interface
            @Override
            public int compare(Point a, Point b ){
                if(a.x == b.x)
                    return a.y-b.y;
                return a.x - b.x;
            }
        });

Complete program to show sorting using Comparator
Using Comparable interface to define our compare function
Comparable is mostly used to define the natural ordering of a class while Comparator is used to define some new ordering.

class Point implements Comparable<Point> {
    int x,y;

    Point(int x,int y){
        this.x = x;
        this.y = y;
    }
    public int compareTo(Point b) {
            if (this.x == b.x)
                return this.y - b.y;
            return this.x - b.y;
    }
}

Complete program to show sorting using Comparable

String in java

Java's String implementation is slightly different than other languages. Many people don't know properly how java String works internally and as such make performance critical mistakes. String in java is immutable i.e. it's value cannot be changed after it is created. If you believe this is wrong and you can change the value of String then I tell you the original String is not changed instead a new String is created and returned with the new value. String is internally implemented as a char array and as such many operations become constant time like the length(), length() function in String class is simply

public int length() {
        //value is the char array that stores the characters of the string
        return value.length;
    }

For String the concatenation operation is O(N). For this reason when you need to create a string by concatenating many times using String is not the best option. In such cases StringBuilder class should be used. StringBuilder provides constant time concatenation.

Base Conversion

Converting from any base to decimal Integer(or Long) is very easy in Java. For example if you have to take number input as binary and convert to decimal:

int mynumber = Integer.parseInt(br.readLine(), 2); //2 is the radix(base) in which the input is given, radix value can be between 2 and 36.

To convert Decimal to any other base

Integer.toString(myIntegerInDecimal, int base); // base can be between 2 and 36
Integer.toString(8, 2); //Converting 8 in decimal to binary
BigInteger

Many times in programming contests the input range is too long and doesn't fit in double or long. It becomes difficult to store in String and do calculations. Java has BigInteger implementation to store very large numbers! You can store numbers with any number of digits unless you run out of memory. BigInteger is in the java.math package so you need to import before using unless you use a nice IDE that does that for you. The methods in BigInteger class allow for fast addition, multiplication, division, pow for large numbers. Here how to use them:

BigInteger a = new BigInteger(br.readLine());
BigInteger b = new BigInteger(br.readLine());
System.out.println("Sum = " + a.add(b));
System.out.println("Difference = " + a.subtract(b));
System.out.println("Multiplication = " + a.multiply(b));
System.out.println("Division = " + a.divide(b));
System.out.println("Modulus = " + a.mod(b));

System.out.println("Mod Pow = " + a.modPow(b, new BigInteger("10000009"))); // returns a^b mod 10000009

System.out.println("Modulus Inverse = " + a.modInverse(b)); //  a^-1 mod b, this throws ArithmeticException - b ≤ 0, or 'a' BigInteger has no multiplicative inverse mod b (that is, this 'a' is not relatively prime to 'b'

System.out.println("GCD = " + a.gcd(b)); // finds gcd, how cool is this?

System.out.println( a.isProbablePrime(15)? true: false ); // checks if the number is probably prime or not , uses th Miller-Rabin primality test and with certainty of about 15 it is good enough to produce correct results.

System.out.println("Next prime after" + a + " is " + a.nextProbablePrime());// Returns the first integer greater than a that is probably prime.

I have not covered BigDecimal, Calendar, HashTable, HashSets and few more other things. They also prove to be useful in programming contests. I'll cover those in the next post.
Sources: Oracle Java™ Platform, Standard Edition 8 API Specification
Links to individual classes/interface:

Last updated

Login to post to this thread.
You need to be logged in to comment on this thread. Click here to login.