Scribd
Upload
12 views6 pages

FastScanner for Java Input Handling

The document contains three Java programs that solve different problems related to graph traversal. The first program finds the nearest meeting cell between two nodes, the second calculates the largest sum cycle in a directed graph, and the third identifies the maximum weight node based on incoming edges. Each program uses a custom FastScanner class for efficient input handling.

Uploaded by

rithikk416
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views6 pages

FastScanner for Java Input Handling

The document contains three Java programs that solve different problems related to graph traversal. The first program finds the nearest meeting cell between two nodes, the second calculates the largest sum cycle in a directed graph, and the third identifies the maximum weight node based on incoming edges. Each program uses a custom FastScanner class for efficient input handling.

Uploaded by

rithikk416
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Nearest Meeting Cell

import [Link].*;
import [Link].*;

public class Main {


public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner([Link]);

// Reading format inferred from the sample:


// T (number of test cases)
// For each test:
// N
// N integers: next[0..N-1] (use -1 for no exit)
// c1 c2
int T = [Link]();
StringBuilder out = new StringBuilder();
while (T-- > 0) {
int N = [Link]();
int[] next = new int[N];
for (int i = 0; i < N; i++) next[i] = [Link]();
int c1 = [Link]();
int c2 = [Link]();

int ans = closestMeetingCell(next, c1, c2);


[Link](ans).append('\n');
}
[Link]([Link]());
}

// Core logic
static int closestMeetingCell(int[] next, int c1, int c2) {
int n = [Link];
int[] d1 = walkDistances(next, c1);
int[] d2 = walkDistances(next, c2);

int bestNode = -1;


long best = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (d1[i] >= 0 && d2[i] >= 0) {
long worst = [Link](d1[i], d2[i]);
if (worst < best || (worst == best && i < bestNode)) {
best = worst;
bestNode = i;
}
}
}
return bestNode;
}

// Record distance from start to each reachable node; -1 means unreachable.


static int[] walkDistances(int[] next, int start) {
int n = [Link];
int[] dist = new int[n];
[Link](dist, -1);
int cur = start, d = 0;
while (cur != -1 && dist[cur] == -1) {
dist[cur] = d++;
cur = next[cur];
}
return dist;
}

// Lightweight fast scanner for Java 8


static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { [Link] = is; }
private int read() throws IOException {
if (ptr >= len) {
len = [Link](buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sgn = 1, val = 0;
do { c = read(); } while (c <= ' '); // skip spaces
if (c == '-') { sgn = -1; c = read(); }
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return val * sgn;
}
}
}

Largest Sum Cycle

import [Link].*;
import [Link].*;

public class Main {


public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner([Link]);

// Input format, inferred to match your screenshots:


// T
// For each test case:
// N
// N integers next[0..N-1] (use -1 for no exit; if your data uses some other senti
int T = [Link]();
StringBuilder sb = new StringBuilder();
while (T-- > 0) {
int N = [Link]();
int[] next = new int[N];
for (int i = 0; i < N; i++) next[i] = [Link]();

long ans = largestSumCycle(next);


[Link](ans).append('\n');
}
[Link]([Link]());
}

// Core: Find maximum sum of node indices in any cycle; -1 if none.


static long largestSumCycle(int[] next) {
int n = [Link];
byte[] state = new byte[n]; // 0 = unvisited, 1 = in path, 2 = processed
int[] seenAt = new int[n];
long[] prefAt = new long[n];

int tick = 1;
long best = -1;

for (int start = 0; start < n; start++) {


if (state[start] != 0) continue;

int u = start;
while (u != -1 && state[u] == 0) {
state[u] = 1;
seenAt[u] = tick++;
u = next[u];
}

if (u != -1 && state[u] == 1) {
long sum = 0;
int cur = u;
do {
sum += cur;
cur = next[cur];
} while (cur != u && cur != -1);
best = [Link](best, sum);
}

int x = start;
while (x != -1 && state[x] == 1) {
state[x] = 2;
x = next[x];
}
}
return best;
}

static class FastScanner {


private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = [Link](buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sgn = 1, val = 0;
do { c = read(); } while (c <= ' ');
if (c == '-') { sgn = -1; c = read(); }
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return val * sgn;
}
}
}

Maximum Weight Node

import [Link].*;
import [Link].*;

public class Main {


public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner([Link]);

// Expected input format:


// T
// For each test:
// N
// N integers: next[0..N-1] (use -1 for no exit)
int T = [Link]();
StringBuilder out = new StringBuilder();
while (T-- > 0) {
int N = [Link]();
int[] next = new int[N];
for (int i = 0; i < N; i++) next[i] = [Link]();

int ans = maximumWeightNode(next);


[Link](ans).append('\n');
}
[Link]([Link]());
}

static int maximumWeightNode(int[] next) {


int n = [Link];
long[] w = new long[n];
boolean anyIncoming = false;

for (int i = 0; i < n; i++) {


int v = next[i];
if (v >= 0 && v < n) {
w[v] += i;
anyIncoming = true;
}
}

if (!anyIncoming) return -1;

long bestW = Long.MIN_VALUE;


int bestIdx = -1;
for (int v = 0; v < n; v++) {
if (w[v] > bestW || (w[v] == bestW && v > bestIdx)) {
bestW = w[v];
bestIdx = v;
}
}
return bestIdx;
}

static class FastScanner {


private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = [Link](buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sgn = 1, val = 0;
do { c = read(); } while (c <= ' ');
if (c == '-') { sgn = -1; c = read(); }
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return val * sgn;
}
}
}

Common questions

Powered by AI

Using an array of next nodes as graph representation is significant because it allows the implementation of succinct, space-efficient algorithms that can handle node connections implicitly by indices, rather than explicitly listing edges. This allows direct access and manipulation to align with indexed-based procedures for cycle detection, distance calculations, and node weight accumulation within algorithms like 'closestMeetingCell', 'largestSumCycle', and 'maximumWeightNode'. Such representation is particularly advantageous in tight optimization scenarios like competitive programming, facilitating quick lookups and reduced overhead .

The 'FastScanner' class is optimized for fast input processing by using a large buffer (1 << 16), which minimizes the number of read operations needed by handling large chunks of data at once. It efficiently manages pointer positions within the buffer and reads input byte by byte, only converting relevant digits into integers. This reduces the overhead of multiple I/O operations, making it significantly faster than standard input methods, especially useful in competitive programming where speed is crucial .

The primary advantage of these algorithms for use with large sparse graphs is their emphasis on direct node operations and linear path-based evaluations rather than matrix representations, which significantly conserves memory and reduces computational overhead during traversals and cycle detections. However, the limitation lies in the assumption of immediate node link accessibilities; sparse graphs with high node counts but sparse connectivity may underutilize algorithm capabilities since many nodes may remain unvisited if disjoint sets abound, possibly leading to inefficient processing times or incomplete insights. Additionally, the reliance on indices presumes validity within the bounds, restricting practical application when dynamic graph expansions or contractions occur .

For the best meeting point in 'closestMeetingCell', ties in maximum distance are resolved by selecting the node with the smallest index (i < bestNode). Similarly, for determining the maximum weight node in 'maximumWeightNode', if nodes have the same accumulated weight, the node with the larger index is chosen (v > bestIdx). These tie-breaking strategies ensure consistent results by establishing a clear, deterministic choice when multiple options are equally optimal based on primary criteria .

The 'maximumWeightNode' function returns -1 if no node has any incoming edges, indicated by the 'anyIncoming' flag remaining false. This occurs when the input graph is comprised entirely of isolated nodes or nodes leading to exits without forming any apparent link to other nodes, meaning no weights can be accumulated for any node .

The 'closestMeetingCell' function first calculates the distance from each node to the starting nodes c1 and c2 using the 'walkDistances' function, which records the distance from a start node to each reachable node. Then, it iterates through the nodes to find the node where both c1 and c2 can reach, identifying the 'bestNode' as the one with the smallest maximum distance from c1 and c2. If multiple nodes have the same distance, the node with the smaller index is chosen. This ensures the shortest path for both nodes to meet at a common point .

The 'seenAt' and 'prefAt' arrays are instrumental in cycle detection within the 'largestSumCycle' function by recording when a node was first visited ('seenAt[u] = tick') and the sequence of node indices encountered ('prefAt'). Incrementally assigning unique ticking values as nodes are visited allows accurate tracking of revisitations that indicate cycles. When a node already in the current path (state 1) is revisited before conversion to fully processed (state 2), it denotes a cycle. The 'prefAt' values are then used to sum node indices for potential inclusion in the maximum sum calculation, efficiently leveraging the cumulative path built until the cycle is confirmed .

The 'largestSumCycle' function uses a depth-first search-like algorithm with two arrays: 'state' to track the visit status (unvisited, in path, processed) and 'seenAt' with 'tick' to track the index when a node is first visited. It detects cycles when a currently visited node in path is revisited (state 1), summing node indices within the cycle. The maximum sum among all cycles is recorded and compared using the 'best' variable. This algorithm efficiently tracks and computes cycle sums in a single pass by marking nodes as fully processed once all reachable nodes in their cycle are evaluated .

The 'state' array in the 'largestSumCycle' function tracks the visit status of each node: 0 for unvisited, 1 for in path (currently visiting), and 2 for processed (completed visiting). This helps in detecting cycles by identifying when a node is revisited while it's still in path (state 1), thus allowing the calculation of the cycle's total node index sum within the cycle detection part of the function .

The 'walkDistances' function contributes by calculating the shortest path distances from a specified start node to all other nodes reachable in the graph. By marking distances from c1 and c2 separately in the 'closestMeetingCell' function, it allows for the comparison of feasible meeting points where both nodes converge. This information is used to determine the node that minimizes the maximum distance either start position would need to traverse, directly aiding in finding the closest meeting cell .

You might also like