1777

A_Everybody_Likes_Good_Arrays

Explanation

Optimized Solution:

1. Check how many times the parity changes in the given array.

2. The number of operations needed is the difference between the original length of the array and the count of parity changes.

3. Explanation

def solve():
    n = int(input())
    ar = list(map(int, input().split()))

    # Count the number of times the parity changes in the array
    last_parity = None
    parity_count = 0
    for x in ar:
        if x % 2 != last_parity:
            parity_count += 1
            last_parity = x % 2

    # The result is the difference between the original length and the count of parity changes
    res = n - parity_count
    print(res)


for _ in range(int(input())):
    solve()

B_Emordnilap

Explanation

Logic:

1. Find the factorial of the given number n
2. Calculate the total number of inversion pairs in the array
3. Multiply the factorial by the number of inversion pairs and take the result modulo 10^9 + 7

def solve():
    n = int(input())
    MOD = 10**9 + 7

    # Calculate the total number of inversion pairs in the array
    pairs = n * (n - 1)

    # Find the factorial of n
    fact = 1
    for i in range(1, n + 1):
        fact = fact * i % MOD  # requirement: size n modulo 1000000007(109+7)

    # Calculate the result by multiplying the factorial by the number of inversion pairs
    res = (fact * pairs) % MOD
    print(res)


for _ in range(int(input())):
    solve()

C_Quiz_Master

Explanation

You need to form a team from a group of students with different smartness levels such that the team is proficient in all given topics.

A student is proficient in a topic if their smartness is divisible by the topic number.

The goal is to minimize the maximum difference in smartness between any two students in the team.

Logic:

1. Precompute divisors for all numbers up to a maximum value
2. Sort the students by their smartness levels
3. Use the sliding window approach with two pointers (left and right) to maintain a window of students
4. Iterate through the students, updating the count of students proficient in each topic using the precomputed divisors
5. Adjust the window size to minimize the maximum difference in smartness levels between any two students in the window

def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()

    res = float("inf")
    l = 0
    cnt = [0] * (m + 1)
    window = 0

    for r in range(n):
        for div in divisors[a[r]]:
            if div > m:
                continue
            cnt[div] += 1
            if cnt[div] == 1:
                window += 1

        while l != n and window == m:
            res = min(res, a[r] - a[l])
            for div in divisors[a[l]]:
                if div > m:
                    continue
                cnt[div] -= 1
                if cnt[div] == 0:
                    window -= 1
            l += 1

    if res != float("inf"):
        print(res)
    else:
        print(-1)


MAX = 100010
divisors = [[] for _ in range(MAX)]
for i in range(1, MAX):
    for j in range(i, MAX, i):
        divisors[j].append(i)


for _ in range(int(input())):
    solve()

D_Score_of_a_Tree

Explanation

You are given a tree with 'n' nodes, where each node has a value of either 0 or 1 at time t=0.

At every subsequent time step, the value of a node becomes the bitwise XOR of the values of its children at the previous time step.

The goal is to find the sum of the values of all nodes at every time step until t=10^100 for all 2^n possible initial configurations of the tree.

The final answer should be the sum of these values modulo 10^9+7.

Logic:

The XOR operation propagates the values in the tree from the leaves towards the root.

The maximum number of time steps required to propagate the values to the root is the depth of the tree.

We can: 1. compute the depth of each node using depth-first search (DFS) 2. calculate the sum of the depths 3. finally multiply the sum by 2^(n-1) to account for all possible configurations.

Naive approach:

A naive approach would be to iterate over all possible initial configurations of 0s and 1s and perform the XOR operation on the tree for every time step, up to a large number (e.g., 10^100), and sum the values of all nodes.

from collections import defaultdict

MOD = 10**9 + 7


def dfs(graph, depth):
    stack = [(1, -1, True)]  # node, parent, first_visit
    while stack:
        node, parent, first_visit = stack.pop()

        if first_visit:
            stack.append((node, parent, False))
            for neighbor in graph[node]:
                if neighbor != parent:
                    stack.append((neighbor, node, True))
        else:  # if it's not the first visit, update the depth of the parent node
            if parent != -1:
                depth[parent] = max(depth[parent], depth[node] + 1)


def solve():
    n = int(input())
    graph = defaultdict(list)

    for _ in range(n - 1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    depth = [1] * (n + 1)
    dfs(graph, depth)

    res = sum(depth[1:])  # sum of depths from the 2nd node to the last node
    print(res * pow(2, n - 1, MOD) % MOD)


for _ in range(int(input())):
    solve()