Moving ants

Problem Statement

There are NN little ants moving on the x-axis. Each ant ii starts moving at time 0 toward a piece of sugar located at x-coordinate DD. Ant ii begins at position PiP_i on the x-axis, moving at a constant speed SiS_i units. All ants start moving at the same time.

A group of ants moving at the same speed from the same position is known as an ant colony. When two or more ants meet at some position, they merge into one ant colony and continue to move toward the piece of sugar with a new speed that is the minimum of all speeds of the ants that merged. If multiple ants (or colonies) reach the piece of sugar at exactly the same time, they are considered one single colony upon arrival.

Task

You need to determine how many ant colonies cross the piece of sugar at DD.

Input Format

An integer TT — the number of test cases (where 1≤T≤101 \le T \le 10).
For each test case:
- An integer NN — the number of ants (1≤N≤105)(1 \le N \le 10^5).
- An integer DD — the position of the piece of sugar (1≤D≤109)(1 \le D \le 10^9).
- A line containing NN integers P1,P2,…,PNP_1, P_2, \ldots, P_N — the initial positions of the ants. (1≤Pi≤1091 \le P_i \le 10^9, and all PiP_i are distinct, and max⁡(Pi)≤D\max(P_i) \le D.)
- A line containing NN integers S1,S2,…,SNS_1, S_2, \ldots, S_N — the speeds of the ants (1≤Si≤109)(1 \le S_i \le 10^9).

Output Format

For each test case, print a single integer — the total number of ant colonies that cross the piece of sugar.

Sample Input

Sample Output

Explanation of the Sample

Number of Test Cases: T=1T = 1
Number of Ants: N=3N = 3
Sugar Position: D=7D = 7
Ant Positions: P=(4,5,1)P = (4, 5, 1)
Ant Speeds: S=(4,1,5)S = (4, 1, 5)
Approach (as described in the images): Ant 1 (position 4, speed 4) and Ant 2 (position 5, speed 1) collide somewhere between x=5 and x=6, forming one colony. Then, this colony collides again at x=6 with Ant 3 (position 1, speed 5), merging all ants into a single colony. Thus, only 1 colony ultimately reaches D=7D=7.

Note:

All ants move at a constant speed until they merge, after which they adopt the colony’s minimum speed.
If multiple ants reach the sugar at the exact same time, they are treated as a single colony.

You are to implement a function (often named solve in competitive programming) that, given NN, DD, arrays PP and SS, computes the final number of colonies crossing the sugar.

Anwer

Key Points

Partition Ants by Side
- Ants with position < DD are considered on the left side, traveling right.
- Ants with position > DD are considered on the right side, traveling left.
- (If an ant starts exactly at DD, it’s already at the sugar and can be considered its own colony, or you can merge them as needed.)
Compute Arrival Times
- For an ant at position pp with speed ss, the arrival time to DD is ∣p−D∣/s\lvert p - D \rvert / s.
Car-Fleet Merging Logic
- Left side: sort ants by position in descending order (closest to DD first).
- Right side: sort ants by position in ascending order (closest to DD first).
- For each side, we iterate over the ants in sorted order and maintain a stack (list) of distinct arrival times.
  - If the new ant’s arrival time ≤\le the top of the stack, it merges with that colony.
  - Otherwise, it starts a new colony (push its arrival time).
Unify Arrival Times from Both Sides
- Once we have the final set of colony arrival times for the left side and the right side, we unify them in a single set.
- If a time tt appears on both sides, that indicates ants from the left and right arrive simultaneously, merging into a single colony at DD.
Answer
- The number of distinct arrival times in the unified set is the total number of colonies crossing DD.

Below is the Java code demonstrating this approach:

import java.util.*;

public class AntColoniesBothSides {

    /**
     * Given arrays of positions and speeds for ants, plus the sugar coordinate D,
     * returns the number of distinct "ant colonies" that arrive at D.
     * Ants on the left side (pos < D) move right; ants on the right side (pos > D) move left.
     * If multiple ants from the same side catch up, they merge. 
     * If an arrival time from left side equals an arrival time from right side, 
     * they merge at D as well, forming a single colony.
     */
    public static int numberOfColoniesCrossSugar(int[] positions, int[] speeds, int D) {
        // Separate ants by side
        List<int[]> leftAnts = new ArrayList<>();   // (pos, speed)
        List<int[]> rightAnts = new ArrayList<>();  // (pos, speed)
        
        int totalGroups = 0;

        for (int i = 0; i < positions.length; i++) {
            int pos = positions[i];
            int spd = speeds[i];
            if (pos < D) {
                leftAnts.add(new int[] {pos, spd});
            } else if (pos > D) {
                rightAnts.add(new int[] {pos, spd});
            } else {
                // pos == D means the ant is already at sugar => 
                // it can be considered an immediate single-colony
                totalGroups++;
            }
        }

        // Compute arrival times for left side
        // Sort descending by pos (closest to D first => largest pos first)
        leftAnts.sort((a,b) -> b[0] - a[0]);
        List<Double> leftArrivals = mergeArrivalTimes(leftAnts, D, true);

        // Compute arrival times for right side
        // Sort ascending by pos (closest to D first => smallest pos first)
        rightAnts.sort((a,b) -> a[0] - b[0]);
        List<Double> rightArrivals = mergeArrivalTimes(rightAnts, D, false);

        // Merge arrival times into a single set
        // If the same time appears on both sides, that merges into one colony
        Set<Double> unified = new HashSet<>(leftArrivals);
        unified.addAll(rightArrivals);

        // The size of 'unified' is how many distinct arrival times => distinct colonies
        return unified.size() + totalGroups;
    }

    /**
     * For a side's ants, sorted so that we can apply the "car fleet" approach:
     * If the new arrival time is <= top of stack, merges. Otherwise push.
     *
     * isLeftSide = true => pos < D, traveling right => arrivalTime = (D - pos)/speed
     * isLeftSide = false => pos > D, traveling left => arrivalTime = (pos - D)/speed
     *
     * Returns a list of distinct arrival times for the side.
     */
    private static List<Double> mergeArrivalTimes(List<int[]> ants, int D, boolean isLeftSide) {
        List<Double> stack = new ArrayList<>();

        for (int[] ant : ants) {
            int pos = ant[0];
            int spd = ant[1];
            double arrival;
            if (isLeftSide) {
                // pos < D
                arrival = (double)(D - pos) / spd;
            } else {
                // pos > D
                arrival = (double)(pos - D) / spd;
            }

            // If arrival <= last stack entry => merges
            if (stack.isEmpty() || arrival > stack.get(stack.size() - 1)) {
                stack.add(arrival);
            }
            // else merges => do nothing
        }

        return stack;
    }

    // Example usage
    public static void main(String[] args) {
        // Example with ants on both sides of D=10
        // Positions:  2,  8, 12, 15
        // Speeds:     1,  2,  2,  1
        // => ants at 2 and 8 on the left side, ants at 12 and 15 on the right side
        int[] positions = {2, 8, 12, 15};
        int[] speeds    = {1, 2,  2,  1};
        int D = 10;

        int result = numberOfColoniesCrossSugar(positions, speeds, D);
        System.out.println("Number of colonies crossing sugar = " + result);
    }
}

Explanation

Partitioning by Side
- We gather all ants on the left (positions < DD) into leftAnts and all ants on the right (positions > DD) into rightAnts. Ants exactly at DD can be treated as an immediate single colony (or arrival time = 0).
Sorting
- Left side: Sort descending by position (largest position first).
- Right side: Sort ascending by position (smallest position first).
Merge Arrival Times
- The function mergeArrivalTimes uses the “car fleet” logic for each side:
  - We compute each ant’s arrival time to DD.
  - We maintain a stack (list) of final arrival times for distinct colonies.
  - If a new arrival time is less than or equal the top of the stack, it merges with that colony (no new entry).
  - Otherwise, it forms a new colony (append a new entry).
Unifying Both Sides
- After we get final arrival times for left side and right side, we unify them in a Set. If a time appears in both, that indicates the left colony and right colony arrive at DD simultaneously, forming one single colony at DD.
- The size of this set is the total number of distinct colonies crossing DD.
Handling Edge Cases
- If an ant is exactly at DD, it’s an immediate single colony. You could track that as arrivalTime = 0 or handle separately.
- If ants can have zero speed or negative speed, that’s a different scenario. Typically we assume positive speeds.

Complexity

Sorting each side is O(Nlog⁡N)O(N \log N) in the worst case.
The merging pass is O(N)O(N).
Overall complexity: O(Nlog⁡N)O(N \log N).

Pros and Cons of This Extended Approach

Pros:
- Handles ants on both sides of DD.
- Correctly merges arrival times if ants from opposite sides arrive simultaneously.
- Maintains the same O(Nlog⁡N)O(N \log N) time complexity.
Cons:
- Slightly more code to handle partitioning and unify final arrival times.
- If ants can pass DD or have more complex interactions (like turning around), more logic is needed.

With this updated approach, the code can handle the scenario where DD is between the ant positions—some ants on the left, some on the right—and unify them if they arrive at DD at exactly the same time.

NextHoliday

Last updated 4 months ago