Java |
An approach to solving a problem may seem to be obvious while doing it using pen and paper ,implementing it using a computer is quite a different thing. That's where the power of the programming language, that one uses, comes into picture.
IO in Java
In java there are many many ways to do input and output. For writing to the console, we can use the simple System.out object, however there are much faster methods of reading and writing data.
Input
Method 1 ( bad )
This is easily the most convenient way of reading in input, however it is very slow and not recommended unless the input is very small. ( less than 50KB of data is to be read )
Method 2 ( good )
This is definitely way faster than Scanner but the only bad thing is that you have to worry about the input format because you have to read line by line.
Method 3 ( very good )
This is amongst the fastest ways to read input in Java, you have to use the primitive read() method and write your own functions to parse integers and real numbers. It is good for reading other data-types like strings but you have to use character arrays and then finally convert to strings, this is more efficient.
However writing these functions is pretty cubersome.
Output
Using PrintWriter and PrintStream to write to console is way faster than just using the System.out writer object. However don't forget to close the streams before you terminate your program.
You can test your Java input routines here
The key to implementing many problems correctly and in a short time interval is using the correct data structure. The Java Collections Framework is a collection of data structures and algorithms for Java. To use these data structures one needs to import the util package using the following statement before writing the class definition.
import java.util.*;
Some of the basic collections discussed here are
1.List
2.Set
3.Queue
4.Stack
5.Map
Note : The elements that can be added in the JCF data structures must be objects of a class. To add elements of a primitive data type (eg. int, double) we must use their corresponding wrapper class (eg.Integer,Double). This will become clear in the examples further in this tutorial.
ArrayList
An ArrayList is simply a list of items(need not be distinct) which is generally used in problems where the number of items to be added is not known to us beforehand.
An ArrayList can be allocated in the following ways:
ArrayList list1 = new ArrayList(); // Here the items added are of type Object
ArrayList<Integer> list2 = new ArrayList<Integer>();
//Here the items that can be added must be of type Integer
ArrayList<ClassName> list3 = new ArrayList<ClassName>();
//objects of class ClassName can be added to this list
"list1" is essentially a list of items whose type is Object. As we know that all classes in java inherit the Object class, thus we could add an integer , a string or any object to "list1". "list2" is a list of items which are integers only. The class name specified in the angular brackets informs the compiler that the items that can be added to "list2" are of type Integer only. (Note: newer versions of jdk supports autoboxing and auto unboxing. You can visit the Sun Tutorials if you wish to know about these concepts.)Similarly "list3" can contain objects of type ClassName only.
These are some of the most commonly used functions for the ArrayList :
1. Adding an element
list2.add(new Integer(3)); // adds 3 to list2
(Note:with newer versions of jdk , list.add(3); will also be a valid statement)
2. Accessing an element at the ith index in a list (0-based index)
int val = list.get(0); // returns the integer at the 0th index , auto-unboxing assumed
3. Current size of the ArrayList
int size(); //Returns the number of elements in the ArrayList
4. To remove an element at a certain index
Object remove(int index); //Removes the element located at the specified index
5. To check the presence of a certain element
boolean contains(Object element); //Returns true if the ArrayList contains element, otherwise false
6. Index of first occurance of an element
int indexOf(Object element) //Searches for the first instance of element and returns its position, or -1 if it is not found
7. Clearing the ArrayList
void clear(); //Removes all elements from the ArrayList
Sorting the elements of ArrayList
The following method is used for sorting -
Collections.sort(listName);
For elements whose types have a predefined natural ordering (eg int,String) the above statement is sufficient. For ordering objects of any class, the class can implement the Comparable Interface and implement the required abstract methods to define the ordering.
// To add: links to problems that can be solved using the ArrayList
Set (HashSet/TreeSet)
A set is a data structure that contains distinct items. In java , the two major classes that implement sets are HashSet and TreeSet.
-> We can define an equality of objects of classes by overriding the equals() and the hashCode() method of the Object class if required.
-> An element already existing in the set is not added again.
-> When iterating the elements in the HashSet, one may or may not get the same order in which one added those elements in the set.
-> The HashSet stores the elements in any arbitrary order , while the TreeSet is used to store the elements in the natural order/the order specified using the Comparable or Comparator . The TreeSet can also be used like a PriorityQueue for removing the element with least or greatest priority.
(Note: Similar to what we have seen in the ArrayList one can maintain a HashSet/TreeSet of specific types (given in angular brackets) or none(in which case the default type is taken to be Object) )
(Note : the term set has been used for the HashSet/ TreeSet object)
Following are some commonly used functions :
1. void add(Object ob); // adds object ob to the set
2. boolean isEmpty(); // returns true if the set is empty, false otherwise
3. int size(); // return the current size of the set
4. boolean remove(Object ob); // Removes ob from the set. Returns true if remove operation is successful , false otherwise.
5. boolean contains(Object ob); //returns true if set contains ob, false otherwise
6. void clear(); //removes all elements from the set
7. Object[] toArray(new Object[0]) ; //returns an array containing all elements in the set
These functions are used for both HashSet and TreeSet.
Specifically for the TreeSet the following functions are often useful :
1.Object first();//returns the first(lowest as per the ordering defined) currently in the set
2.Object last(); //returns the last(highest as per the ordering defined) currently in the set
To iterate through the elements in the set
With jdk 1.5 and above the "for each" style is generally used. Say a HashSet set1 is allocated which contains Strings. To print the strings in the set1 , we can do the following
for(String s: set1){
System.out.println(s);
}
This is quite intutive and generally preferred style to iterate through the elements in a set. The second way to do this is to use what is called an iterator.
Sets will be found very useful for solving many problems.
//To add: links to some problems that can be solved using sets.
Queue
Queue is a data structure that follows the FIFO principle or simply "the first element in, is the first element out" . One of the basic algorithm in graph theory namely the Breadth First Search (BFS) can be implemented elegantly using a queue.
Generally the specific type allocation of queue is required which can be done as follows -
Queue<ClassName> Q = new LinkedList<ClassName>();
(Note : Queue is an interface)
Most commonly used methods on Q are as follows -
1. Q.add(ClassName ob); // adds ob to the queue , returns true if successful
2. Q.element(); //retrieves but does not remove the first element in the queue , throws an exception if queue is empty
3. Q.remove(); //returns and removes the head of the queue, throws an exception if queue is empty
4. Q.isEmpty();//returns true if the queue is empty , false otherwise
5. Q.size(); //returns the current size of the queue as an int
//To Add: Links to basic BFS problems
Stack
Stacks are data structures that follow the LIFO principle or "the last element in , is the first element out" . A stack can be visualised as a pile of books. You always add a book th the top of the pile and to remove a book (with least effort ;)) you simple remove the topmost book. Thus the last book to be added was the first one to be removed.
Stack is an important data structure. Stacks are used when a subroutine is called within a program. The power of the stack becomes evident for recursive subroutines. One of the basic algorithm in graph theory, namely ,depth first search or DFS uses a stack. (DFS can be implemented by writing a simple recursive method too , but sometimes this gives a TLE/memory error as the implicit stack stores a lot many other things , that time you should use an explicit stack).
A stack of integers can be allocated as follows -
Stack<Integer> stk = new Stack<Integer>();
Most commonly used methods on stk are as follows -
1. stk.push(5); //pushes 5 (can be any integer in this case (object in general)) on the top of the stack, returns the argument passed
2. stk.pop(); //removes the element at the top and return it
3. stk.peek(); //returns but does not remove the top most element
4. stk.empty(); //returns true iff stack doesn't contain any element, false otherwise
5. stk.size(); //number of elements in the stack
//To Add: DFS problems , other problems that can be solved using stack
Map(HashMap/TreeMap)
In many problems, one may want to associate an element with the other. In other words, one may like to map keys to values. For example, we may need to map students to their grades in an examination. The way this is implemented is by using the HashMap and TreeMap classes. Note that the keys that are maitained are always distinct. If you add two values with the same key, the older value is replaced with new value. Thus keys are distinct, values can repeat.
Moreover,
-> HashMap contains entries , keys of which are placed in arbitrary order
-> TreeMap contains entries, keys of which are sorted according to their natural ordering or the order defined using the Comparator.
An example to demonstrate various methods -
Allocating a hash map -
HashMap<Integer,String> mapIdName = new HashMap<Integer,String>();
/* the first parameter in the angular bractets represent the type of keys to be added , the second represents the type of values that the keys can be mapped to. */
Adding few elements -
mapIdName.put(1,"Alice"); //maps integer 1 to Alice
mapIdName.put(2,"Aladdin");
map.put(1,"Jasmine"); //replaces the value at key 1 with Jasmine
Accessing the value at a particular key -
String name = mapIdName.get(2); //name will contain Aladdin
Traversing the map values -
for(int id : mapIdName.keySet()){
System.out.println(map.get(id));
}
Checking if the map contains a particular key -
boolean see = mapIdName.containsKey(1); //returns true if the map contains a mapping with the key passed as argument
Checking if the map contains a value -
boolean there = mapIdName.containsValue("Alice"); //returns true if the map contains one or more keys mapped to the value passed
To remove a key and its corresponding value -
mapIdName.remove(1); //removes the entry having 1 as the key
mapIdName.clear(); //clears the map
mapIdName.size(); //returns the number of keys in the map
mapIdName.isEmpty(); //returns true if the map contains no entries
Moreover, if we use a TreeMap ,we have many additional methods that we can use for example , someMap.firstKey() returns the lowest key .
//To Add - problems using a map , certain memoization problems that use maps rather than arrays to store the computed values
The true understanding of these data structures come when one knows the nitty-gritty of implementing them.Nevertheless, such Framework and libraries come in very handy during programming contests.
BigInteger
Let us now have a look at a very interesting and useful class called the BigInteger. Many times for solving a problem, we need to store huge numbers , very huge , for example, 1000! (1000 factorial). How do you represent such a big number. You cant use your primitive data types for sure.This is where our language comes to rescue us ;).
Allocating a BigInteger :
BigInteger big = new BigInteger("123");
You can pass any valid number as a String as an argument in the above constructor. There are many overloaded constructors, which one can look up in the Java API, but this is the one which is needed to solve many problems.
For the sake of concreteness, I will demonstrate the use of commonly used methods using a few BigIntegers.
BigInteger big1 = new BigInteger("1000");
BigInteger big2 = new BigInteger("1500");
BigInteger MOD = new BigInteger("200000");
BigInteger result = BigInteger.ZERO; //(ZERO is a static final variable/constant already defined)
//alternative way - BigInteger result = new BigInteger("0");
result = big1.add(big2); //result = big1+big2
result = big1.subtract(big2); //result = big1-big2
result = big1.multiply(big2); //result = big1 * big2
result = big1.divide(big2); // result = big1/big2
result = big1.remainder(big2); // result = big1 % big2
result = big1.modPow(big2,MOD); //result = (big1^big2)%MOD
result = big1.gcd(big2); //result = gcd(big1,big2)
(big1.compareTo(big2))
returns -1: big1 is less than big2
returns 0: big1 is equal to big2
returns 1: big1 is greater than big2
String s = result.toString(int radix); //returns the value in the result in the specified radix
(Note : simply by writing big1.add(big2) doesnt update the value in big1 , you need to store the result back in big1 in case you need to update it)
These were some of the basic methods that are used. To explore more operations, it is a nice idea to look up the Java API or use an appropriate IDE (eg. Netbeans 6.0).
//To add: links to codechef , SPOJ problems that can be solved using BigInteger.
SPOJ problems requiring big integers
| MCONVERT | |
| MUL2COM | |
| REC | |
| SETNJA | |
| TREE | |
| WORMS |
