Java Competitive Programming Handbook

Comprehensive Illustrated Reference (Naive vs Optimized • Clickable Links • Contest-Ready Templates)

Table of Contents
Placeholder for table of contents 0
Contest Ready Template (Fast I/O + Utilities)
Use this as your starting file in Codeforces/AtCoder.
import [Link].*;
import [Link].*;

public class Main {

static class FastScanner {
BufferedReader br; StringTokenizer st;
FastScanner() { br = new BufferedReader(new InputStreamReader([Link])); }
String next() throws IOException {
while (st == null || ![Link]()) st = new StringTokenizer([Link]());
return [Link]();
}
int nextInt() throws IOException { return [Link](next()); }
long nextLong() throws IOException { return [Link](next()); }
double nextDouble() throws IOException { return [Link](next()); }
String nextLine() throws IOException { return [Link](); }
}
static final long MOD = 1_000_000_007L;

static long modPow(long a, long e, long m) {

long r = 1 % m; a %= m;
while (e > 0) {
if ((e & 1) == 1) r = (r * a) % m;
a = (a * a) % m; e >>= 1;
}
return r;
}
static long gcd(long a, long b) { while (b != 0) { long t = a % b; a = b; b = t; } return a; }

public static void main(String[] args) throws Exception {

FastScanner fs = new FastScanner();
PrintWriter out = new PrintWriter([Link]);
int t = 1; // t = [Link]();
while (t-- > 0) {
// solve here
}
[Link]();
}
}
Math & Number Theory
Fast Exponentiation (pow) – Naive vs Optimized

Naive:
// Naive O(exp) – not feasible for large exponents
public class PowNaive {
static long pow(long a, long e) {
long r = 1;
for (long i = 0; i < e; i++) r *= a;
return r;
}
public static void main(String[] args) { [Link](pow(2, 10)); }
}

Optimized:
// Optimized Binary Exponentiation O(log exp) – contest-ready
public class PowFast {
static long modPow(long a, long e, long m) {
long r = 1 % m; a %= m;
while (e > 0) {
if ((e & 1) == 1) r = (r * a) % m;
a = (a * a) % m; e >>= 1;
}
return r;
}
public static void main(String[] args) { [Link](modPow(2, 50, 1_000_000_007)); }
}

■ Note: Use binary exponentiation for large exponents; complexity improves from O(e) → O(log e).

nCr modulo prime – Naive vs Optimized

Naive:
// Naive nCr using factorial (no mod) – overflow & slow for large n
public class NCRNaive {
static long fact(int n) { long r = 1; for (int i=2;i<=n;i++) r *= i; return r; }
static long ncr(int n, int r) { return fact(n)/(fact(r)*fact(n-r)); }
public static void main(String[] args) { [Link](ncr(10,3)); }
}

Optimized:
// Optimized nCr mod p with precomputed factorials & inverse factorials
public class NCROpt {
static final int MAX = 100000;
static final long MOD = 1_000_000_007L;
static long[] fact = new long[MAX+1], inv = new long[MAX+1];
static long modPow(long a, long e) {
long r=1; a%=MOD;
while (e>0){ if((e&1)==1) r=(r*a)%MOD; a=(a*a)%MOD; e>>=1; }
return r;
}
static void init() {
fact[0]=1;
for (int i=1;i<=MAX;i++) fact[i]=(fact[i-1]*i)%MOD;
inv[MAX]=modPow(fact[MAX], MOD-2);
for(int i=MAX;i>0;i--) inv[i-1]=(inv[i]*i)%MOD;
}
static long nCr(int n, int r) {
if (r<0||r>n) return 0;
return (((fact[n]*inv[r])%MOD)*inv[n-r])%MOD;
 }
public static void main(String[] args){ init(); [Link](nCr(100000, 3)); }
}

■ Note: Precompute factorials up to needed N; complexity per query becomes O(1) after O(N) prep.

Primes: Sieve of Eratosthenes + Smallest Prime Factor (SPF)

public class SieveSPF {
static int N = 1000000;
static boolean[] isPrime = new boolean[N+1];
static int[] spf = new int[N+1]; // smallest prime factor
static void sieve() {
[Link](isPrime, true);
isPrime[0]=isPrime[1]=false;
for(int i=2;i<=N;i++) spf[i]=i;
for (int i=2;i*i<=N;i++) if (isPrime[i]) {
for (int j=i*i;j<=N;j+=i) {
isPrime[j]=false;
if (spf[j]==j) spf[j]=i;
}
}
}
static List<Integer> factorize(int x){
List<Integer> f=new ArrayList<>();
while(x>1){ [Link](spf[x]); x/=spf[x]; }
return f;
}
public static void main(String[] args){ sieve(); [Link](isPrime[9973]); }
}

Practice: CSES – Counting Divisors, CSES – Sum of Divisors

Data Structures
Disjoint Set Union (Union-Find) – Naive vs Optimized

Diagram:

Naive:
// Naive DSU without optimizations
class DSUNaive {
int[] parent;
DSUNaive(int n) { parent = new int[n]; for (int i=0;i<n;i++) parent[i]=i; }
int find(int x) { while (x!=parent[x]) x = parent[x]; return x; }
void union(int a,int b){ a=find(a); b=find(b); if(a!=b) parent[b]=a; }
}

Optimized:
// Optimized DSU with path compression + union by size
class DSU {
int[] p, sz;
DSU(int n){ p=new int[n]; sz=new int[n]; for(int i=0;i<n;i++){ p[i]=i; sz[i]=1; } }
int find(int x){ return p[x]==x?x:(p[x]=find(p[x])); }
void union(int a,int b){
a=find(a); b=find(b);
if(a==b) return;
if(sz[a]<sz[b]){ int t=a;a=b;b=t; }
p[b]=a; sz[a]+=sz[b];
}
}

■ Note: Amortized inverse Ackermann (≈ constant). Always enable both optimizations.

Segment Tree (Range Sum) – Build/Query/Update

Diagram:
 public class SegTree {
int n; long[] st;
SegTree(int[] a){
n = 1; while(n < [Link]) n <<= 1;
st = new long[2*n];
for (int i=0;i<[Link];i++) st[n+i] = a[i];
for (int i=n-1;i>0;i--) st[i] = st[2*i] + st[2*i+1];
}
long query(int l,int r){ // inclusive l,r
l += n; r += n; long res = 0;
while(l<=r){
if((l&1)==1) res += st[l++];
if((r&1)==0) res += st[r--];
l>>=1; r>>=1;
}
return res;
}
void update(int idx,int val){
int i = idx + n; st[i] = val; i >>= 1;
while(i>0){ st[i] = st[2*i] + st[2*i+1]; i >>= 1; }
}
}

Practice: CSES – Range Sum Queries II, CF 339D – Xenia and Bit Operations

Fenwick Tree (BIT) – Simpler Range Sums

public class Fenwick {
int n; long[] bit;
Fenwick(int n){ this.n=n; bit=new long[n+1]; }
void add(int idx,long delta){
for(int i=idx+1;i<=n;i += i&-i) bit[i]+=delta;
}
long sumPrefix(int idx){
long s=0;
for(int i=idx+1;i>0;i -= i&-i) s+=bit[i];
return s;
}
long rangeSum(int l,int r){ return sumPrefix(r)-sumPrefix(l-1); }
}

■ Note: BIT uses O(n) space, O(log n) updates/queries; easier to code than Segment Tree for sums.
Graph Algorithms
BFS / DFS Templates (Iterative)
import [Link].*;
public class GraphTemplates {
static List<Integer>[] g;
static void bfs(int s){
int n=[Link]; boolean[] vis=new boolean[n];
Queue<Integer> q=new ArrayDeque<>(); [Link](s); vis[s]=true;
while(![Link]()){
int u=[Link]();
for(int v:g[u]) if(!vis[v]){ vis[v]=true; [Link](v); }
}
}
static void dfs(int s){
int n=[Link]; boolean[] vis=new boolean[n];
Deque<Integer> st=new ArrayDeque<>(); [Link](s);
while(![Link]()){
int u=[Link]();
if(vis[u]) continue; vis[u]=true;
for(int v:g[u]) if(!vis[v]) [Link](v);
}
}
}

Dijkstra – Array (O(V^2)) vs PriorityQueue (O((V+E) log V))

Naive:
// Naive O(V^2) – use only for dense graphs or small V
static int[] dijkstraArray(List<int[]>[] g, int s){
int n=[Link]; int INF=1<<30; int[] dist=new int[n]; boolean[] used=new boolean[n];
[Link](dist, INF); dist[s]=0;
for(int it=0; it<n; it++){
int u=-1;
for(int i=0;i<n;i++) if(!used[i] && (u==-1 || dist[i]<dist[u])) u=i;
if (dist[u]==INF) break;
used[u]=true;
for(int[] e:g[u]){
int v=e[0], w=e[1];
if(dist[v] > dist[u]+w) dist[v]=dist[u]+w;
}
}
return dist;
}

Optimized:
// Optimized with PriorityQueue – suitable for large sparse graphs
static int[] dijkstraPQ(List<int[]>[] g, int s){
int n=[Link]; int INF=1<<30; int[] dist=new int[n];
[Link](dist, INF); dist[s]=0;
PriorityQueue<int[]> pq=new PriorityQueue<>([Link](a->a[1]));
[Link](new int[]{s,0});
boolean[] vis=new boolean[n];
while(![Link]()){
int[] cur=[Link](); int u=cur[0]; if(vis[u]) continue; vis[u]=true;
for(int[] e:g[u]){
int v=e[0], w=e[1];
if(dist[v] > dist[u]+w){
dist[v]=dist[u]+w; [Link](new int[]{v, dist[v]});
}
}
}
 return dist;
}

Practice: CSES – Shortest Routes I

Minimum Spanning Tree – Kruskal with DSU

static long kruskal(int n, int[][] edges){
[Link](edges, [Link](e->e[2]));
DSU d=new DSU(n); long cost=0; int cnt=0;
for(int[] e:edges){
int u=e[0], v=e[1], w=e[2];
if([Link](u)!=[Link](v)){ [Link](u,v); cost+=w; cnt++; if(cnt==n-1) break; }
}
return cost;
}

Practice: CSES – Road Reparation

Dynamic Programming
0/1 Knapsack – 2D vs 1D Optimization

Naive:
// 2D DP O(nW) with table
static int knapsack2D(int[] wt,int[] val,int W){
int n=[Link]; int[][] dp=new int[n+1][W+1];
for(int i=1;i<=n;i++){
for(int w=0; w<=W; w++){
dp[i][w]=dp[i-1][w];
if(w>=wt[i-1]) dp[i][w]=[Link](dp[i][w], dp[i-1][w-wt[i-1]]+val[i-1]);
}
}
return dp[n][W];
}

Optimized:
// 1D DP O(nW) with reduced memory
static int knapsack1D(int[] wt,int[] val,int W){
int n=[Link]; int[] dp=new int[W+1];
for(int i=0;i<n;i++){
for(int w=W; w>=wt[i]; w--){
dp[w]=[Link](dp[w], dp[w-wt[i]]+val[i]);
}
}
return dp[W];
}

■ Note: Use 1D when only previous row is needed; iterate weights descending.

Longest Increasing Subsequence – O(n^2) vs O(n log n)

Naive:
static int lisN2(int[] a){
int n=[Link]; int[] dp=new int[n]; [Link](dp,1);
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++) if(a[i]>a[j]) dp[i]=[Link](dp[i], dp[j]+1);
ans=[Link](ans, dp[i]);
}
return ans;
}

Optimized:
static int lisNlogN(int[] a){
ArrayList<Integer> d=new ArrayList<>();
for(int x: a){
int i=[Link](d, x);
if(i<0) i = -(i+1);
if(i==[Link]()) [Link](x); else [Link](i, x);
}
return [Link]();
}

Practice: CSES – Increasing Subsequence

String Algorithms
KMP – Prefix Function

Diagram:

public class KMP {

static int[] prefix(String s){
int n=[Link](); int[] pi=new int[n];
for(int i=1;i<n;i++){
int j=pi[i-1];
while(j>0 && [Link](i)!=[Link](j)) j=pi[j-1];
if([Link](i)==[Link](j)) j++;
pi[i]=j;
}
return pi;
}
}

Practice: CSES – String Matching

Rolling Hash (Polynomial Hash)

public class RollingHash {
static final long MOD = 1_000_000_007L;
static final long BASE = 911382323L; // choose random odd < MOD
static long[] p, h;
static void build(String s){
int n=[Link](); p=new long[n+1]; h=new long[n+1];
p[0]=1;
for(int i=0;i<n;i++){
p[i+1]=(p[i]*BASE)%MOD;
h[i+1]=(h[i]*BASE + [Link](i))%MOD;
}
}
static long get(int l,int r){ // [l,r)
return (h[r] - (h[l]*p[r-l])%MOD + MOD)%MOD;
}
}

■ Note: For safety, consider double hashing with two moduli to reduce collisions.
Geometry
Orientation Test (CCW) + Line Intersection
public class GeometryBasics {
static long cross(long ax,long ay,long bx,long by){ return ax*by - ay*bx; }
static int orient(long ax,long ay,long bx,long by,long cx,long cy){
long v = cross(bx-ax, by-ay, cx-ax, cy-ay);
return [Link](v, 0);
}
static boolean onSeg(long ax,long ay,long bx,long by,long px,long py){
return [Link](ax,bx)<=px && px<=[Link](ax,bx) &&
[Link](ay,by)<=py && py<=[Link](ay,by);
}
static boolean inter(long ax,long ay,long bx,long by,long cx,long cy,long dx,long dy){
int o1=orient(ax,ay,bx,by,cx,cy);
int o2=orient(ax,ay,bx,by,dx,dy);
int o3=orient(cx,cy,dx,dy,ax,ay);
int o4=orient(cx,cy,dx,dy,bx,by);
if(o1*o2<0 && o3*o4<0) return true;
if(o1==0 && onSeg(ax,ay,bx,by,cx,cy)) return true;
if(o2==0 && onSeg(ax,ay,bx,by,dx,dy)) return true;
if(o3==0 && onSeg(cx,cy,dx,dy,ax,ay)) return true;
if(o4==0 && onSeg(cx,cy,dx,dy,bx,by)) return true;
return false;
}
}

Practice: CSES – Point Location Test, CSES – Polygon Area

Common Java CP Mistakes (and Fixes)

Pitfalls & Fixes:
• Use long for multiplications; cast before multiply (e.g., (long)a*b).
• Prefer FastScanner + PrintWriter; avoid Scanner for large inputs.
• String concatenation in loops → use StringBuilder.
• Beware of recursion depth; prefer iterative DFS/DP or increase stack if allowed.
• Avoid heavy object allocations in hot loops; use arrays where possible.

Contest Strategy & Checklist

• Read all problems quickly; solve A/B first for momentum.
• If stuck > 15–20 min, switch problems; upsolve later.
• Write from template; avoid re-typing I/O and helpers.
• Test on small custom cases; assert invariants during debug.
• After contest: upsolve 1–2 problems you couldn’t solve.

Quick Reference Sheet

Fast I/O FastScanner + PrintWriter

Math gcd, modPow, nCr mod p (precompute fact & inv)

DSU Path compression + union by size

BIT / SegTree O(log n) updates/queries

Graphs Iterative BFS/DFS; Dijkstra with PQ

DP Knapsack 1D; LIS O(n log n)

Strings KMP prefix; Rolling Hash