On a daily basis you are broker facilitating buy and sell of stocks for different hedge funds to support their trading strategies. As a result you are required to manage the stock movements across different accounts.

Primary function is to deliver stocks to the clients based on their needs, any excess stocks that is present can be pledged in "triparty" accounts to be able to raise cash which can be used for client requirements.

Each movement of stock between accounts has a transaction cost associated with it. Lesser the number of movements lesser is the transaction cost. Additionaly, each account belongs to a parent account. Aggregated transaction cost of the movement within the accounts of same parent account is always less than the transaction cost of the movement between accounts of different parent account, and hence should be always prefered. Another way to put this is cost of any number of transactions within the accounts of single parent account is less than cost of single transaction between 2 accounts that belong to different parent entity

Given the daily trading activity, device an alogirthm that will be able to effectively use the stocks to make sure the client demands are met on priority and maximizing the cash value of the asset, with minimum transaction cost possible. (Each row in the output is a transaction/movement.)

Input Format

First line is the number of stocks(n) and the next (n) lines are of format (stock Id,price) where stock Id is the stock identifier(string) and price is the stock price in $USD.

2

P1,2.5

P2,1.25

Post above lines, you are given the number of accounts between which stocks can be transferred(n) and the next (n) lines are of format (account Id,account type,parent account) where account Id is the account identifier(string), account type is the reference data indicating if it is a custody account(CUSTODY) or a triparty account(TRIPARTY) which will give cash in exchange of excess stocks, the third number parent account will represent the parent account representing which parent account does the account belong to.

3

Loc1,CUSTODY,1

Loc2,CUSTODY,2

Loc3,TRIPARTY,2

Post above lines, you are given number of lines(n) to read for eligible accounts per stock(indicating in which account can a particular stock be held), followed by (n) lines of format (stock Id, account Id), a stock will have multiple eligible accounts therefore multiple rows for a stock.

6

P1,Loc1

P1,Loc2

P1,Loc3

P2,Loc1

P2,Loc2

P2,Loc3

Post above lines, you are given number of lines(n) to read for eligible flows(directed) per stock(indicating the movement between the accounts that is allowed for a stock), followed by (n) lines of format (stock Id, source account Id, destination account Id), which indicates the stock(stock Id) can move from source account Id to destination account Id, a stock will have multiple eligible flows therefore multiple rows for a stock.

7

P1,Loc1,Loc2

P1,Loc1,Loc3

P1,Loc2,Loc1

P1,Loc2,Loc3

P2,Loc1,Loc2

P2,Loc2,Loc3

P2,Loc3,Loc1

Post above lines, you are given number of lines(n) to read for balances of each stock per account followed by (n) lines of format (stock Id, account Id, quantity), representing the stock stock Id currently has quantity number of shares in account account Id, if quantity positive number, it indicates that you have the stock excess and negative number is the demand of that stock that needs to be fulfilled.

3

P1,Loc1,10

P1,Loc2,-5

P2,Loc1,5

Constraints

all recommended quantity should be positive numbers only

Output Format

Output should be in the format (stock Id,source acccount Id,destination account Id,quantity) representing we need to move quantity shares of stock Id from account source account Id to destination account Id. The output rows should be sorted in ascending order of Stock Id, then source account Id, and destination account Id at last where each Id is a String.

P1,Loc1,Loc2,5

P1,Loc1,Loc3,5

P2,Loc1,Loc2,5

P2,Loc2,Loc3,5

Sample Input 0

2 
P1,2.5
P2,1.25
3 
Loc1,CUSTODY,1
Loc2,CUSTODY,2
Loc3,TRIPARTY,2
6
P1,Loc1
P1,Loc2
P1,Loc3
P2,Loc1
P2,Loc2
P2,Loc3
7
P1,Loc1,Loc2
P1,Loc1,Loc3
P1,Loc2,Loc1
P1,Loc2,Loc3
P2,Loc1,Loc2
P2,Loc2,Loc3
P2,Loc3,Loc1
3
P1,Loc1,10 
P1,Loc2,-5 
P2,Loc1,5

Sample Output 0

P1,Loc1,Loc2,5
P1,Loc1,Loc3,5
P2,Loc1,Loc2,5
P2,Loc2,Loc3,5

Below code fails in some cases fix it
# Read stocks
n_stocks = int(input_lines[idx]); idx +=1
stock_prices = {}
for _ in range(n_stocks):
    parts = input_lines[idx].split(',')
    stock_id = parts[0].strip()
    price = float(parts[1].strip())
    stock_prices[stock_id] = price
    idx +=1

# Read accounts
n_accounts = int(input_lines[idx]); idx +=1
accounts = {}
parent_accounts = {}
account_types = {}
for _ in range(n_accounts):
    parts = input_lines[idx].split(',')
    acc_id = parts[0].strip()
    acc_type = parts[1].strip()
    parent = parts[2].strip()
    accounts[acc_id] = {'type': acc_type, 'parent': parent}
    parent_accounts[acc_id] = parent
    account_types[acc_id] = acc_type
    idx +=1

# Read eligible accounts per stock
n_eligible_accounts = int(input_lines[idx]); idx +=1
stock_eligible_accounts = defaultdict(set)
for _ in range(n_eligible_accounts):
    parts = input_lines[idx].split(',')
    stock_id = parts[0].strip()
    acc_id = parts[1].strip()
    stock_eligible_accounts[stock_id].add(acc_id)
    idx +=1

# Read eligible flows per stock
n_flows = int(input_lines[idx]); idx +=1
stock_flows = defaultdict(list)
for _ in range(n_flows):
    parts = input_lines[idx].split(',')
    stock_id = parts[0].strip()
    src = parts[1].strip()
    dst = parts[2].strip()
    stock_flows[stock_id].append( (src, dst) )
    idx +=1

# Read balances
n_balances = int(input_lines[idx]); idx +=1
stock_balances = defaultdict(lambda: defaultdict(int))
for _ in range(n_balances):
    parts = input_lines[idx].split(',')
    stock_id = parts[0].strip()
    acc_id = parts[1].strip()
    quantity = int(parts[2].strip())
    stock_balances[stock_id][acc_id] = quantity
    idx +=1

movements = defaultdict(int)  # key: (stock_id, src, dst), value: qty

for stock_id in stock_prices:
    eligible_accounts = stock_eligible_accounts[stock_id]
    flows = stock_flows[stock_id]

    # Build adjacency list
    adj = defaultdict(list)
    for src, dst in flows:
        adj[src].append(dst)

    # Identify excess and demand
    excess = {}
    demand = {}
    for acc in eligible_accounts:
        qty = stock_balances[stock_id].get(acc,0)
        if qty >0:
            excess[acc] = qty
        elif qty <0:
            demand[acc] = -qty

    # Function to find path using BFS with preference to same parent
    def find_path(src, dst):
        queue = deque()
        queue.append((src, [src]))
        visited = set()
        visited.add(src)
        while queue:
            current, path = queue.popleft()
            if current == dst:
                return path
            for neighbor in adj[current]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, path + [neighbor]))
        return None  # No path found

    # Fulfill demands
    for d_acc, d_qty in demand.items():
        # Find all possible surplus accounts that can reach d_acc
        possible_sources = []
        for s_acc, s_qty in excess.items():
            path = find_path(s_acc, d_acc)
            if path:
                # Calculate inter-parent transitions
                inter_parent = 0
                for i in range(len(path)-1):
                    if parent_accounts[path[i]] != parent_accounts[path[i+1]]:
                        inter_parent +=1
                possible_sources.append( (inter_parent, len(path), s_acc, path) )
        # Sort sources by least inter_parent, then shortest path
        possible_sources.sort()
        needed = d_qty
        for inter_parent, path_length, s_acc, path in possible_sources:
            if needed ==0:
                break
            available = excess[s_acc]
            move_qty = min(available, needed)
            # Record movement steps
            for i in range(len(path)-1):
                src = path[i]
                dst = path[i+1]
                movements[(stock_id, src, dst)] += move_qty
            # Update surplus and demand
            excess[s_acc] -= move_qty
            needed -= move_qty
            if excess[s_acc] ==0:
                del excess[s_acc]
        if needed >0:
            # Cannot fulfill demand fully; depending on requirements, handle accordingly
            # For this problem, we assume demands can be fully fulfilled
            pass

    # Handle remaining excess by moving to TRIPARTY accounts
    triparty_accounts = [acc for acc in eligible_accounts if account_types[acc]=='TRIPARTY']
    if triparty_accounts:
        for s_acc, s_qty in list(excess.items()):
            if s_qty <=0:
                continue
            # Find paths to any triparty account
            possible_paths = []
            for t_acc in triparty_accounts:
                path = find_path(s_acc, t_acc)
                if path:
                    # Calculate inter-parent transitions
                    inter_parent = 0
                    for i in range(len(path)-1):
                        if parent_accounts[path[i]] != parent_accounts[path[i+1]]:
                            inter_parent +=1
                    possible_paths.append( (inter_parent, len(path), t_acc, path) )
            if possible_paths:
                # Choose the path with least inter_parent transitions and shortest path
                possible_paths.sort()
                _, _, chosen_t_acc, chosen_path = possible_paths[0]
                move_qty = s_qty
                for i in range(len(chosen_path)-1):
                    src = chosen_path[i]
                    dst = chosen_path[i+1]
                    movements[(stock_id, src, dst)] += move_qty
                # Update excess
                excess[s_acc] -= move_qty
                if excess[s_acc] ==0:
                    del excess[s_acc]
            else:
                # No path to any triparty account; handle accordingly (ignored for this problem)
                pass

# Prepare and sort movements
final_movements = []
for (stock_id, src, dst), qty in movements.items():
    if qty >0:
        final_movements.append( (stock_id, src, dst, qty) )

# Sort by stock_id, src_account, dst_account
final_movements.sort(key=lambda x: (x[0], x[1], x[2]))

# Print movements
for move in final_movements:
    print(','.join([move[0], move[1], move[2], str(move[3])]))