SDE - Intern

Generate All Subsequences: Since n≤20, there are 2n possible subsequences (220≈106). This is small enough to brute force.
Filter and Convert: Iterate through all 2n−1 bitmasks. For each mask, construct the binary string, convert it to a decimal integer, and store it in a set to handle duplicates.
Primality Test: Sort the unique integers in descending order. Use a primality test (like a pre-computed Sieve of Eratosthenes up to 220 or a simple N​ check) on each number.
Result: The first (largest) number that passes the primality test is your answer.

Feasibility Check: Count total 'b's in s. If total 'b's 
Greedy Construction: Build the result string character by character while maintaining the two constraints:
We need k characters total.
We need at least x 'b's.
The Strategy: Use a monotonic-like approach. We prefer 'a' over 'b' at any position unless taking an 'a' prevents us from meeting the x 'b's requirement or the k length requirement later.
Suffix Counting: Pre-calculate suffix_b[i], the number of 'b's from index i to n−1.
Iteration: As you iterate through s, pick 'a' if:
(Current 'b' count) + (remaining 'b's in s after this index) ≥x.
You still have enough characters left in s to reach length k.
Otherwise, you may be forced to pick 'b' or skip the character.

Graph Representation: Treat each free cell . as a node and adjacent free cells as edges with weight 1.
Algorithm (BFS): Since all edge weights are equal (1 minute), Breadth-First Search (BFS) is the optimal and simplest algorithm.
Initialize a 2D dist array with ∞. Set dist[x1][y1] = 0.
Push (x1,y1) into a queue.
Traversal: While the queue is not empty:
Pop the current cell (currX,currY).
Check all 4 neighbors (Up, Down, Left, Right).
If a neighbor is within bounds, is a ., and dist[neighbor] is still ∞:
Update dist[neighbor] = dist[currX][currY] + 1.
Push neighbor to the queue.
Termination: If you reach (x2,y2), return dist[x2][y2]. If the queue empties and you haven't reached the target, the destination is unreachable.

Define the Recursive Function
Define a function solve(u, p) that returns the maximum path sum starting at node u and extending downwards into its subtree.
ans (global/static): Keeps track of the overall maximum path sum found so far.
Step 2: Calculate the Downward Path
For a node u, calculate the max path sum from its children v1​,v2​,...vk​:
gain(vi​)=max(0,solve(vi​,u))
We use max(0,…) because if a subtree's maximum path sum is negative, it's better not to include it in a path passing through u.
Step 3: Update the Global Maximum
The maximum path sum that has node u as its "highest" point (the curved peak of the path) is:
Current Path Sum=arr[u]+∑top two gain(vi​)
Update ans = max(ans, Current Path Sum).
Step 4: Return for Parent
The function should return the maximum sum of a path starting at u and going down one branch:
return arr[u]+max(gain(vi​))

To reverse the list in-place, you need to keep track of three nodes at any given time:
prev: The node that will become the new next.
curr: The node we are currently re-linking.
next_node: A temporary pointer to "save" the rest of the list before we break the connection.
Initialize: * Set prev = NULL.
Set curr = head.
Iterate: While curr is not NULL:
Save: Store the next node: next_node = curr->next.
Reverse: Point the current node back to the previous: curr->next = prev.
Move: Shift the pointers forward for the next iteration:
prev = curr
curr = next_node
Finalize: After the loop, prev will be pointing to the new head of the reversed list. Return prev.

How to Solve in Steps
Count Frequencies: Use a frequency map or an array to count the occurrences of each color. Let these counts be c1​,c2​,…,ck​.
Identify the Operation: You can pick all balls of color A and turn them into color B. This effectively merges the two counts: cnew​=cA​+cB​.
Maximize the Denominator: To minimize the total arrangements, you want to merge the two counts that, when combined, create the largest possible product of factorials in the denominator.
Mathematically, replacing ni​!⋅nj​! with (ni​+nj​)! always increases the denominator because (ni​+nj​)!>ni​!⋅nj​! for any ni​,nj​≥1.
Pick the Best Merge: To get the absolute minimum, you should merge the two largest existing counts.
Correction/Refinement: Actually, since (ni​+nj​)! grows super-linearly, merging any two colors will reduce the total count, but merging the two largest groups results in the largest possible denominator.
Calculate with Modular Inverse: Since we need the answer modulo 109+7, use Fermat's Little Theorem to calculate the modular multiplicative inverse for the division.