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).
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);
}
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;
}
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;
}
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]);
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];
}
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];
}
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;
}
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;
}
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