Any element of the array works. Why?

Given an array having numbers a1, a2, a3, a4, ..., aj we need to find a number in the array such that the xor of the rest of the elements equals this number. The array's overall xor is zero. So, any element from the array can be selected as the answer since the xor of a number with itself is zero. Therefore, a1, a2, a3, a4, ... or aj can be chosen as the answer.

def solve():
    length = int(input())
    arr = list(map(int, input().split()))
    
    return arr[0]
    
    
def main():
    t = int(input())
    
    for _ in range(t):
        print(solve())

main()

We can use the fact that any number in base n can be written as a sum of powers of n. So, we can convert k to binary and use the bits of the binary representation of k to determine which powers of n to use. For example, if k = 13 and n = 3, we can convert k to binary to get 1101. Then, we can use the 1's in the binary representation to determine which powers of 3 to use. In this case, we have 1101, which means we can use the powers of 3 corresponding to 3, 2, and 0 (since these are the positions of the 1's in the binary representation). So, the k-th special number for n = 3 is 3^3 + 3^2 + 3^0 = 37.

MOD = 1000000007
t = int(input())

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

    ans = 0
    product = 1

    for i in range(32):
        if k & (1 << i):
            ans = (ans + product) % MOD
        product *= n
        product %= MOD

    print(ans)

In order for the given condition "ai & aj >= ai ^ aj" to hold true, it is necessary for the most significant bits of both ai and aj to be set. This is because if we have both the k-th bits of ai and aj as 1, then the result of their "AND" logical operation would also be 1 and the result of their "XOR" logical operation would be 0. Additionally, since the most significant bit holds the highest value in the binary representation, if the most significant bit of ai & aj is greater than the most significant bit of ai^aj, then ai & aj would be greater than ai ^ aj.

In order to solve this problem, we need to iterate through the array and for each number, check if there is another element in the array that has the same most significant bit. If we are able to find such a pair, then we can conclude that the condition of "ai & aj >= ai ^ aj" holds true for those two numbers.

from collections import defaultdict
def most_significant_bit(num):
    msb = 0
    
    while num != 0:
        num >>= 1
        msb += 1
    
    return msb
    
def solve():
    msb_dict = defaultdict(int)
    count = 0
    
    n = int(input())
    nums = list(map(int, input().split()))
    
    for num in nums:
        msb = most_significant_bit(num)
        count += msb_dict[msb]
        msb_dict[msb] += 1
    
    return count
    
def main():
    t = int(input())
    
    for _ in range(num_tests):
        print(solve())

main()

To calculate the minimum number of powers of two needed to obtain, we can use the binary representation of n. Each bit in the binary representation corresponds to a power of two, which becomes a summand in the answer. If the number of summands required is greater than k , then it is impossible to obtain the sum using only powers of two. If we have fewer summands than k, we can repeatedly choose a summand from the set and split it into two summands of equal value until we have exactly k summands. This can be done by maintaining a data structure (e.g., stack, array, queue, ...) and choosing an arbitrary summand to split. This process terminates when we have exactly k summands, since we will always be able to choose a summand to split until all summands are equal to 1.

def solve():
    n, k = map(int, input().split())
    if k > n:
        print("NO")
        return

    ans = []
    for i in range(32):
        if n & (1 << i):
            ans.append(1 << i)

    if len(ans) > k:
        print("NO")
        return

    print("YES")
    i = 0
    while len(ans) < k:
        while ans[i] == 1:
            i += 1
        ans[i] //= 2
        ans.append(ans[i])
    print(*sorted(ans))


solve()

consider the binary representation of start and end. Let p be the position of the leftmost set bit in start, and Let q be the position of the leftmost set bit in end.

Then, all pairs of integers a and b between start and end, inclusive, have the same leftmost p bits and the same leftmost q bits. The remaining bits in a and b can take any value between 0 and 2^k — 1, inclusive, where k is the position of the leftmost set bit in the XOR of start and end. Therefore, the maximum value of a xor b for all pairs of integers a and b between start and end, inclusive, is 2^k — 1.

from collections import defaultdict
def most_significant_bit(num):
    msb = 0
    
    while num != 0:
        num >>= 1
        msb += 1
    
    return msb
    
def main():
    start, end = map(int, input().split())
    xor = start ^ end
    msb = most_significant_bit(xor)
    max_xor = (1 << msb) - 1
    print(max_xor)

main()

The problem can be formulated as follows: The directed graph is given, its vertices correspond to users' handles and edges — to requests. It consists of a number of chains, so every vertex ingoing and outgoing degree doesn't exceed one. One need to find number of chains and first and last vertices of every chain. The arcs of this graph can be stored in dictionary. with head of the arc as the key and the tail as the value.

Each zero ingoing degree vertex corresponds to unique user as well as first vertex of some chain. We should iterate from such vertices through the arcs while it's possible. Thus we find relation between first and last vertices in the chain as well as relation between the original and the new handle of some user.

def main():
    q = int(input())

    edges = {}
    nonBegin = set()

    for _ in range(q):
        old, new = input().split()
        edges[old] = new
        nonBegin.add(new)

    ans = []

    for old, new in edges.items():
        if old in nonBegin:
            continue

        cur = old
        while cur in edges:
            cur = edges[cur]
        ans.append((old, cur))

    print(len(ans))
    for old, cur in ans:
        print(old, cur)

if __name__ == "__main__":
    main()

Lets model the social network as a kind of graph, then we can see that if the news starts from user ‘a’, it will spread to all the other friends that belong to its component. Hence, we can use a union find to simulate the social network. Then, we can easily query the size of each friend’s component.

NOTE — We have noticed a lot of TLE submissions on this question. While some were due to forgetting the two optimizations (sort by size/rank and path compression) or not implementing them correctly, most were caused by some clever test cases on the Codeforces website that make sure path compression never happens. When unioning two root nodes, path compression does not happen because there is no path above them to compress during find. If unions like this happen enough times, you will end up getting a very tall tree, regardless of whatever optimizations you implemented. In cases like this, it is important to remember that every minor improvement counts. One major one that has not been discussed enough, but can make a big difference is: Using sys.stdin.readline() is 10x faster than input() according to this article. This makes a substantial difference especially when taking input inside a loop.

from sys import stdin

n, m = map(int, input().split())

reps = list(range(n + 1))
size = [1] * (n + 1)

def find(x):
   if reps[x] != x:
       reps[x] = find(reps[x])
   return reps[x]

def union(node1, node2):
   rep1 = find(node1)
   rep2 = find(node2)

   if rep1 == rep2:
       return

   if size[rep1] >= size[rep2]:
       reps[rep2] = rep1
       size[rep1] += size[rep2]
   else:
       reps[rep1] = rep2
       size[rep2] += size[rep1]

for _ in range(m):
   g, *group = list(map(int, stdin.readline().split()))

   for i in range(1, g):
       union(group[0], group[i])

ans = [size[find(node)] for node in range(1, n+1)]

print(*ans)

The key to this problem is realizing that once we buy a spell of form (c1, c2), we can turn any c1 to c2. If we then add a spell of form (c2, c3), we can turn any c1 into c2 and c3, any c2 into c1 and c3, etc. Basically, any two characters that are connected by a direct or indirect spell can be interchanged. This brings the problem to a simple union find problem. As we iterate over the two strings, if the two characters at an index are not similar and are not part of the same group (connected by an already bought spell), we buy a spell to connect them and record that spell. Otherwise, we skip them.

reps = list(range(n + 1))
size = [1] * (n + 1)

def find(x):
  if reps[x] != x:
      reps[x] = find(reps[x])
  return reps[x]

def union(node1, node2):
  rep1 = find(node1)
  rep2 = find(node2)

  if rep1 == rep2:
      return False

  if size[rep1] >= size[rep2]:
      reps[rep2] = rep1
      size[rep1] += size[rep2]
  else:
      reps[rep1] = rep2
      size[rep2] += size[rep1]

  return True

input()
s1 = input()
s2 = input()

spells = []
for c1, c2 in zip(s1, s2):
  if union(ord(c1) - ord('a'), ord(c2) - ord('a')):
      spells.append([c1, c2])

print(len(spells))
for spell in spells:
   print(*spell)

The tricky part about this problem is understanding the problem statement. It asks you to find the size of the largest group at the ith step, assuming that exactly i introductions have been made. This means that if you were asked to introduce two people that already know each other, you have not made that introduction. But since you were told to make exactly i introductions at each step, the question becomes how do you use that extra introduction optimally.

To solve this problem, we use union find. At each condition, we union the two given people. If they already know each other, we have one extra introduction we can make. To find the maximal group that would exist if we had used the extra pairing, we assume to use it to introduce the two largest groups. For example, at a point, if we have groups of size 3, 5, 2 and 4:

• If we have no extra introductions, the size of the maximal group will be 5
• If we have 1 extra introduction, the size of the maximal group will be 9 (since we can use the extra introduction to introduce two people from the groups of size 5 and 4)
• If we have 2 extra introductions, the size of the maximal group will be 12 (since we can use the extra introductions to merge the groups of size 3, 4, and 5.

It is important to remember that we don’t actually union the groups with our extra introductions, since the group sizes change and the largest groups will always be changing. To find the k largest groups (assuming we have k extra introductions at a step), we can use a max heap. Converting the parents array into a max-heap at each union step is costly (n2), but it is manageable with the given constraints.

from heapq import *
from sys import stdin

n, t = [int(i) for i in  stdin.readline().split()]
reps = list(range(n + 1))
size = [1] * (n + 1)
extras = 0

def find(x):
  if reps[x] != x:
      reps[x] = find(reps[x])
  return reps[x]

def union(node1, node2):
   global extras
   rep1 = find(node1)
   rep2 = find(node2)

   if rep1 != rep2:
     if size[rep1] >= size[rep2]:
         reps[rep2] = rep1
         size[rep1] += size[rep2]
     else:
         reps[rep1] = rep2
         size[rep2] += size[rep1]
   else:
       extras += 1

   heap = [-s for n, s in enumerate(size) if reps[n] == n]
   heapify(heap)

   max_cons = 0
   for _ in range(extras + 1):
       max_cons += abs(heappop(heap))

   print(max_cons - 1)

for _ in range(t):
   p1, p2 = [int(i) for i in stdin.readline().split()]
   union(p1, p2)

This is a classic minimum spanning tree problem with a slight twist. If you are unfamiliar with minimum spanning trees, we suggest you read this material to get a general idea. Coming back to the question, it is important to realize that special offers are not necessarily more optimal than classic edges (creating an edge with a cost equal to the sum of the two nodes it connects). This means we need to consider normal edges as well as special offer edges in the same manner. A straightforward implementation for this would be to just create all possible edges by combining every node with every other node and putting all those edges together with the special edges. We could then sort them based on weight and count the cost to connect the whole tree. However, it is not efficient to create every possible edge (it would take O(n2) time). At this point, it is important to realize that although we are grouping items, creating groups in such a way that we make all the nodes join into a group with the smallest cost node is the most optimal way to use the normal edges. This arises from the fact that the cost of these edges is the sum of the two nodes, choosing one of the nodes to be as small as possible can help us. Looking at the general solution, we create edges that connect the smallest node with every other node, and put them together with the special edges. We then sort all these edges by cost and start checking if they connect two separate components or if they are redundant edges that connect two nodes already in the same component. If the former is the case, we add the cost to our total, otherwise we skip this node. We do this for all our nodes and the running total will be the answer. This algorithm is known as Kruskal’s Algorithm and we encourage you to do your own further research on it.

from sys import stdin

n, o = [int(i) for i in input().split()]
cost = [int(i) for i in input().split()]

reps = list(range(n + 1))
size = [1] * (n + 1)

def find(x):
  if reps[x] != x:
      reps[x] = find(reps[x])
  return reps[x]
def union(node1, node2):
   rep1 = find(node1)
   rep2 = find(node2)

   if rep1 == rep2:
       return False
   if size[rep1] >= size[rep2]:
       reps[rep2] = rep1
       size[rep1] += size[rep2]
   else:
       reps[rep1] = rep2
       size[rep2] += size[rep1]

   return True

offers = []
for _ in range(o):
   n1, n2, c = [int(i) for i in stdin.readline().split()]
   offers.append((c, n1, n2))
  
for i in range(n):
   cost[i] = (cost[i], i + 1)
cost.sort()

for i in range(1, n):
   offers.append((cost[0][0] + cost[i][0], cost[0][1], cost[i][1]))
offers.sort()

total = 0
for c, n1, n2 in offers:
   if union(n1, n2):
       total += c
      
print(total)

Try to think in a level order manner

We can notice that the Level of the Employee matters for it to have dinner with the others. Which is basically his level in the graph which decides this. So what we can do is to construct the graph with keeping track of the indegree of the node and doing BFS starting from the nodes which have 0 indegree because they are the top level managers and collecting all of them who have the same level to one place.

import heapq, math
from itertools import *
from bisect import *
from collections import *
from sys import stdin, stdout

def pr(out):
    return stdout.write(f"{out}\n")


def input():
    return stdin.readline().rstrip()


def int_inp():
    return int(input())


def inp_int_l():
    return list(map(int, stdin.readline().split()))


def inp_l():
    return stdin.readline().split()

def solve():
    n = int(input())
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for node in range(n):
        p = int_inp()
        if p != -1:
            graph[p - 1].append(node)
            indegree[node] += 1
    level = [[node for node in range(n) if indegree[node] == 0]]
    queue = deque(level[0])
    while queue:

        lev = []
        for _ in range(len(queue)):
            node = queue.popleft()
            for nei in graph[node]:
                lev.append(nei)
                queue.append(nei)
        level.append(lev)
    count = 0
    for l in level:
        if l:
            count += 1

    print(count)


if __name__ == "__main__":
    t = 1
    for _ in range(t):
        solve()

Notice that the second array is already sorted

Could you be Greedy

For maximizing our sum we need to replace the minimum numbers that we have with the minimum number in the second array since the order doesn't matter we can do that pretty easily. We can use heap for getting the minimum number in the first array and since the second array is already sorted we can reverse the second array ans start from the end of the second array and replace the minimum number in the first array by the number at the end. Repeat this process till the second array become empty and return the sum of the numbers that you have left in the first array.

import heapq

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    first_array = list(map(int, input().split()))
    second_array = list(map(int, input().split()))
    second_array.reverse()
    heapq.heapify(first_array)
    while second_array:
        heapq.heapreplace(first_array, second_array.pop())
    print(sum(first_array))

Try considering the two cases differently.

Identify the source and destination and find the path in between.

Since the Two cases are different we can just do a basic source and destination bfs with two states and check whether the path could lead to the the (2,n) place if we could reach there we can return True else we return False.

import heapq, math
from itertools import *
from bisect import *
from collections import *
from sys import stdin, stdout


###########-> Templates <- ##########
def pr(out):
    return stdout.write(f"{out}\n")


def input():
    return stdin.readline().rstrip()


def int_inp():
    return int(input())


def inp_int_l():
    return list(map(int, stdin.readline().split()))


def inp_l():
    return stdin.readline().split()


####################################


def solve():
    n = int_inp()
    grid = [input() for _ in range(2)]

    def inbound(row, col):
        return 0 <= row < 2 and 0 <= col < n

    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    flag = True
    queue = deque([(0, 0)])
    visited = set([(0, 0)])

    while queue:
        if flag:
            for _ in range(len(queue)):
                row, col = queue.popleft()
                for dr, dc in directions:
                    new_row, new_col = row + dr, col + dc
                    if inbound(new_row, new_col) and (new_row, new_col) not in visited:
                        queue.append((new_row, new_col))
                        visited.add((new_row, new_col))
                if (row, col) == (1, n - 1):
                    print("YES")
                    return
            flag = False

        else:
            for _ in range(len(queue)):
                row, col = queue.popleft()
                if grid[row][col] == ">":
                    new_col = col + 1
                    if inbound(row, new_col) and (row, new_col) not in visited:
                        queue.append((row, new_col))
                        visited.add((row, new_col))

                elif grid[row][col] == "<":
                    new_col = col - 1
                    if inbound(row, new_col) and (row, new_col) not in visited:
                        queue.append((row, new_col))
                        visited.add((row, new_col))
                if (row, col) == (1, n - 1):
                        print("YES")
                        return
            flag = True
    print("NO")


if __name__ == "__main__":
    t = int(input())E. The Two Routes
    for _ in range(t):
        solve()

Could we be Greedy

Since we are required to drink the most possible number of potions we should drink all of the positive potions. For negative ones we can choose either to use the health that we have already collected on them already or jump them. Since jump and checking whether we should have taken it will take much time. What we can do is to drink the negative potion if we have health greater than it if we don't have we can store the potions that we have drunk till now in a heap and pop from the heap till the health becomes greater than or equal to the negative potion if we couldn't reach that number we just jump it and do the process and we take the maximum length of the heap each time and that will be our answer.

import heapq, math
from itertools import *
from bisect import *
from collections import *
from sys import stdin, stdout


###########-> Templates <- ##########
def pr(out):
    return stdout.write(f"{out}\n")


def input():
    return stdin.readline().rstrip()


def int_inp():
    return int(input())


def inp_int_l():
    return list(map(int, stdin.readline().split()))


def inp_l():
    return stdin.readline().split()


####################################


def solve():
    n = int_inp()
    potions = inp_int_l()

    count = 0
    max_heap = []
    curr_health = 0
    for i in range(n):
        curr_health += potions[i]
        heapq.heappush(max_heap, potions[i])
        while curr_health < 0 and max_heap:
            curr_health -= heapq.heappop(max_heap)
    print(len(max_heap))


if __name__ == "__main__":
    t = 1
    for _ in range(t):
        solve()

Try to construct different roads for the car and the train

Since we are required to find the minimal time it will be the max time from that of the train and the bus to reach the nth town. For doing that we need to construct the graphs for both the bus and the train but constructing for the bus will consume much time so we can use the train graph and use that graph's complement for getting the graph for the bus. After that the solution is easy we just do source and destination bfs if both the train and the bus could reach the nth city we return the maximum time from the two otherwise if one of them could not reach we return -1.

import heapq, math
from itertools import *
from bisect import *
from collections import *
from sys import stdin, stdout


###########-> Templates <- ##########
def pr(out):
    return stdout.write(f"{out}\n")


def input():
    return stdin.readline().rstrip()


def int_inp():
    return int(input())


def inp_int_l():
    return list(map(int, stdin.readline().split()))


def inp_l():
    return stdin.readline().split()


####################################


def solve():
    n, m = inp_int_l()
    graph = [set() for _ in range(n)]
    for _ in range(m):
        u, v = inp_int_l()
        graph[u - 1].add(v - 1)
        graph[v - 1].add(u - 1)
    visited = set()

    train_time = -1
    queue = deque([(0, 0)])  # Node and time
    visited.clear()
    visited.add(0)
    while queue:
        node, time = queue.popleft()
        if node == n - 1:
            train_time = time
            break
        for nei in graph[node]:
            if nei not in visited:
                queue.append((nei, time + 1))
                visited.add(nei)
    nodes = set(i for i in range(n))
    bus_time = -1
    queue = deque([(0, 0)])
    visited.clear()
    visited.add(0)
    while queue:
        node, time = queue.popleft()
        nodes.remove(node)
        if node == n - 1:
            bus_time = time
            break
        neighbors = nodes - graph[node]
        for nei in neighbors:
            if nei not in visited:
                queue.append((nei, time + 1))
                visited.add(nei)
    if train_time == -1 or bus_time == -1:
        print(-1)
    else:
        print(max(train_time, bus_time))


if __name__ == "__main__":
    t = 1
    for _ in range(t):
        solve()