Monday, October 3, 2022

Codechef Starters 57, Tree and Divisors

Introduction


In TREEDIVS problem from Codechef Starters 57 contest, you need to compute the product of every node value within a node subtree, for each node of the tree.

While the output was correct, I got Time Limit Exceeded on my submission.





In this article, we will go over multiple optimization strategies to keep runtime execution short.

Refer for the successful submission from another community member from which I got the hints for the optimizations. See also Codechef editorial & Small-to-Large merging USACO article.


Setup


Sample input

The input consists of

  1. N, the tree size
  2. A, the list of node value
  3. (u_i, v_i), the list of edges to build adjacency list


3
4
100 101 102 103
1 2
1 3
1 4
4
2 2 2 2
1 2
2 3
3 4
5
43 525 524 12 289
1 2
1 3
3 4
4 5


Expected output


We output the list of node value products for each node:


192 2 8 2 
5 4 3 2
1080 12 60 18 3


Input Parsing


package codechef.starters57.TREEDIVS;

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class TreeAndDivisorsMain {
public static void main(String[] args) throws IOException {
TreeAndDivisorsFactory factory = TreeAndDivisors3::new;

//InputStream inputStream = System.in;
InputStream inputStream = new FileInputStream("TREEDIVS");
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

String[] tokens;

tokens = bufferedReader.readLine().split(" ");
int T = Integer.parseInt(tokens[0]);
while (T > 0) {
tokens = bufferedReader.readLine().split(" ");
int N = Integer.parseInt(tokens[0]);
tokens = bufferedReader.readLine().split(" ");

int[] A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(tokens[i]);
}

TreeAndDivisors treeAndDivisors = factory.createTreeAndDivisors(N, A);
for (int i = 0; i < N-1; i++) {
tokens = bufferedReader.readLine().split(" ");
int u = Integer.parseInt(tokens[0]);
int v = Integer.parseInt(tokens[1]);
treeAndDivisors.addEdge(u-1, v-1);
}

int[] divisorCount = treeAndDivisors.divisors();
String divisorLine = AbstractTreeAndDivisors.listToString(divisorCount);
writer.println(divisorLine);

T--;
}

writer.close();
inputStream.close();
}
}


Benchmark


We define an interface for the solution contract:


public interface TreeAndDivisors {
void addEdge(int u, int v);
int[] divisors();
}


We define a factory to decouple running a solution on input data from the implementation itself.


public interface TreeAndDivisorsFactory {
TreeAndDivisors createTreeAndDivisors(int n, int[] A);
}


We define a tree generator to compare the effect of the tree structure shape on runtime:


public interface TreeGenerator {
void generate(List<List<Integer>> adjacency);
}


Unit Test


Here's JUnit 5 parameterized unit test :


@ParameterizedTest
@MethodSource
public void correctness(int[] A, int[][] edges, int[] expectedDivisors) {
TreeAndDivisorsFactory factory = TreeAndDivisors3::new;
TreeAndDivisors treeAndDivisors = factory.createTreeAndDivisors(A.length, A);
Arrays.stream(edges)
.forEach(edge -> treeAndDivisors.addEdge(edge[0], edge[1]));
Assertions.assertArrayEquals(expectedDivisors, treeAndDivisors.divisors());
}

static Object[][] correctness() {
return new Object[][] {
new Object[] {
new int[] { 100, 101, 102, 103 },
new int[][] { { 0, 1 }, { 0, 2 }, { 0, 3 } },
new int[] { 192, 2, 8, 2 } }
};
}


Input Generation


We define 3 input generators:


static void setThickAdjacency(List<List<Integer>> adjacency) {
for (int i = 1; i < adjacency.size(); i++) {
adjacency.get(0).add(i);
}
}

static void setSlimAdjacency(List<List<Integer>> adjacency) {
for (int i = 1; i < adjacency.size(); i++) {
adjacency.get(i-1).add(i);
}
}

static void setRandomAdjacency(List<List<Integer>> adjacency) {
for (int i = 1; i < adjacency.size(); i++) {
int parent = random.nextInt(i);
adjacency.get(parent).add(i);
}
}


With setRandomAdjacency, we generate a random tree structure. For each node i, 0 < i < N, its parent is selected at random in [0, ..., i-1].


With setSlimAdjacency, we generate a list-like tree where each node only has one child.




With setThickAdjacency, we generate a single parent where each nodes other than the root are the children.





Analysis


Depth First Search traversal here is more practical than Breadth First Search. We only need the recursion to compute parent value from the children values.


Algorithm: DFS


Like in this other problem, we can setup a node visitor in DFS traversal. It abstracts away DFS implementation logics. We can then focus only on the node value update logics, located in updateNode method.

private void dfs() {
Traversal traversal = new AdjacencyListDFSTraversal(adjacency);
traversal.traverse(this::updateNode);
}

protected abstract void updateNode(int current, int parent, List<Integer> children);

Data structure: Hash Map


When computing a current node product value, we need to keep track of the prime factorization of the product value for each child node.

Each prime factorization is stored as a Map<Integer,Integer> where

  • keys are prime numbers
  • values are associated exponents


Version 1


private void updateNode(int current, int parent, List<Integer> children) {
Map<Integer, Integer> parentExponents = primeFactors(A[current]);

children.stream()
.filter(child -> !(child == parent))
.map(child -> primeExponents[child])
.forEach(childExponents -> mergeExponents(parentExponents, childExponents));

primeExponents[current] = parentExponents;
divisorCount[current] = divisorCount(parentExponents);
}

On the slim adjacency use case, assuming each node values are distinct primes,

  • node n-1 requires 0 merges
  • node n-2 requires 1 merges
  • ...
  • node 0 requires n-1 merges

This results in O(N^2) total merges.

We see an exponential trend in the runtime as N grows:




We start getting memory error as we increase N. It is thrown when increasing hash table size in HashMap resize.


Caused by: java.lang.OutOfMemoryError: Java heap space
at java.base/java.util.HashMap.resize(HashMap.java:702)
at java.base/java.util.HashMap.merge(HashMap.java:1363)
at codechef.starters57.TREEDIVS.AbstractTreeAndDivisors.mergeExponents(AbstractTreeAndDivisors.java:85)
at codechef.starters57.TREEDIVS.TreeAndDivisors1.lambda$updateNode$2(TreeAndDivisors1.java:19)
at codechef.starters57.TREEDIVS.TreeAndDivisors1$$Lambda$472/0x0000000800d54248.accept(Unknown Source)
at java.base/java.util.stream.ForEachOps$ForEachOp$OfRef.accept(ForEachOps.java:183)
at java.base/java.util.stream.ReferencePipeline$3$1.accept(ReferencePipeline.java:197)
at java.base/java.util.stream.ReferencePipeline$2$1.accept(ReferencePipeline.java:179)
at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1625)
at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509)
at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499)
at java.base/java.util.stream.ForEachOps$ForEachOp.evaluateSequential(ForEachOps.java:150)
at java.base/java.util.stream.ForEachOps$ForEachOp$OfRef.evaluateSequential(ForEachOps.java:173)
at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
at java.base/java.util.stream.ReferencePipeline.forEach(ReferencePipeline.java:596)
at codechef.starters57.TREEDIVS.TreeAndDivisors1.updateNode(TreeAndDivisors1.java:19)
at codechef.starters57.TREEDIVS.AbstractTreeAndDivisors$$Lambda$466/0x0000000800d4efa0.visit(Unknown Source)
at graph.tree.traversal.AbstractDFSTraversal.traverse(AbstractDFSTraversal.java:63)
at graph.tree.traversal.AbstractDFSTraversal.traverse(AbstractDFSTraversal.java:36)
at codechef.starters57.TREEDIVS.AbstractTreeAndDivisors.dfs(AbstractTreeAndDivisors.java:78)
at codechef.starters57.TREEDIVS.AbstractTreeAndDivisors.divisors(AbstractTreeAndDivisors.java:67)
at codechef.starters57.TREEDIVS.TreeAndDivisorsTest.runInput(TreeAndDivisorsTest.java:89)
at codechef.starters57.TREEDIVS.TreeAndDivisorsTest.runBatch(TreeAndDivisorsTest.java:68)
at codechef.starters57.TREEDIVS.TreeAndDivisorsTest.run(TreeAndDivisorsTest.java:24)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:77)
at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.base/java.lang.reflect.Method.invoke(Method.java:568)
at org.junit.platform.commons.util.ReflectionUtils.invokeMethod(ReflectionUtils.java:725)
at org.junit.jupiter.engine.execution.MethodInvocation.proceed(MethodInvocation.java:60)
at org.junit.jupiter.engine.execution.InvocationInterceptorChain$ValidatingInvocation.proceed(InvocationInterceptorChain.java:131)
at org.junit.jupiter.engine.extension.TimeoutExtension.intercept(TimeoutExtension.java:149)


To reduce memory footprint, we can null out children Map references. It will mark the objects as candidates for Garbage Collection. We no longer need them after computing parent Map.


@Override
protected void updateNode(int current, int parent, List<Integer> children) {
Map<Integer, Integer> parentExponents = primeFactors(A[current]);

children.stream()
.filter(child -> !(child == parent))
.forEach(child -> {
mergeExponents(parentExponents, primeExponents[child]);
primeExponents[child] = null;
});

primeExponents[current] = parentExponents;
divisorCount[current] = divisorCount(parentExponents);
}


We can now see the O(N^2) trend:



Version 2


private void updateNode(int current, int parent, List<Integer> children) {
Map<Integer, Integer> valueExponents = primeFactors(A[current]);

Optional<Integer> maxOptional = children.stream()
.filter(child -> child != parent)
.max(Comparator.comparing(child -> primeExponents[child].size()));

Map<Integer, Integer> parentExponents;

if (maxOptional.isPresent()) {
int maxChild = maxOptional.get();

parentExponents = primeExponents[maxChild];
mergeExponents(parentExponents, valueExponents);
children.stream()
.filter(child -> !(child == parent || child == maxChild))
.map(child -> primeExponents[child])
.forEach(childExponents -> mergeExponents(parentExponents, childExponents));
} else {
parentExponents = valueExponents;
}

primeExponents[current] = parentExponents;
divisorCount[current] = divisorCount(parentExponents);
}


We can skip a high ratio of the total merges for free by reusing a child object. We get most bang for the buck by extracting the child with the max Map size. Then just reuse the same object to assign it to the current node.


It turns out that there's still room for improvement in HashMap iterations. We are iterating through the hash table twice

  1. merge prime factor exponents
  2. compute divisor count


Version 3


We can reduce the hash table scans by 50% by performing both actions at once. We switch to mergeMultiplyExponents instead of mergeExponents to now perform both actions at once.


private void updateNode(int current, int parent, List<Integer> children) {
Map<Integer, Integer> valueExponents = primeFactors(A[current]);

Optional<Integer> maxOptional = children.stream()
.filter(child -> child != parent)
.max(Comparator.comparing(child -> primeExponents[child].size()));

Map<Integer, Integer> parentExponents;
int dc;

if (maxOptional.isPresent()) {
int maxChild = maxOptional.get();

parentExponents = primeExponents[maxChild];
dc = divisorCount[maxChild];

dc = mergeMultiplyExponents(dc, parentExponents, valueExponents);

for (int child: children) {
if (child == parent || child == maxChild) {
continue;
}
dc = mergeMultiplyExponents(dc, parentExponents, primeExponents[child]);
}
} else {
parentExponents = valueExponents;
dc = divisorCount(valueExponents);
}

primeExponents[current] = parentExponents;
divisorCount[current] = dc;
}


Gradle Report


See this commit for the full application code.

We compare runs multiple versions against random and slim input types.

Compare execution times for slim input across the versions on N=4000 nodes.

  1. [2][27.915s] Original version
  2. [4][17.442s] Null out children maps
  3. [6][4.536s] Reuse max child Map
  4. [8][0.312s] Reuse Map scan for both merging and divisor count computation


TestMethod nameDurationResult
random, Original, N=30000run(String, String, int, TreeGenerator, TreeAndDivisorsFactory)[1]3.562spassed
slim, Original, N=4000run(String, String, int, TreeGenerator, TreeAndDivisorsFactory)[2]27.915spassed
random, Null out children maps, N=30000run(String, String, int, TreeGenerator, TreeAndDivisorsFactory)[3]3.324spassed
slim, Null out children maps, N=4000run(String, String, int, TreeGenerator, TreeAndDivisorsFactory)[4]17.442spassed
random, Reuse max child Map, N=30000run(String, String, int, TreeGenerator, TreeAndDivisorsFactory)[5]3.368spassed
slim, Reuse max child Map, N=4000run(String, String, int, TreeGenerator, TreeAndDivisorsFactory)[6]4.536spassed
random, 50% less Map scans, N=30000run(String, String, int, TreeGenerator, TreeAndDivisorsFactory)[7]3.881spassed
slim, 50% less Map scans, N=4000run(String, String, int, TreeGenerator, TreeAndDivisorsFactory)[8]0.312spassed


See codechef submissions for 3 versions

  1. Version 1
  2. Version 2
  3. Version 3





Conclusion


As we merge hash tables bottom-up towards the root, hash table grows significantly. Iterating through the entries is the bottleneck in the code execution. We should optimize towards reducing full hash table scans as much as possible.



Appendix


Plotting code


#!/usr/bin/env python3

import matplotlib.pyplot as plt
import numpy as np

x = [ 100, 500, 1000, 2000, 3000, 4000 ]

y_random = [ 0.054, 0.082, 0.117, 0.204, 0.309, 0.417 ]
y_slim = [ 0.079, 0.394, 1.143, 4.167, 9.741, 26.487 ]
y_slim_null = [ 0.051, 0.371, 1.125, 4.076, 8.883, 16.031 ]

p_random = np.polyfit(x, y_random, 1)
p_slim = np.polyfit(x, np.log(y_slim), 1, w=np.sqrt(y_slim))
p_slim_null = np.polyfit(x, y_slim_null, 2)

x_interpolated = np.arange(0, 4100, 100)
yi_random = np.polyval(p_random, x_interpolated)
yi_slim = np.exp(np.polyval(p_slim, x_interpolated))
yi_slim_null = np.polyval(p_slim_null, x_interpolated)

fig, ax = plt.subplots()
ax.plot(x, y_random, 'r+', label='Random adjacency list')
ax.plot(x, y_slim, 'go', label='Slim adjacency list')
ax.plot(x, y_slim_null, 'bx', label='Slim adjacency list, less memory')
ax.plot(x_interpolated, yi_random, 'r', label='Linear interpolation')
ax.plot(x_interpolated, yi_slim, 'g', label='Exponential interpolation')
ax.plot(x_interpolated, yi_slim_null, 'b', label='Square interpolation')

plt.title('TREEDIVS runtime')
plt.xlabel('N')
plt.ylabel('Time (seconds)')
plt.legend()
plt.show()

Dot graphs

Slim

digraph G {

  0 -> 1

  1 -> 2

  2 -> 3

  3 -> 4

  4 -> 5

  5 -> 6

  6 -> 7

  7 -> 8

  8 -> 9

} 

Thick

digraph G {

  0 -> 1

  0 -> 2

  0 -> 3

  0 -> 4

  0 -> 5

  0 -> 6

  0 -> 7

  0 -> 8

  0 -> 9

}


Wednesday, September 7, 2022

Meta Hacker Cup 2022, Qualification Round, Problem D, Second Flight

Introduction


In Problem D, we need to return the max number of passengers who can travel from airport X to airport Y, using either

  1. a direct flight, available in the morning & the evening
  2. a 2-leg flight, going through 1 intermediate airport

Graph contains N nodes and M edges. We need to run Q queries overall.


Interface


The end-goal is to implement following interface within the problem constraints,


interface SecondFlightService {
void addFlight(int x, int y, int capacity);
void setConnectionCapacity();
long passengers(int x, int y);
}

  • addFlight is called for each edge to add it
  • setConnectionCapacity is called once after all edges were added
  • passengers is called to process the query

Input Parsing


package hackercup2022;

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class SecondFlight implements SecondFlightService {

public static void main(String[] args) throws Exception {
//InputStream inputStream = System.in;
InputStream inputStream = new FileInputStream("second_flight_sample_input.txt");
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(inputStream));

//OutputStream outputStream = System.out;
OutputStream outputStream = new FileOutputStream("second_flight_sample_output.txt");
PrintWriter writer = new PrintWriter(new BufferedOutputStream(outputStream));

String[] tokens;

tokens = bufferedReader.readLine().split(" ");
int T = Integer.parseInt(tokens[0]);
for (int t = 1; t <= T; t++) {
tokens = bufferedReader.readLine().split(" ");
int N = Integer.parseInt(tokens[0]);
int M = Integer.parseInt(tokens[1]);
int Q = Integer.parseInt(tokens[2]);
int[] A = new int[M];
int[] B = new int[M];
int[] C = new int[M];
SecondFlightService secondFlight = new SecondFlight(N);
for (int i = 0; i < M; i++) {
tokens = bufferedReader.readLine().split(" ");
A[i] = Integer.parseInt(tokens[0]);
B[i] = Integer.parseInt(tokens[1]);
C[i] = Integer.parseInt(tokens[2]);
secondFlight.addFlight(A[i], B[i], C[i]);
}

secondFlight.setConnectionCapacity();

writer.print(String.format("Case #%d:", t));
for (int i = 0; i < Q; i++) {
tokens = bufferedReader.readLine().split(" ");
int x = Integer.parseInt(tokens[0]);
int y = Integer.parseInt(tokens[1]);
writer.print(" " + secondFlight.passengers(x, y));
}
writer.println();
}

writer.close();
outputStream.close();
inputStream.close();
}
}


Solution with adjacency matrix


We iterate over the list of nodes. We maintain 2 2D arrays, capacity vs connectionCapacity, to maintain the counts for direct vs indirect flights.


public class SecondFlight {


/**
* number of airports
*/
int N;

public SecondFlight(int N) {
this.N = N;
capacity = new int[N+1][N+1];
connectionCapacity = new int[N+1][N+1];
}

int[][] capacity;
int[][] connectionCapacity;
public void addFlight(int a, int b, int c) {
capacity[a][b] = c;
capacity[b][a] = c;
}

public void setConnectionCapacity() {
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
if (capacity[x][y] == 0) {
continue;
}
for (int z = 1; z <= N; z++) {
if (capacity[y][z] == 0 || x == z) {
continue;
}

connectionCapacity[x][z] += Math.min(capacity[x][y], capacity[y][z]);
connectionCapacity[z][x] = connectionCapacity[z][x];
}
}
}
}

public int passengers(int x, int y) {
return 2 * capacity[x][y] + connectionCapacity[x][y];
}
}


This approach runs in O(N^3) runtime complexity, O(N^2) space complexity.

We cache all possible values. Each 2-leg flight [x, y, z] contribute to the count for associated (x, z) pair.

The matrix is symmetrical since we use an undirected graph. A flight going in either direction [x,y] or [y,x] has the same capacity.


Caching all values


We now switch from adjacency matrix to adjacency list.

We use directed edges to represent the graph.


static class Edge {
int a, b, capacity;
Edge(int a, int b, int capacity) {
this.a = a;
this.b = b;
this.capacity = capacity;
}
}


We iterate over List<Edge> the list of edges, instead of nodes.

We lookup the list of the airports connected to any airport in List<List<Edge> adjacency list.


public class SecondFlight {


/**
* number of airports
*/
int N;

int[][] capacity;


List<Edge> edges = new ArrayList<>();
List<List<Edge>> adjacency = new ArrayList<>();

public SecondFlight(int N) {
this.N = N;
capacity = new int[N+1][N+1];

for (int i = 0; i <= N; i++) {
adjacency.add(new ArrayList<>());
}
}

public void addFlight(int a, int b, int c) {
addEdge(new Edge(a, b, c));
addEdge(new Edge(b, a, c));
}

private void addEdge(Edge edge) {
edges.add(edge);
adjacency.get(edge.a).add(edge);
capacity[edge.a][edge.b] = 2*edge.capacity;
}


public void setConnectionCapacity() {
edges.forEach(this::addSecondLeg);
}

private void addSecondLeg(Edge leg1) {
for (Edge leg2 : adjacency.get(leg1.b)) {
if (leg2.b != leg1.a) {
capacity[leg1.a][leg2.b] += Math.min(leg1.capacity, leg2.capacity);
}
}
}

public int passengers(int x, int y) {
return capacity[x][y];
}
}


What's the new runtime complexity?

For each edge leg1, we iterate over all the neighbors of the destination airport of the flight represented by leg1. If we don't end up with a round trip, we update the count associated to the considered 2-leg flight, [leg1.a, leg1.b, leg2.b]

Each edge incoming to a node v can be used as leg1, each edge outgoing from v can be used as leg2, as long as it's not the reverse of leg1.

Since this is undirected graph, we have

deg_in(v) = deg_out(v) = deg(v)

so the overall complexity is

Sum(deg(v)^2) <= (Sum(deg(v))^2 = M^2

To summarize,

  • runtime complexity is O(M^2)
  • space complexity is O(N^2)

which won't work with problem constraint

1 <= M,N <= 200 000


Computing the query


Computing the query instead of precomputing it does not require the 2-D array:


public class SecondFlight implements SecondFlightService {


/**
* number of airports
*/
int N;

static class Edge {
int a, b, capacity;
Edge(int a, int b, int capacity) {
this.a = a;
this.b = b;
this.capacity = capacity;
}

@Override
public String toString() {
return String.format("(%d->%d) %d", a, b, capacity);
}
}
List<Map<Integer, Edge>> adjacency = new ArrayList<>();

public SecondFlight(int N) {
this.N = N;
for (int i = 0; i <= N; i++) {
adjacency.add(new HashMap<>());
}
}

public void addFlight(int a, int b, int c) {
addEdge(new Edge(a, b, c));
addEdge(new Edge(b, a, c));
}

private void addEdge(Edge edge) {
adjacency.get(edge.a).put(edge.b, edge);
}

public void setConnectionCapacity() {
}

public long passengers(int x, int y) {
long p = 0;
for (Edge leg1: adjacency.get(x).values()) {
if (leg1.b == y) {
p += 2 * leg1.capacity;
continue;
}

Edge leg2 = adjacency.get(leg1.b).get(y);
if (leg2 == null) {
continue;
}

p += Math.min(leg1.capacity, leg2.capacity);
}
return p;
}
}


We switched from List<Edge> to  Map<Integer, Edge> in adjacency list.

The complexity of calculating the result is O(deg(x)) which is O(M).


Optimizations


Optimizations outlined in the editorial are


Caching query results


We cache the results in a 2D map, Map<Integer, Map<Integer, Long>>.

Selecting the node with smaller degree


We check adjacency list size to pick start node with fewer neighbors.

Solution


The new version for the query logics is

Map<Integer, Map<Integer, Long>> results = new HashMap<>();

public long passengers(int x, int y) {
if (adjacency.get(x).size() > adjacency.get(y).size()) {
return passengers(y, x);
}
// assert x has fewer neighbors than y

return results.computeIfAbsent(x, x2 -> new HashMap<>())
.computeIfAbsent(y, y2 -> computePassengers(x, y));
}

private long computePassengers(int x, int y) {
long p = 0;
for (Edge leg1: adjacency.get(x).values()) {
if (leg1.b == y) {
p += 2 * leg1.capacity;
continue;
}

Edge leg2 = adjacency.get(leg1.b).get(y);
if (leg2 == null) {
continue;
}

p += Math.min(leg1.capacity, leg2.capacity);
}
return p;
}

Conclusion


Simple approaches did not fit problem constraints.

We looked at doing offline computation. To get query in O(1), caching all values required O(N^2) space complexity. Calculating them was O(M^2) runtime complexity. Both size are impractical.

For online computation, 1 query's runtime was at first O(M) with optimized data structure using map in adjacency list.

It turned out that simple further optimizations such as caching previous queries and picking node with smaller degree did the trick to reduce overall runtime from O(Q*M) down to O(Q^(1/2)*M).