This problem just needs to simulate everything that was given in the statement.

n, k = map(int, input().split())
nums = input().split()
count = 0 
for num in nums:
    num_count = num.count('4') + num.count('7')
    if num_count <= k:
        count += 1

print(count)

The problem requires finding how many values ofxcan divide the chores into exactlyachores for Petya (with complexity greater thanx) andbchores for Vasya (with complexity less than or equal tox).

Approach:

1. Sort the Chore Complexities: Begin by sorting the array of chore complexities in ascending order. This allows us to easily separate the chores for Petya and Vasya based on their desired counts.
2. Identifying the Chore Split: Since Vasya will take thebleast complex chores, these will be the firstbelements in the sorted array. Petya will then take the remaining a chores, which are the lastaelements in the sorted array.
3. Determinex: The thresholdxthat divides the chores must be greater than the largest complexity of the chores Vasya takes and less than or equal to the smallest complexity of the chores Petya takes. Therefore,xmust satisfy: arr[b - 1] < x ≤ arr[b].
4. Calculate the Number of Valid Values forx: The number of validxvalues is given by arr[b] - arr[b - 1]. This represents the range of values thatxcan take to properly divide the chores between Petya and Vasya. If the values of arr[b] and arr[b - 1] are the same, no suchxexists, and the answer is $$$0$$$.

import sys

input = lambda: sys.stdin.readline().rstrip()

n, a, b = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

print(arr[b] - arr[b - 1])

We can simulate exactly what's described in the statement: loop over all cells not equal to $$$1$$$ and check if it doesn't break the city property. To check if a cell breaks the property, just loop over an element in the same row, and an element in the same column, and see if they can add to give the cell's number. The complexity is $$$O(n^4)$$$.

n = int(input())

lab = [] 
for _ in range(n):
    lab.append(list(map(int, input().split())))

for i in range(n):
    for j in range(n):
        if lab[i][j] != 1:
            for k in range(n):
                if i != k and lab[i][j] - lab[k][j] in lab[i]:
                    break
            else:
                print('No')
                exit(0)

print('Yes')

Look for patterns in how cards are distributed based on the step number..

Group steps using modulo 4 to see who gets which cards.

To determine how many cards Alice and Bob receive from a deck of n cards dealt in increasing steps, we can use two approaches: a direct simulation and an optimized mathematical method.

Initial Approach (Simulation):

1. Calculate Maximum Complete Steps x: Simulate dealing cards step-by-step until the total dealt cards exceed n.

2. Compute Total Cards Dealt and Remainder: Sum the cards dealt up to the largest complete step x and find the remaining cards.

3. Distribute Cards:
   • Alice receives cards on steps where current_step % 4 is $$$1$$$ or $$$0$$$.
   • Bob receives cards on steps where current_step % 4 is $$$2$$$ or $$$3$$$.
4. Add Remaining Cards: Distribute any leftover cards based on the current step index after the last complete step.

Time complexity: $$$O(n)$$$
Space complexity: $$$O(1)$$$

import sys
input = lambda: sys.stdin.readline().rstrip()

t = int(input())
for _ in range(t):
    n = int(input())
    total_cards = 0
    step = 1

    # Find the maximum number of complete steps
    while total_cards + step <= n:
        total_cards += step
        step += 1

    x = step - 1
    remainder = n - total_cards

    alice_sum = bob_sum = 0
    current_step = 1

    # Distribute cards up to step x
    for i in range(1, x + 1):
        if current_step % 4 == 1 or current_step % 4 == 0:
            alice_sum += i
        else:
            bob_sum += i
        current_step += 1

    # Add the remainder to the correct person
    if remainder > 0:
        if current_step % 4 == 1 or current_step % 4 == 0:
            alice_sum += remainder
            
        else:
            bob_sum += remainder
            
    print(alice_sum, bob_sum)

The initial approach, while straightforward, may be inefficient for large n. We can optimize it using mathematical formulas.

Solution Approach:

1. Find Maximum Number of Complete Stepsx: Calculatex where the sum of the first x numbers does not exceed n:

   • Solving for x from this equation ($$$n = \frac{x \cdot (x + 1)}{2}$$$ ) which is the sum of the first natural numbers up to $$$x$$$ gives the bound as $$$x = \left\lfloor \frac{-1 + \sqrt{1 + 8 \cdot n}}{2} \right\rfloor$$$.

2. Calculate Total Cards Dealt and Remaining Cards:

   • Total cards dealt total: $$$\frac{x \cdot (x + 1)}{2}$$$
   • Remainder: n - total

3. Distribute Cards Using Arithmetic Series:

   • Alice’s Cards: Sum of series for steps where i % 4 = 1 and i % 4 = 0.
   • Bob’s Cards: Sum of series for steps where i % 4 = 2 and i % 4 = 3.
   • Use the formula for the sum of an arithmetic series:
     • $$$S_m = \frac{m}{2} \left(2a_1 + (m - 1) \cdot d \right)$$$ where $$$a_1$$$ is the first term, $$$d$$$ is the common difference, and $$$m$$$ is the number of terms.
4. Add Remaining Cards: Distribute the remainder based on the step index after x steps.

Time complexity: $$$O(\log n)$$$
Space complexity: $$$O(1)$$$

import sys, math

input = lambda: sys.stdin.readline().rstrip()

def arithmetic_series_sum(start, diff, last_term):
    """
    Calculate the sum of an arithmetic series where the first term is `start`,
    the common difference is `diff`, and the last term is `last_term`.
    """
    count = (last_term - start) // diff + 1
    return count * (2 * start + (count - 1) * diff) // 2

def find_max_x(n):
    """
    Find the maximum `x` such that the sum of the first `x` natural numbers is <= `n`.
    """
    return math.floor((-1 + math.sqrt(1 + 8 * n)) / 2)

t = int(input())

for _ in range(t):
    n = int(input())
    
    # Determine the maximum `x` for which the sum of the first `x` natural numbers is <= `n`
    x = find_max_x(n)
    
    # Total sum of the first `x` natural numbers
    total_sum_x = x * (x + 1) // 2
    
    # Calculate the remaining cards
    remainder = n - total_sum_x
    
    # Calculate sums for Alice and Bob up to the largest valid `x`
    alice_sum = 1 + arithmetic_series_sum(4, 4, x) + arithmetic_series_sum(5, 4, x)
    bob_sum = arithmetic_series_sum(2, 4, x) + arithmetic_series_sum(3, 4, x)
    
    # Distribute the remaining cards
    if remainder > 0:
        if (x + 1) % 4 in (1, 0):
            alice_sum += remainder
        else:
            bob_sum += remainder
    
    print(alice_sum, bob_sum)

If $$$d_i$$$ is less than $$$l_i$$$, then $$$d_i$$$ itself is the smallest integer that satisfies the condition because it is divisible by $$$d_i$$$ and does not belong to $$$[l_i, r_i]$$$.

Otherwise, if $$$d_i$$$ is within the segment $$$[l_i, r_i]$$$, the smallest integer divisible by $$$d_i$$$ that is not in the segment is $$$(\lfloor r_i / d_i \rfloor + 1) \cdot d_i$$$.

for _ in range(int(input())):
    l, r, d = map(int,input().split())
    if d < l:
        print(d)
    else:
        print((r//d + 1)*d)

In this problem, our goal is to determine the number of indices that can be set to $$$1$$$ after performing m swaps. Each swap operation allows us to swap elements within a given range $$$[l, r]$$$.

Initially, without any swaps, the only index that can be $$$1$$$ is $$$x$$$. However, if we have a range that includes the current index $$$x$$$, we can swap any of the indices within that range with the current index. This means that the possible indices that can be $$$1$$$ expand based on the ranges provided.

To solve this, we need to combine all the ranges. If the final combined range includes the index $$$x$$$, then all indices within that range can be set to $$$1$$$.

t = int(input())
for _ in range(t):
    n,k,m = list(map(int,input().split()))
    start = k
    end = k
    
    for i in range(m):
        l,r = gns()
        if l <= start <= r or  l <= end <= r:
            start  = min(start,l)
            end = max(end,r)
    print(end - start + 1)

Notice that there will be a path that passes through the edge labeled $$$0$$$ and the edge labeled $$$1$$$ no matter how you label the edges, so there's always a path with MEX $$$2$$$ or more. If any node has degree $$$3$$$ or more, you can distribute the labels $$$0$$$, $$$1$$$, and $$$2$$$ to edges incident to this node and distribute the rest of the labels arbitrarily. Otherwise, the tree is a bamboo, and it doesn't actually matter how you label the edges, since there will be a path with MEX $$$n−1$$$ anyway.

import sys
from collections import defaultdict

graph = defaultdict(list)
ans = {}

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

for i in range(1, n):
    a, b = map(int, sys.stdin.readline().strip().split())
    graph[a].append(i)
    graph[b].append(i)
    ans[i] = -1

# Find the node with the maximum degree
mx = (0, 0)
for i in range(1, n + 1):
    if len(graph[i]) > mx[0]:
        mx = (len(graph[i]), i)

cur = 0
for i in graph[mx[1]]:
    ans[i] = cur
    cur += 1

for i in range(1, n):
    if ans[i] == -1:
        ans[i] = cur
        cur += 1
    print(ans[i])

• Solution 1: Let's use the data structure called a bitwise trie. Fix some $$$a_{i}$$$, where all $$$a_{j}$$$ for $$$j<i$$$ have already been added to the trie. We will iterate over the bits in $$$a_{i}$$$ from the $$$(k−1)^{th}$$$ bit to the $$$0^{th}$$$ bit. Since $$$2^{t}>2^{t−1}+2^{t−2}+…+2+1$$$, if there exists $$$a_{j}$$$ with the same bit at the corresponding position in $$$a_{i}$$$, we will go into that branch of the trie and append $$$1−b$$$ to the corresponding bit $$$x$$$. Otherwise, our path is uniquely determined. When we reach a leaf, the bits on the path will correspond to the optimal number $$$a_{j}$$$ for $$$a_{i}$$$. The time complexity of this solution is $$$O(nk)$$$.
• Solution 2: Sort $$$a_{1},a_{2},…,a_{n}$$$ in non-decreasing order. We will prove that the answer is some pair of adjacent numbers. Let the answer be numbers $$$a_{i},a_{j} (j−i>1)$$$. If $$$a_{i}=a_{j}$$$, then $$$a_{i}=a_{i+1}$$$. Otherwise, they have a common prefix of bits, after which there is a differing bit. That is, at some position $$$t$$$, $$$a_{i}$$$ has a $$$0$$$ and $$$a_{j}$$$ has a $$$1$$$. Since $$$j−i>1$$$, $$$a{i+1}$$$ can have either $$$0$$$ or $$$1$$$ at this position, but in the first case it is more advantageous to choose $$$a_{i},a_{i+1}$$$ as the answer, and in the second case it is more advantageous to choose $$$a_{i+1},a_{j}$$$ as the answer. The complexity of this solution is $$$O(nlogn)$$$.

For the first approach, make sure to use $$$PyPy 3-64$$$.

import sys
input = lambda: sys.stdin.readline().rstrip()

class TrieNode:
    def __init__(self):
        self.children = [None, None]
        self.position = -1 # index of the corresponding number in the given array

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

    ans_i = ans_j = ans_x = 1, 1, 0
    max_val = 0 # maximum value of (a[i] ^ x) & (a[j] ^ x)
    
    root_node = TrieNode()
    for i, num in enumerate(a):
        cur_node = root_node
        # find a pair a[j] for this number
        # first check if there's at least one number in the trie
        if cur_node.children[0] or cur_node.children[1]:
            x = 0
            for bit_i in range(k - 1, -1, -1):
                if num & (1 << bit_i):
                    # match 1 bit with 1 bit
                    if cur_node.children[1]:
                        cur_node = cur_node.children[1]
                    else: # if not possible, match 1 bit with 0 bit
                        cur_node = cur_node.children[0]

                else:
                    # match 0 bit with 0 bit
                    if cur_node.children[0]:
                        cur_node = cur_node.children[0]
                        x = x ^ (1 << bit_i)
                    else: # if not possible, match 0 bit with 1 bit
                        cur_node = cur_node.children[1]

            j = cur_node.position
            new_val = (num ^ x)&(a[j] ^ x)
            if new_val >= max_val:
                max_val = new_val
                ans_i, ans_j, ans_x = i + 1, j + 1, x

        # insert the current number into the trie
        cur_node = root_node
        for bit_i in range(k - 1, -1, -1):
            if num & (1 << bit_i):
                if not cur_node.children[1]:
                    cur_node.children[1] = TrieNode()
                cur_node = cur_node.children[1]

            else:
                if not cur_node.children[0]:
                    cur_node.children[0] = TrieNode()
                cur_node = cur_node.children[0]

        cur_node.position = i

    print(ans_i, ans_j, ans_x)

    

If we connect the graph using $$$0$$$-weighted edges only and we are left with $$$k$$$ components, we need $$$k - 1$$$ $$$1$$$-weighted edges.

Let's keep track of the unconnected nodes in a set and every time we do a BFS starting from an unconnected node to a node that has no edge with it. We have to check if there is a node in unconnected nodes that is not a neighbor (considering $$$1$$$-weighted edge) of it. Every time we check if the node is the neighbor we pass it and if not we add it in the BFS queue. Worst case, the first case will only happen $$$m$$$ (the number of $$$1$$$-weighted edges) times and the second case will only happen $$$n$$$ times. The overall time complexity will be $$$O(n + m)$$$.

from collections import defaultdict, deque
from sys import stdin


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

N, M = map(int, input().split())

adj = defaultdict(set)
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    adj[u].add(v)
    adj[v].add(u)

unconnected = set(range(N))
edges = 0

for i in range(N):
    if i in unconnected:
        q = deque([i])
        unconnected.remove(i)
        while q:
            v = q.popleft()
            remove = []
            for u in unconnected:
                if v not in adj[u]:
                    edges += 1
                    remove.append(u)
                    q.append(u)
            for u in remove:
                unconnected.remove(u)
print(N - 1 - edges)