Competitive Programming in Java

• This repository contains all the important data structures and algorithms that I use in Competitive Programming.

• I have cis_pie as my username on all coding platforms. You can view me on Codechef or Codeforces.

• Feel free to use these codes and let me know if you find any bug.

Links

Data Structures

• Next smaller and bigger element using Stack in array O(n)

• Disjoint Set Data Structure using Arrays

• Centroid Decomposition

• LCA - Lowest Common Ancestor

• Virtual Tree

• BIT/ Fenwick Tree

• Segment Tree : Basic

• Segment Tree : Range Updates (add)

• Segment Tree : Range Updates (assign)

• Segment Tree : Kth Order statistic on subarray (No updates allowed)

Algorithms

• Binary Search

• BFS

• DFS

• Kruskal's MST Algorithm using Disjoint Set Union

• Dijkstra using Priority Queue

• Floyd Warshalls (with all shortest paths )

• LIS : Longest Increasing Subsequence O(nlogn)

• PIE : Principle of Inclusion Exclusion

Strings

• String hashing - Rolling Polynomial Hash

Maths related

• Sieve for finding prime numbers n<=10^7

• Handling Fractions

• Rounding Doubles to x-places

• Geometry -Segments Intersections and Polygon Area from Co-ordinates

• Geometry -Closest pair of Points

• nCr with mod

• Next Permutation for n! permutations (C++ equivalent)

• Selection Of r Things from n things

• Power function -Modular

• Matrix Exponentiation

Miscellaneous

• Stress Testing

• Java template for Competitive Programming

Fast IO for JAVA : Template.

• Taken this template from legendary coder uwi

• Java is a little bit slower than C++/C and the main factor behind this is slow console input/output.

• Java's Scanner, as well as BufferedReader class, is too slow. So the best option is creating your own input-output classes.

• I had never faced Time Limit Exceed Error (i.e Code takes too much time because of an inefficient/wrong algorithm ) after I started using this template.

• To use this template you have to write all your code in solve() method.

• From main() method we are calling solve() method which is supposed to solve the asked problem.

Documentation of methods from this template :

• INPUT METHODS

  • int x=ni() -to input single number Short form of nextInt()

  • long x=nl() -to input long number nextLong()

  • double x=nd() - to input double values nextDouble()

  • String x=ns() - to input string nextString()

  • char x=nc() - to input character nextChar()

  • int[] arr=na(int n) -to input array of size n i.e parameter is integer with value n. It will allocate a new array and return its reference. nextArray()

  • char [][] matrix =nm(int n,int m) this is method is used tor inputing character matrix nextMatrix()

  • Refer this for inputs which are EOF terminated.

• OUTPUT METHODS

  • pn(Object o) - method is used to print anthing on console the parameter is Object is you can pass anthing. It is similar as System.out.println().

  • p(Object o)- Similar as System.out.print()

• UTILITY FUNCTIONS

  • int x=max( int[] arr) -it will find max element from array.

  • int y=min(int [] arr) it will find min element from array.

  • int g=gcd(x,y) for finding gcd.

  • Implemented pair class because there is no inbuilt pair class. You can use the pair in Hashed Collections as well as Tree Collections because hashCode() and compareTo() methods are implemented in this pair class.