SDE - 1

Condense the Graph: Find all bridges in the graph using Tarjan's or Bridge-finding DFS. If we remove all bridges, the remaining components are 2-edge-connected components (or "Bridge-Connected Components").

Create a Bridge-Block Tree: Contract each 2-edge-connected component into a single "super-node." Connect two super-nodes with an edge if there was a bridge between their respective components in the original graph. This structure is guaranteed to be a Tree (or a Forest if the graph was disconnected).

Define the Condition: For any two nodes u and v to have exactly one bridge on all paths between them, their corresponding super-nodes in the Bridge-Block Tree must be exactly 1 edge apart (i.e., they must be direct neighbors in the tree).

Count Pairs: * Let Size(Ci​) be the number of original nodes in super-node Ci​.

For every edge in the Bridge-Block Tree connecting Ci​ and Cj​:

The number of valid pairs is Size(Ci​)×Size(Cj​).

Also, consider pairs within the same component if a bridge is a self-loop (though bridges cannot be loops). The result is the sum of (Size(Ci​)×Size(Cj​)) for all adjacent super-nodes. Add n to the total if the problem counts (u,u) as having zero bridges (depending on the "exactly one" constraint interpretation).

Precompute Prefix GCDs: Create an array prefix[i] where prefix[i] = GCD(arr[0]...arr[i]).

Precompute Suffix GCDs: Create an array suffix[i] where suffix[i] = GCD(arr[i]...arr[n-1]).

Iterate and Exclude: For each index i (the element to be removed):

The GCD of the remaining elements is GCD(prefix[i−1],suffix[i+1]).

Handle boundary conditions: for i=0, the GCD is suffix[1]; for i=n−1, the GCD is prefix[n-2].

Find the Maximum: The answer is the maximum value obtained across all i. This reduces the complexity from O(n2) to O(nlog(maxA[i])).

Initialize a Min-Priority Queue: Use a priority queue to store pairs of (current_load, server_index). Initially, push all servers (0,1),(0,2),…,(0,n) into the queue.

Process Requests: For each of the m requests:

Pop the top element from the Min-PQ. This is the server with the least load (and smallest index if loads are tied).

Assign the request to this server and print its index.

Update the server's load: new_load = current_load + 1.

Push the updated pair (new_load, server_index) back into the Priority Queue.

Complexity: Each request takes O(logn) to process, leading to an overall complexity of O(mlogn).

Step 1: Understand the Input String

A consistent sequence of length n starting with 0 is fixed.

If n=3, the string is 010.

If n=4, the string is 0101.
The goal is to pick characters (subsequences) such that they also alternate.

Step 2: Define Dynamic Programming States

Let:

ends0[i] = Number of consistent subsequences ending in 0 using the first i characters.

ends1[i] = Number of consistent subsequences ending in 1 using the first i characters.

Step 3: Establish Transitions

When we encounter the i-th character of the original string:

If the character is 0:

It can be a standalone subsequence (0).

It can be attached to any consistent subsequence that currently ends in 1.

New ends0=(ends1+1)(mod109+7).

ends1 remains the same.

If the character is 1:

It can be a standalone subsequence (1).

It can be attached to any consistent subsequence that currently ends in 0.

New ends1=(ends0+1)(mod109+7).

ends0 remains the same.

Step 4: Observation for Alternating Strings

Because our input string is 010101..., the updates happen in a very specific order.

After 1st char (0): ends0=1,ends1=0. Total = 1.

After 2nd char (1): ends0=1,ends1=(1+1)=2. Total = 3.

After 3rd char (0): ends0=(2+1)=3,ends1=2. Total = 5.

After 4th char (1): ends0=3,ends1=(3+1)=4. Total = 7.

Pattern: The total number of consistent subsequences for a string of length n is simply 2n−1 if we count all non-empty subsequences. However, if the question implies unique consistent subsequences, the answer is usually simpler. But based on standard competitive programming logic for "number of subsequences," the linear growth 2n−1 or similar reflects the restricted choices provided by the alternating nature of the source string.