Counting Pairs Whose Product is a Perfect Square

Given an array of length N, count the number of index pairs (i, j) where i < j such that the product A[i] * A[j] is a perfect square (a non-negative integer square).

Approach

For a non-zero integer x, define its square-free component as x divided by the largest perfect square divisor. Two non-zero numbers multiply to a perfect square if and only if their square-free components are equal. For zero, any product involving zero is a perfect square.

1. Process non-zero elements: For each element, compute its square-free component. Maintain a frequency map of these components. For each component, the number of new valid pairs equals its current frequency before incrementing.
2. Handle zeros: Let Z be the count of zeros encountreed so far. A zero forms a valid pair with every previous element (index). Also, each non-zero element forms a valid pair with all preceding zeros.

Implementation

import java.util.*;

public class SquarePairCounter {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextLong();
        
        Map<Long, Integer> compFreq = new HashMap<>();
        long totalPairs = 0;
        int zeroCount = 0;
        
        for (int idx = 0; idx < n; idx++) {
            long val = arr[idx];
            if (val == 0) {
                totalPairs += idx; // pair with all previous elements
                zeroCount++;
                continue;
            }
            
            long remainder = val;
            long sqrtLimit = (long) Math.sqrt(remainder);
            for (long s = sqrtLimit; s >= 1; s--) {
                long square = s * s;
                if (remainder % square == 0) {
                    remainder /= square;
                    break;
                }
            }
            
            int freq = compFreq.getOrDefault(remainder, 0);
            totalPairs += freq;
            compFreq.put(remainder, freq + 1);
            
            totalPairs += zeroCount;
        }
        System.out.println(totalPairs);
    }
}

Determining Latest Possible Departure Times in a Time-Table Graph

Given a directed graph with N nodes and M edges. Each edge has parameters (L, D, K, C, u, v): starting from node u, a train departs at times L, L+D, L+2D, ..., L+(K-1)*D. Each departure takes C time to travel from u to v. For each node, find the latest possible time to depart and still reach node N, or determine it's unreachable.

Strategy

Reverse the graph and treat node N as the source. Use a priority queue (max-heap) to propagate the latest feasible arrival time backwards through edges.

For a current node x with known latest arrival time T, consider an incoming edge (from v to x) with parameters (L, D, K, C). The latest possible departure time from v using this edge is the largest time t ≤ T - C such that t is in the arithmetic sequence: t = L + m*D, where m is an integer with 0 ≤ m < K. If such a t exists, it becomes a candidate latest arrival time for node v.

Implementation Details

import java.util.*;

class GraphEdge {
    int from, to, next;
    long start, interval, trips, cost;
    GraphEdge(int f, int t, long L, long D, long K, long C) {
        from = f; to = t;
        start = L; interval = D; trips = K; cost = C;
    }
}

class State implements Comparable<State> {
    int node;
    long time;
    State(int n, long t) { node = n; time = t; }
    public int compareTo(State other) {
        return Long.compare(other.time, this.time); // Max-heap
    }
}

public class LatestArrival {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int vertices = sc.nextInt();
        int edges = sc.nextInt();
        
        GraphEdge[] edgeList = new GraphEdge[edges + 1];
        int[] head = new int[vertices + 1];
        Arrays.fill(head, 0);
        int edgeCnt = 0;
        
        for (int i = 0; i < edges; i++) {
            long L = sc.nextLong();
            long D = sc.nextLong();
            long K = sc.nextLong();
            long C = sc.nextLong();
            int u = sc.nextInt();
            int v = sc.nextInt();
            edgeCnt++;
            edgeList[edgeCnt] = new GraphEdge(v, u, L, D, K, C);
            edgeList[edgeCnt].next = head[v];
            head[v] = edgeCnt;
        }
        
        long[] latestTime = new long[vertices + 1];
        Arrays.fill(latestTime, -1);
        latestTime[vertices] = Long.MAX_VALUE;
        
        PriorityQueue<State> pq = new PriorityQueue<>();
        pq.add(new State(vertices, Long.MAX_VALUE));
        
        while (!pq.isEmpty()) {
            State cur = pq.poll();
            if (cur.node != vertices && latestTime[cur.node] >= cur.time) continue;
            latestTime[cur.node] = cur.time;
            
            for (int eIdx = head[cur.node]; eIdx != 0; eIdx = edgeList[eIdx].next) {
                GraphEdge e = edgeList[eIdx];
                long latestDeparture = cur.time - e.cost;
                if (latestDeparture < e.start) continue;
                
                long steps = Math.min((latestDeparture - e.start) / e.interval, e.trips - 1);
                long candidateTime = e.start + steps * e.interval;
                pq.add(new State(e.to, candidateTime));
            }
        }
        
        for (int i = 1; i < vertices; i++) {
            if (latestTime[i] == -1) System.out.println("Unreachable");
            else System.out.println(latestTime[i]);
        }
    }
}