If we have $$$n$$$ distinct balloons, first we have $$$n$$$ choices to burst, then $$$n - 1$$$ and so on. Hence, totally we have $$$n!$$$ ways to burst the balloons.

from math import factorial


N = int(input())

distinct_balloons = set(map(int, input().split()))

n = len(distinct_balloons)
print(factorial(n))

Since there is frequent removal and insertion, a linked list (a doubly linked one) is a good fit for the solution. To keep track of the first occurrences of the numbers we can utilize a hashmap with queues as values.

For insertion, the hashmap will tell us which node is the first occurrence of $$$y$$$, with a key, $$$y$$$; and a value, the occurrences of $$$y$$$ (nodes with value == $$$y$$$) in a queue. If we get the instance of the first $$$y$$$, it will be as easy as manipulating pointers of the linked list.

For removal, it is the same process, we get the first occurrence from the hashmap and remove it from the linked list as well as the queue.

import sys
from collections import defaultdict, deque

class ListNode:
    def __init__(self, val, prev=None, next=None):
        self.val = val
        self.next = next
        self.prev = prev

q = int(input())
queries = [input().split() for i in range(q)]

head = ListNode(None) # dummy node
tail = ListNode(None, prev=head) # dummy node
head.next = tail

positions = defaultdict(lambda :deque())

for query in queries:
    operation = query[0]
    if operation == 'insert':
        x, y = map(int, query[1:])
        new_x = ListNode(x)
        if positions[y]:
            first_y = positions[y][0]
            temp = first_y.next
            new_x.prev = first_y
            new_x.next = temp
            first_y.next = new_x
            temp.prev = new_x
            positions[x].append(new_x)
        else:
            temp = tail.prev
            temp.next = new_x
            tail.prev = new_x
            new_x.next = tail
            new_x.prev = temp
            positions[x].append(new_x)
    
    else:
        w = int(query[1])
        if positions[w]:
            target = positions[w].popleft()
            prev = target.prev
            nxt = target.next
            prev.next = nxt
            nxt.prev = prev

ans = []
current = head.next
while current.val != None:
    ans.append(current.val)
    current = current.next

print(*ans)

The problem can be solved using dynamic programming (DP). The key idea is to use a DP table to keep track of the maximum points Sam can achieve after processing each tree. Let dp[i][j] represent the maximum points Sam can achieve after processing the first i trees, with exactly j half picks made so far. The DP table is initialized to zero because starting at tree 0 gives Sam 0 points.

If Sam picks all the fruits from the current tree $$$i$$$, then the points accumulated will be: $$$dp[i][0]=dp[i−1][0]+(produce[i−1]−k)$$$

If Sam chooses to half-pick the fruits at tree i, then the points will be influenced by the number of previous half-picks j. We have two subcases:

Don't Divide: This continues from the previous state without making an additional half-pick.

Divide: This adds one more half-pick at the current tree.

The transition can be defined as: $$$dp[i][j]=max⁡(dp[i−1][j]+floor(produce[i−1]/2j)−k,dp[i−1][j−1]+floor(produce[i−1]/2j))$$$

$$$dp[i][j]=max(dp[i−1][j]+floor(produce[i−1]/2j)−k,dp[i−1][j−1]+floor(produce[i−1]/2j))$$$

The final result is the maximum value from the last row and column of the DP table after processing all the trees, considering all possible numbers of half-picks.

test_case = int(input())
for _ in range(test_case):
   n,k =  list(map(int,input().split()))
   nums = list(map(int,input().split()))
   dp = [[0 for _ in range(15)] for _ in range(n+1)]
  
  
   for i in range(1,n+1):
       dp[i][0] = dp[i-1][0]+ nums[i-1]- k
  
  
       for j in range(1,min(15,i+1)):
  
  
           dont_div = (dp[i-1][j]+ (nums[i-1]//(2**j))-k)
           div = (dp[i-1][j-1] + nums[i-1]//(2**j))
           dp[i][j] = max(dont_div,div)
  
  
   print(max(dp[n] + [i[-1] for i in dp]))

The goal of this solution is to find the maximum possible value using the aforementioned operation by simulating the tree in reverse order (starting from the leaf nodes to the root). Then, we can return the summation of the possible maximum value and the initial value at the root node as the answer.

We will perform a topological sort starting from the leaf nodes and moving towards the root node. During this process, we update the values of the nodes based on their children's values. This means: For each leaf node, we return the initial given value. For any non-leaf node, once we get the minimum value out of the children of the given non-leaf node, called $$$min_val$$$, we update the value of that non-leaf node based on two conditions: If the $$$min_val$$$ is less than the value of the current non-leaf node, the value of the current non-leaf node should be updated to $$$min_val$$$. If the $$$min_val$$$ is greater than or equal to the value of the current non-leaf node, then the value of the current non-leaf node should be updated to the average of the current node's value and $$$min_val$$$ (it should be rounded to the smallest nearest whole number). This will guarantee that we are performing the operations as much as possible without having any negative nodes. Once we reach the root node, we stop further processing as we've obtained the final possible value for the root. Then the final answer is the sum of the initial value of the root node and the final computed value for the root node after processing.

from collections import defaultdict, deque

for _ in range(int(input())):
    n = int(input())
    vals = list(map(int, input().split()))
    min_vals = [float('inf')] * n
    graph = defaultdict(list)
    indegree  = [0] * n
    # assigning the initial value of the root node as initial answer
    initial_ans = vals[0]
    vals[0] = float('inf')
    
    for i, each in enumerate(map(int, input().split())):
        graph[i + 1].append(each - 1)
        indegree[each - 1] += 1

    # including all leaf nodes as a source node
    queue = deque()
    for i in range(n):
        if indegree[i] == 0:
            queue.append((i, vals[i]))

    # calculating the maximum possible value written at the root using the aforementioned operation
    while queue:
        node, val = queue.popleft()
        if node == 0:
            break
        for neib in graph[node]:
            indegree[neib] -= 1 
            min_vals[neib] = min(min_vals[neib], val)
        
            if indegree[neib] == 0:
                if neib == 0:
                    vals[neib] = min(vals[neib], min_vals[neib]) 
                else:
                    if min_vals[neib] < vals[neib]:
                        vals[neib] = min_vals[neib]
                    else:
                        vals[neib] = (vals[neib] + min_vals[neib]) // 2
                queue.append((neib, vals[neib]))

    print(initial_ans + vals[0])

This problem is about the "rerooting" technique. Firstly, let's calculate the answer for some fixed root. How can we do this? Let $$$dp_v$$$ be the maximum possible difference between the number of white and black vertices in some subtree of $$$v$$$ (yes, the subtree of the rooted tree, i.e. $$$v$$$ and all its direct and indirect children) that contains the vertex $$$v$$$. We can calculate this dynamic programming by simple $$$dfs$$$ or $$$bfs$$$, for the vertex $$$v$$$ it will look like this: $$$dp_v=a_v+ \sum_{\text{to} \in \text{children}(v)} \max(0, dp_{to})$$$.

Okay, we can store the answer for the root somewhere. What's next? Let's try to change the root from the vertex $$$v$$$ to some adjacent to it vertex to. Which states of dynamic programming will change? Only $$$dp_v$$$ and $$$dp_{to}$$$. Firstly, we need to "remove" the child to from the subtree of the vertex $$$v$$$: $$$dp_v=dp_v−max(0,dp_{to})$$$. Then we need to "attach" the vertex $$$v$$$ and make it a child of the vertex to: $$$dp_{to}=dp_{to}+max(0,dp_v)$$$. Then we need to run this process recursively from to (store the answer, reroot the tree and so on) and when it ends we need to "rollback" our changes. Now $$$v$$$ is the root again and we can try the next child of $$$v$$$ as the root.

Time complexity: O(n).

import sys
from collections import defaultdict, deque
   
n = int(sys.stdin.readline().strip())
dp = list(map(int, sys.stdin.readline().strip().split()))

for i in range(n):
    if dp[i] == 0:
        dp[i] = -1

graph = defaultdict(list)
for _ in range(n - 1):
    u, v  = map(int, sys.stdin.readline().strip().split())
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)

queue = deque()
queue.append((0, -1))
i = 0

while i < len(queue):
    le =  len(queue)
    for _ in range(i, le):
        cur, par = queue[i]
        i += 1
        for ne in graph[cur]:
            if ne != par:
                queue.append((ne, cur))

for i in range(len(queue) -1,0, -1):
    dp[queue[i][1]] += max(0, dp[queue[i][0]])

queue = [(0, -1)]
while queue:
    le = len(queue)
    for _ in range(le):
        cur, par = queue.pop()
        for ne in graph[cur]:
            if ne != par:
                dp[ne] += max(0, dp[cur]  - max(0, dp[ne]))
                queue.append((ne, cur))
print(*dp)