To maximize the minimum frequency of a character, it's best to equalize the frequencies of each character as much as possible. So, each set of $$$k$$$ characters should have a frequency of at least $$$n$$$ // $$$k$$$. Then, we can distribute the remaining $$$n$$$ % $$$k$$$ characters however we want among those $$$k$$$ characters.

t = int(input())
for _ in range(t):
    n,k = input()
    
    numbers = n // k
    
    remaining = n % k
    
    ans = ""
    
    for i in range(k):
        ans += chr(i + ord("a")) * numbers
    ans += "a" * remaining
    print(ans)

We can easily add a friend to the display system when that friend goes online. When there is a query to check if a friend can be displayed by the system, we need to remove friends with the lowest goodness values until the size of the online friends list is less than or equal to $$$k$$$. The answer will be $$$YES$$$ if the friend exists in the displayed system. If the friend is not currently in the display system, either because they were never added or because they were removed from the list, the answer will be $$$NO$$$.

Time Complexity: $$$(O(q * log(n)))$$$ where $$$q$$$ is number of queries and $$$n$$$ is number of friends Space Complexity: $$$O(n)$$$

from heapq import heappop, heappush
from collections import defaultdict

def main():
    n, k, q = map(int, input().split())
    friendship = list(map(int, input().split()))
    hashMap = defaultdict(int)
    heap = []

    for _ in range(q):
        type, friend = map(int, input().split())
        if type == 1:
            hashMap[friend] = 2
            heappush(heap, (friendship[friend - 1], friend))
        else:
            if hashMap[friend]:
                while len(heap) > k:
                    weight, f = heappop(heap)
                    hashMap[f] = 1 
            if hashMap[friend] == 2:
                print('YES') 
            else:
                print('NO')
    
if __name__ == '__main__':
    main()
 
 

The order in which they will be applied is not important.

To solve it, it should be noted that despite the way the deck with bonuses works, the order in which they will be applied is not important. Then, when we meet the hero card, we just need to add to the answer the maximum of the available bonuses.

Constraints make you use data structures such as $$$heap$$$ to quickly find and extract the maximum.

Total complexity: $$$O(nlogn)$$$

import sys
from heapq import heappush, heappop

t = int(sys.stdin.readline().strip())

for _ in range(t):
    
    n =  int(sys.stdin.readline().strip())
    nums = list(map(int, sys.stdin.readline().strip().split()))
    my_heap = []
    ans = 0
    for num in nums:
        if num:
            heappush(my_heap, -1 * num)
        else:
            if my_heap:
                ans +=( heappop(my_heap) * -1)
    print(ans)

Consider an $$$N$$$-vertex directed graph where for each $$$i$$$ $$$(1 \leq i \leq M)$$$, there is an edge from vertex $$$a_i$$$ to vertex $$$b_i$$$. The goal is to find the lexicographically smallest sequence of topologically sorted vertices.

Topological sorting can be applied to the directed graph we have built. By choosing the vertex with the smallest index and indegree 0 at each step, we obtain the lexicographically smallest sequence $$$S$$$.

To choose the vertex with the smallest index and indegree, we can use a heap data structure.

import heapq

N, M = map(int, input().split())
indeg = [0] * N
out = [[] for _ in range(N)]
for _ in range(M):
a, b = map(int, input().split())
	a -= 1
	b -= 1
	indeg[b] += 1
	out[a].append(b)

heap = []
for i in range(N):
	if indeg[i] == 0:
    		heapq.heappush(heap, i)

ans = []
while heap:
	i = heapq.heappop(heap)
	ans.append(i)
	for j in out[i]:
    		indeg[j] -= 1
    		if indeg[j] == 0:
        			heapq.heappush(heap, j)

if len(ans) != N:
	print(-1)
else:
	print(*[x + 1 for x in ans])

When do we print $$$NO$$$?

If we can't form a valid topological order of the vertices by using only the directed edges, the answer is $$$NO$$$.

If the graph consisting of the vertices and only directed edges contains at least one cycle then the answer is $$$NO$$$. In other words, If we can’t form a valid topological order of the vertices with just the directed edges, we print $$$NO$$$.

Let’s now have the topological sort of the graph without undirected edges. For each pair of vertices $$$X, Y$$$ in the undirected edges, if $$$X$$$ comes before $$$Y$$$ in the topological order, we direct the edge from $$$X$$$ to $$$Y$$$, otherwise we direct it from $$$Y$$$ to $$$X$$$.

from collections import deque, defaultdict


def topSort(graph, indegree):
    queue = deque()

    for node in range(n):
        if not indegree[node]:
            queue.append(node)

    top_order = []

    while queue:
        cur = queue.popleft()
        top_order.append(cur)

        for neigh in graph[cur]:
            indegree[neigh] -= 1

            if not indegree[neigh]:
                queue.append(neigh)
    
    return top_order


t = int(input())

for _ in range(t):
    n, m = map(int, input().split())

    directed = []
    undirected = []
    
    for i in range(m):
        direction, x, y = map(int, input().split())

        x -= 1 # let's make it zero indexed
        y -= 1

        if direction:
            directed.append((x, y))
        
        else:
            undirected.append((x, y))
    

    graph = [[] for node in range(n)]
    indegree = defaultdict(int)

    for x, y in directed:
        graph[x].append(y)
        indegree[y] += 1
    

    order= topSort(graph, indegree)

    if len(order) < n:
        print("NO")
    
    else:
        # compute the index of each node in the topological order
        temp = {node: idx for idx, node in enumerate(order)}


        print('YES')
        for x, y in undirected:
            if temp[x] < temp[y]:
                print(x + 1, y + 1)
                
            else:
                print(y + 1, x + 1)

        for x, y in directed:
            print(x + 1, y + 1)