AtCoder 400 points algorithm summary (Java edition)

About half a year ago, I was satisfied with the light blue color, so I was away from the competition pro for a while, but from ABC on 5/19 (Sun) it will be ~ 2000 Rated. So, I thought about returning to this opportunity, so I reviewed the algorithm that frequently appeared in the 400-point problem that was solved at that time and made it into a template. The details of each algorithm will be left to other pages to specialize in the amount of calculation, usage, and template explanation. Stars represent frequency (arbitrary).

Mathematical calculation

GCD (greatest common divisor) ★★★

Even if the problem is less than 400 points, it will come out, but for the time being. You can calculate the greatest common divisor with O (log (min (num1, num2))). By the way, you can calculate the least common multiple with num1 * num2 / gcd.

gcd.java


	//return gcd O(logN)
	public static int gcd(int num1,int num2) {
		if(num2==0) return num1;
		else return gcd(num2,num1%num2);
	}

nCk (mod M) (combination) ★★

Especially since the mod processing of 10 ^ 9 + 7 was troublesome, I made it a template. Also power calculation. Exponentiation is the complexity of O (logb) with the base a / exponent b and O (min (k, n-k) * log M) for nCk (mod M).

combination.java


	//return nCk mod M (M must be prime number) O(min(k,n-k)*logM)
	public static int nCk(int n,int k,int M) {
		long ret = 1;
		int min = Math.min(k, n-k);
		for(int i=1;i<=min;i++) {
			ret = (ret * pow(i,M-2,M)) % M;
		}
		for(int i=n-min+1;i<=n;i++) {
			ret = (ret * i) % M;
		}
		return (int)ret;
	}

	//return a^b mod M O(logB)
	public static long pow(long a,long b,int M) {
		long ret = 1;
		long tmp = a;
		while(b>0) {
			if((b&1)==1) ret = (ret * tmp) % M;
			tmp = (tmp * tmp) % M;
			b = b>>1;
		}
		return ret;
	}

Convenient data structure

Union-Find ★★★ The problem of managing grouping is deadly. However, it is rare to answer as it is, and in most cases it is necessary to change the data structure inside to fit the problem. For example, transforming it to hold the number of nodes in the group. Since it is easy to ask the right application ability in that area, you will often be asked with 400 points. Both extracting parent nodes and joining groups can be performed faster than O (logN).

union-find.java


	//return root node idx O(a(N)) ( O(1)<O(a(N))<O(logN) )
	public static int find(int[] tree,int idx) {
		if(tree[idx]==idx) return idx;
		else return tree[idx] = find(tree,tree[idx]);
	}
	
	//union idx2 tree to idx1 tree O(a(N))
	public static void union(int[] tree,int idx1,int idx2) {
		int root1 = find(tree,idx1);
		int root2 = find(tree,idx2);
		tree[root2] = root1;
	}

BinaryIndexedTree ★ It is a data structure that can extract partial sums and add them to array elements by O (logN). If you just want to extract the partial sum, you can usually use the cumulative sum, but this is more suitable if you need to add to the array elements in the meantime. Well, I don't see much.

binary-indexed-tree.java


	//add value at idx on bit O(logN)
	public static void add(int[] bit,int idx,int value) {
		for(int i=idx;i<bit.length;i+=(i&-i)) bit[i] += value;
	}
	
	//return sum [1,idx] O(logN)
	public static int sum(int[] bit,int idx) {
		int ret = 0;
		for(int i=idx;i>0;i-=(i&-i)) ret += bit[i];
		return ret;
	}

Others (PriorityQueue) ★★★

I think that the rest will be managed with the Java standard library, but the one I often use is

Is it? It is a convenient one that adds elements and extracts maximum / minimum elements in 0 (logN) time respectively. It is also used in Dijkstra. However, by default, only the minimum value acquisition of the numeric type is accepted, so if you want to get the maximum value or insert an element other than the numeric type, let's define the Comparator by yourself. The sample is a Priority Queue defined by Comparator to insert the int array and get the 0th largest element.

priority-queue.java


		PriorityQueue<int[]> p_que = new PriorityQueue<>((array1,array2)->-array1[0]+array2[0]);

Shortest path problem

Dijkstra ★★

It is a familiar one with the shortest path problem. The amount of calculation is O (Elog V) with the number of nodes as V and the number of sides as E. However, if there is a negative side, it will not work well, so in that case Bellman Ford is used.

dijkstra.java


	//return min distance from start to end O(ElogV) (negative cost is prohibited)
	//edge is int[3] array {from,to,cost}
	//edges is edge list from specific node
	//all_edges is Map<from node number,edges>
	public static int dijkstra(Map<Integer,List<int[]>> all_edges,int start,int end,int max_node_number) {
		int[] distance = new int[max_node_number+1];
		for(int i=0;i<distance.length;i++) distance[i] = -1;
		PriorityQueue<int[]> p_que = new PriorityQueue<>((a,b)->((distance[a[0]]+a[2])-(distance[b[0]]+b[2])));
		distance[start] = 0;
		List<int[]> edges = all_edges.get(start);
		for(int i=0;i<edges.size();i++) p_que.add(edges.get(i));
		while(distance[end]<0) {
			int[] nearest_edge = p_que.poll();
			if(distance[nearest_edge[1]]<0) {
				distance[nearest_edge[1]] = distance[nearest_edge[0]] + nearest_edge[2];
				if(all_edges.containsKey(nearest_edge[1])) {
					edges = all_edges.get(nearest_edge[1]);
					for(int i=0;i<edges.size();i++) {
						int[] edge = edges.get(i);
						if(distance[edge[1]]<0) p_que.add(edge);
					}
				}
			}
		}
		return distance[end];
	}

Bellman Ford ★★

This algorithm is effective in cases where there is a negative edge in the shortest path problem. The amount of calculation is O (EV), which is slightly inferior to Dijkstra. However, there are some things that Dijkstra can't do, such as detecting negative cycles. Is there a negative side, or is there a loose restriction on the number of nodes and sides for Dijkstra? If you think about it, it may be this pattern.

bellman-ford.java


	//return min distance from start to end O(EV) (negative cost is possible)
	//edge is int[3] array {from,to,cost}
	//edges is edge list from specific node
	//all_edges is Map<from node number,edges>
	public static int bellmanFord(Map<Integer,List<int[]>> all_edges,int start,int end,int max_node_number) {
		int[] distance = new int[max_node_number+1];
		int INF = Integer.MAX_VALUE;
		for(int i=0;i<distance.length;i++) {
			distance[i] = INF;
		}
		distance[start] = 0;
		int counter = all_edges.size();
		while(counter>0) {
			boolean updated = false;
			for(List<int[]> edges: all_edges.values()) {
				if(distance[edges.get(0)[0]]==INF) continue;
				for(int[] edge: edges) {
					if(distance[edge[0]]+edge[2] < distance[edge[1]]) {
						distance[edge[1]] = distance[edge[0]]+edge[2];
						updated = true;
					}
				}
			}
			if(!updated) break;
			counter--;
		}
		return counter==0?Integer.MIN_VALUE:distance[end];
	}

Floyd-Warshall Floyd ★

This is useful when the shortest path problem requires the shortest distance between all nodes. Since the amount of calculation is heavy as O (V ^ 3) with the number of nodes as V, it can be used only when the constraint condition of the number of nodes is 100 or less, but on the contrary, if you know it, you can solve it in most cases, so remember There is no loss.

warshall-floyd.java


	//return new distance matrix O(logV^3)
	public static int[][] warshallFloyd(int[][] distance){
		int node_number = distance.length;
		int[][] min_distance = new int[node_number][node_number];
		for(int i=0;i<node_number;i++) {
			for(int j=0;j<node_number;j++) {
				min_distance[i][j] = distance[i][j];
			}
		}
		for(int via=0;via<node_number;via++) {
			for(int from=0;from<node_number;from++) {
				for(int to=0;to<node_number;to++) {
					min_distance[from][to] = Math.min(min_distance[from][to], min_distance[from][via]+min_distance[via][to]);
				}
			}
		}
		return min_distance;
	}

Minimum spanning tree problem

Kruskal method ★★

Often used for minimum spanning tree problems. The amount of calculation is O (Elog V) with the number of nodes as V and the number of sides as E. Union-Find is used to determine the connection state of nodes (whether they belong to the same group).

kruskal.java


	//return min cost for union all nodes O(ElogV)
	//edge is int[3] array {node1,node2,cost}
	//edges is edge list
	public static int kruskal(List<int[]> edges,int max_node_number) {
		edges.sort((a,b)->(a[2]-b[2]));
		int[] uft = new int[max_node_number+1];
		for(int i=0;i<uft.length;i++) {
			uft[i] = i;
		}
		int cost_sum = 0;
		for(int[] edge: edges) {
			if(find(uft,edge[0])!=find(uft,edge[1])) {
				union(uft,edge[0],edge[1]);
				cost_sum += edge[2];
			}
		}
		return cost_sum;
	}
	
	public static int find(int[] tree,int idx) {
		if(tree[idx]==idx) return idx;
		else return tree[idx] = find(tree,tree[idx]);
	}

	public static void union(int[] tree,int idx1,int idx2) {
		int root1 = find(tree,idx1);
		int root2 = find(tree,idx2);
		tree[root2] = root1;
	}

Other frequent topics

I can't template the algorithm, but the topic that comes up messed up is like this.

--Cumulative sum --DP (Dynamic Programming) --bit operation (bit full search, xor problem)

Since it cannot be templated, it is easy to measure the applied power / mounting power on the spot, so it will come out often. If you look it up, you'll find lots of related articles, so let's devote ourselves to ~ 2000 Rated ABC.

Recommended Posts

AtCoder 400 points algorithm summary (Java edition)
[Java Silver] Summary of access modifier points
Java knowledge summary
Java Generics Summary
Java related summary
Java Algorithm Library-Artery-Sample
Java 8 documentation summary
Java 11 document summary
Effective Java 2nd Edition Related Matters Survey Summary
[Summary] Java environment preparation
effective java 3rd summary
[Java Silver] Summary of points related to lambda expressions
Java 13 new feature summary
Java static [Personal summary]
Thread safe summary ~ Java ~
Java Primitive Specialization Summary
Java development link summary
About Java entry points
Personal summary about Java
paiza skill check standard input / output summary [Java edition]
Java 10 new feature summary
java regular expression summary
Java 14 new feature summary
Summary of Java support 2018
Java design pattern summary
Java reserved word summary
Java8 Stream Rough Summary
What is Java Assertion? Summary.
Modern Java Development Guide (2018 Edition)
[Java11] Stream Summary -Advantages of Stream-
Progate Java (Beginner) Review & Summary
Personal comment criteria [Java edition]
[Java] Summary of regular expressions
[Java] Summary of operators (operator)
Java8 stream, lambda expression summary
Object-oriented summary by beginners (Java)
AtCoder Challenge Environment Construction (Java 8)
Rails Tutorial (4th Edition) Summary
Summary of Java language basics
Java tips --Spring execution Summary
[Java] Summary of for statements
Summary of Java Math class
[Java11] Stream Usage Summary -Basics-
[Java] Summary of control syntax
Summary of java error processing
[Java] Summary of design patterns
[Java] Summary of mathematical operations
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 10)
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 7)
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 3)
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 9)
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 6)
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 4)
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 5)
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 2)
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 1)
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 11)
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 12)
Summary of "Design Patterns Learned in Java Language (Multithread Edition)" (Part 8)