There are many possible solutions. One of them is just to print $$$2,3,…,n,1$$$.

import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    ans = []
    for i in range(2, n + 1):
        ans.append(i)
    ans.append(1)
    print(*ans)

Let $$$score(i)$$$ be the result of the game if we chose $$$i$$$ as the starting position. Let's look at some starting position $$$i$$$. After making a move from it, we will get $$$a[i]$$$ points and move to the position $$$i+a[i]$$$. Let $$$j = i+a[i]$$$, if this is still inbounds we will apply the same operation until it gets out of bounds where the score is $$$0$$$. Formally, $$$score(i)=score(i+a[i])+a[i]$$$.

So lets consider every index as a starting position and track the maximum score we can get.

import sys, threading
input = lambda: sys.stdin.readline().strip()


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

        memo = [-1]*n

        def dp(idx):
            # base case
            if idx >= n:
                return 0

            if memo[idx] != -1:
                return memo[idx]
            
            memo[idx] = dp(idx + a[idx]) + a[idx]
            return memo[idx]
        
        ans = 0
        for start in range(n):
            ans = max(ans, dp(start))
        
        print(ans)

    
if __name__ == '__main__':
    
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()

What should our state be?

At each state, what are our possible options?

How does our state change after choosing one of the options?

We are going to use dynamic programming to solve this problem. Our state is going to be $$$n$$$. At each step, we have 3 choices: take $$$a$$$, $$$b$$$, or $$$c$$$. Our recurrence relation is going to be:

$$$dp(n)= 1+max⁡(dp(n−a),dp(n−b),dp(n−c))$$$

For our base cases, if $$$n$$$ becomes 0, we return 0. Another base case is if $$$n$$$ is less than 0, we return $$$-inf$$$, which is a very small number because we want the maximum answer. This answer will ensure that we do not consider this path.

from functools import lru_cache
import sys
import threading

def main():
    n,a,b,c = list(map(int,input().split()))

    memo = [-1 for i in range(n + 1)]
    
    def dp(n):
        
        if n < 0:
            return -float('inf')
        if n == 0:
            return 0
        
        if memo[n] != -1:
            return memo[n]
        
        memo[n] = 1 + max(dp(n - a),dp(n - b),dp(n - c))
        
        return memo[n]
    
    print(dp(n))
    
sys.setrecursionlimit( 1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target = main)
main_thread.start()
main_thread.join()

One thing we can notice is that if we choose a number $$$x$$$, it means we can't choose $$$x - 1$$$ and $$$x + 1$$$. In other words, this means we can't choose two consecutive values. Another point is that once we choose $$$x$$$, choosing it multiple times wouldn't have any disadvantage on our score. Therefore, if we decide to choose $$$x$$$, we have to choose all instances of $$$x$$$, and the score if we choose all $$$x$$$ is going to be $$$\text{count}[x] \times x$$$.

For every number between 1 and $$$\max(a)$$$:

$$$f(i) = \max(f(i - 1), f(i - 2) + \text{count}[i] \times i), \quad 2 \leq i \leq n;$$$

$$$f(1) = \text{count}[1];$$$

$$$f(0) = 0;$$$

The answer is $$$f(n)$$$.

import sys, threading
from collections import Counter

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

def main():
    memo = {}
    n = int(input())
    cnt = Counter(map(int,input().split()))
    def dp(n):

        if n <= 1:
            return cnt[n]
        if n not in memo:
            memo[n] = max(dp(n -1), dp(n -2) + cnt[n]*n)
    	return memo[n]
    print(dp(max(cnt.keys())))
    
if __name__ == '__main__':
    
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()

Let's define ( S(k) ) as the sum of elements $$$\sum\limits_{i = k}^{n}{a_i}$$$. Additionally, let $$$p_i$$$ denote the starting position of the $$$( ith)$$$ subarray, where $$$( p1 = 1)$$$ and $$$( pi < pi+1)$$$.

Now, consider the transformation:$$$\sum_{i=1}^{n}{a_i \cdot f(i)} = 1 \cdot (S(p_1) - S(p_2)) + 2 \cdot (S(p_2) - S(p_3)) + \dots + k \cdot (S(p_k) - 0) = \ = S(p_1) + (2 - 1) S(p_2) + (3 - 2) S(p_3) + \dots + (k - (k - 1))) S(p_k) = \ = S(p_1) + S(p_2) + S(p_3) + \dots + S(p_k)$$$

So, our objective is to select the sum of the entire array ( S(1) ) and ( k — 1 ) different suffix sums to maximize their total sum. Consequently, we can simply select the (k — 1) maximum suffix sums along with the sum of the entire array.

Time Complexity: $$$O(n)$$$ time. Space Complexity: $$$O(n)$$$

def main():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))

    sfxSum = [nums[-1]]
    for i in range(n - 2, -1, -1):
        sfxSum.append(sfxSum[-1] + nums[i])
    
    ans = sfxSum.pop()
    sfxSum.sort(reverse=True)
    for i in range(k - 1):
        ans += sfxSum[i]
    print(ans)

if __name__ == '__main__':
    main()

For this problem, the constraints allow us to implement it in $$$O(n)^2$$$ time, but let's try to do it in linear time complexity. We can have a variable for the final answer and iterate through the given string s. If the last character in our answer is a vowel and if $$$s_i$$$ is also a vowel, we can skip adding it to our answer; otherwise, we will add $$$s_i$$$ to our answer.

import sys
input = sys.stdin.readline

N = int(input())
word = input()

answer = []
vowels = {'a', 'e', 'i', 'o', 'u', 'y'}
for char in word:
    if answer and answer[-1] in vowels and char in vowels:
        continue
    answer.append(char)
print(*answer, sep="")

Can we get a better value for $$$z$$$?

Note that $$$z$$$ is masking itself. Therefore its value cannot increase larger than the initial value.

We can now conclude that to get a maximum value, we just need to apply the operation to each index once without changing $$$z$$$. Then take the maximum $$$a_i$$$.

This will tell us that we only actually applied the operation to the number that gives us the maximum value (just once).

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

    max_val = 0
    for num in a:
        max_val = max(max_val, num | z)

    print(max_val)

To achieve the maximum $$$AND$$$ result, we set bits from the $$$30th$$$ bit down to the $$$0th$$$ bit for each number in the given array. However, the available operations $$$k$$$ may be less than the number of elements in the array $$$nums$$$. We first count how many operations we need for each bit position from $$$0$$$ to $$$30$$$ and store these counts in an array $$$needs$$$. Starting with the $$$30th$$$ bit (highest bit), we check if the operations required $$$needs[i]$$$ for setting that bit is within the available operations $$$k$$$. If it is less than or equal to $$$k$$$, we set that bit in the result $$$answer$$$ and subtract the required operations from $$$k$$$. This way, we prioritize setting higher bits in $$$answer$$$ first, as they have a greater impact on the value.

Time Complexity: $$$O(n)$$$

Space Complexity: $$$O(1)$$$

def main():
    for _ in range(int(input())):
        n, k = map(int, input().split())
        nums = list(map(int, input().split()))
        needs = [0] * 31

        for loc in range(31):
            for num in nums:
                if num & (1 << loc) == 0:
                    needs[loc] += 1
        
        max_val = 0

        for i in range(len(needs) - 1, -1, -1):
            if needs[i] <= k:
                max_val |= (1 << i)
                k -= needs[i]
        
        print(max_val)
    
if __name__ == '__main__':
    main()

Try calculating $$$f(l,r)$$$ bit by bit

Which condition has to hold true for all elements on a subsegment $$$[l,r]$$$, and for a certain bit, for that bit to be present in $$$f(l,r)$$$?

How can we check if that condition is true for a certain bit fast?

Try prefix sums.

Try binary search.

1. Calculating Prefix Sums of Bits:
   • We start by counting how many times each bit appears in the array up to a certain point. For example, how many 1s or 0s are there in the first few elements of the array.
   • We do this efficiently in $$$O(n \log(\text{max}(a)))$$$ time. Here, '$$$n$$$' is the length of the array, and '$$$\text{max}(a)$$$' is the maximum value in the array.
2. Understanding Bit Presence in a Range:
   • If the count of a particular bit (like the $$$j$$$-th bit) from index $$$l$$$ to index $$$r$$$ in the array is exactly the same as the length of that range $$$(r - l + 1)$$$, it means that bit appears in all the elements within that range.
3. Calculating $$$f(l,r)$$$:
   • Now, we want to find out for which bits this condition holds true within a certain range $$$[l, r]$$$ of the array.
   • We sum up the counts of all the bits where this condition holds true. This gives us the value of $$$f(l,r)$$$.
4. Solving Queries Efficiently:
   • For each query, given $$$l$$$ and $$$k$$$, we want to find the rightmost index $$$r$$$ such that $$$f(l,r)$$$ is greater than or equal to $$$k$$$.
   • We can use binary search to efficiently find $$$r$$$.
   • If $$$f(l,\text{mid})$$$ is greater than or equal to $$$k$$$, we move towards the right to find a larger $$$r$$$.
   • If not, we move towards the left to find a smaller $$$r$$$.
5. Overall Time Complexity:
   • This entire approach takes $$$O(Q \log(N) \log(\text{max}(a)))$$$ time to process all the queries, where $$$Q$$$ is the number of queries, $$$N$$$ is the length of the array, and $$$\text{max}(a)$$$ is the maximum value in the array.
   • For typical values, this works out to about $$$4 \times 10^7$$$ operations, which is pretty efficient.

So, by using this method, we efficiently handle queries about the presence of certain bits in specific ranges of the array.

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

    arr = [0] * 32
    prefix = [arr]  # Initialize prefix array with zeros

    # Calculate prefix sums of bits
    for num in nums:
        arr = prefix[-1].copy()
        for i in range(32):
            # If the i-th bit is set in num, increment the corresponding count in arr
            if num & (1 << i) != 0:
                arr[i] += 1
        prefix.append(arr)

    # Function to find the bitwise AND of all numbers within a range
    def rangeAnd(l, r):
        ans = 0
        for i in range(32):
            bit_count = prefix[r][i] - prefix[l - 1][i] if l > 0 else prefix[r][i]
            if bit_count == (r - l + 1):
                ans |= (1 << i)
        return ans

    # Binary search to find the rightmost index satisfying the condition
    def bin_search(l, k):
        left = l
        right = n
        while left <= right:
            mid = (right + left) // 2
            if rangeAnd(l, mid) >= k:
                left = mid + 1
            else:
                right = mid - 1

        if right < l:
            return -1
        return right

    ans = []
    # Process queries
    for _ in range(q):
        l, k = map(int, input().split())
        ans.append(bin_search(l, k))

 
    print(*ans)

First solve a simplified version: suppose that in type $$$1$$$ queries, only a single character of the string s is inverted, i.e., $$$l=r$$$ in all type $$$1$$$ queries.

When we invert $$$s_i$$$, the XOR of all numbers from group $$$0$$$ and group $$$1$$$ change in the same way, regardless of whether this inversion was from $$$0$$$ to $$$1$$$ or from $$$1$$$ to $$$0$$$.

We will store $$$2$$$ variables: $$$X_0,X_1$$$, which represent the XOR of all numbers from group $$$0$$$ and group $$$1$$$, respectively. When answering a query of type $$$2$$$, we will simply output either $$$X_0$$$ or $$$X_1$$$. Now we need to understand how to update $$$X_0$$$ and $$$X_1$$$ after receiving a query of type $$$1$$$.

Let's first solve a simplified version: suppose that in type $$$1$$$ queries, only a single character of the string s is inverted, i.e., $$$l=r$$$ in all type $$$1$$$ queries.

Let's see how $$$X_0$$$ and $$$X_1$$$ change after this query. If $$$s_i$$$ was $$$0$$$ and became $$$1$$$, then the number $$$a_i$$$ will be removed from group $$$0$$$. Since $$$XOR$$$ is its own inverse operation ($$$w⊕w=0$$$), we can do this with $$$X_0=X_0⊕a_i$$$. And in $$$X_1$$$, we need to add the number $$$a_i$$$, since now $$$s_i=1$$$. And we can do this with $$$X_1=X_1⊕a_i$$$.

The same thing happens if $$$s_i$$$ was $$$1$$$.

This is the key observation: when we invert $$$s_i$$$, $$$X_0$$$ and $$$X_1$$$ change in the same way, regardless of whether this inversion was from $$$0$$$ to $$$1$$$ or from $$$1$$$ to $$$0$$$.

Therefore, to update $$$X_0$$$ and $$$X_1$$$ after a query of type $$$1$$$ with parameters $$$l,r,$$$ we need to do this: $$$X_0=X_0⊕(a_l⊕…⊕a_r)$$$, and the same for $$$X_1$$$.

To quickly find the XOR value on a subsegment of the array a, we can use a prefix XOR array. If $$$p_i=a_1⊕…a_i$$$, then: $$$a_l⊕…⊕a_r=p_r⊕p_{l−1}$$$.

import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    a = list(map(int, sys.stdin.readline().strip().split()))
    s = sys.stdin.readline().strip()
    q = int(sys.stdin.readline().strip())

    pref = [0] * (n + 1)
    for i in range(1, n + 1):
        pref[i] = pref[i - 1] ^ a[i-1]

    x_0 = 0
    x_1 = 0
    for i in range(n):
        if s[i] == "0":
            x_0 ^= a[i]
        else:
            x_1 ^= a[i]

    ans = []
    for i in range(q):
        line = list(map(int, sys.stdin.readline().strip().split()))
        if line[0] == 2:
            if line[1]:
                ans.append(int(str(x_1)))
            else:
                ans.append(int(str(x_0)))
        else:
            l, r = line[1], line[2]
            seg = pref[r] ^ pref[l - 1]   
            x_0 ^= seg
            x_1 ^= seg
    print(*ans)

The formula given in this task looks difficult to calculate, so we can rewrite it:

$$$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n (x_i \, \& \, x_j) \cdot (x_j \, | \, x_k) = \sum_{j=1}^n \sum_{i=1}^n (x_i \, \& \, x_j) \sum_{k=1}^n (x_j \, | \, x_k) = \sum_{j=1}^n \left[ \sum_{i=1}^n (x_i \, \& \, x_j) \right] \cdot \left[ \sum_{k=1}^n (x_j \, | \, x_k) \right]$$$

We fix the element $$$x_j$$$. Now the task is to calculate two sums $$$\sum_i (x_i \, \& \, x_j)$$$ and $$$\sum_k (x_j \, | \, x_k)$$$, and multiply them by each other.

Let's define function $$$f(x, c)$$$ as the value of $$$c$$$-th bit in $$$x$$$. For example $$$f(13, 1) = 0$$$, because $$$13 = 11\underline{0}1_2$$$, and $$$f(12, 2) = 1$$$, because $$$12 = 1\underline{1}00_2$$$. Additionally, define $$$M$$$ as the smallest integer such that $$$\forall_i \, x_i < 2^M$$$. Note that in this task $$$M \leq 60$$$.

We can rewrite our sums using function $$$f$$$:

$$$\sum_i (x_i \, \& \, x_j) = \sum_{c = 0}^{M} 2^c \sum_i f(x_i, c) \cdot f(x_j, c) = \sum_{c = 0}^{M} 2^c f(x_j, c) \sum_i f(x_i, c)$$$

$$$\sum_k (x_j \, | \, x_k) = \sum_{c = 0}^{M} 2^c \sum_k 1 - (1 - f(x_j, c)) \cdot (1 - f(x_k, c)) = \sum_{c = 0}^{M} 2^c \left[ n - (1 - f(x_j, c)) \sum_k (1 - f(x_k, c)) \right]$$$

In other words, we just split elements $$$x_i$$$, $$$x_j$$$, $$$x_k$$$ into the powers of two.

If we memorize the values of $$$\sum_i f(x_i, c)$$$, for each $$$c \in {0, 1, \ldots, M }$$$, then we can calculate the desired sums in $$$\mathcal{O}(M)$$$ for fixed $$$x_j$$$ using the above equations.

So the final solution is to iterate over all elements in the array and fix them as $$$x_j$$$, and sum all of the results obtained. Complexity is $$$\mathcal{O}(nM) = \mathcal{O}(n \log \max_i(x_i))$$$

from sys import stdin


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

T = int(input())

for _ in range(T):
    N = int(input())
    x = list(map(int, input().split()))

    MOD = 1000_000_007
    bit_counts = [0]*60
    for xi in x:
        for i in range(60):
            if xi&(1<<i):
                bit_counts[i] += 1
    ans = 0
    for xi in x:
        tot_or = tot_and = 0
        for i in range(60):
            if xi&(1<<i):
                tot_or += (1<<i)%MOD*N
                tot_or %= MOD
                tot_and += (1<<i)%MOD*bit_counts[i]
                tot_and %= MOD
            else:
                tot_or += (1<<i)%MOD*bit_counts[i]
                tot_or %= MOD
        ans += tot_or*tot_and
        ans %= MOD

    print(ans)

If the length of the given string $$$s$$$ is odd, then the answer is $$$NO$$$, since it cannot be a concatenation of two equal strings. Otherwise, Let's slice the string into equal halves. If the two halves are equal the answer is $$$YES$$$, otherwise $$$NO$$$.

t = int(input())
for _ in range(t):
    s = input()

    if len(s)%2:
        print('NO')
    
    else:
        mid = len(s)//2
        print('YES' if s[:mid] == s[mid:] else 'NO')
        

Treat the forest as a union-find data structure.

The key observation is that each baboon and its most distant relative on the same tree belong to the same tree (connected component). We can use this fact to identify the number of trees.

Solution Approach:

We can use a Union-Find data structure to efficiently group relative baboons in a single tree. Initialize a union-find object with $$$n$$$ baboons (one for each baboon) Iterate through the sequences $$$s$$$. For each baboon $$$i$$$, perform a union operation on $$$i$$$ and $$$(s[i] - 1)$$$. This connects baboon $$$i$$$ with its most distant relative. Count the number of unique representatives in the union-find. That will be the answer.

Time & Space Complexity

Time Complexity: $$$O(n)$$$, where $$$n$$$ is the number of baboons. This is due to the single loop for processing the $$$s$$$ sequence and another loop for finding representatives. Space Complexity: $$$O(n)$$$, due to the Union-Find data structure and the set used to store representatives.

from collections import defaultdict
class UnionFind:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.size = [1] * size

    def find(self, x):
        while x != self.root[x]:
            self.root[x] = self.root[self.root[x]]
            x = self.root[x]
        return x
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.size[rootX] > self.size[rootY]:
                self.root[rootY] = rootX
                self.size[rootX] += self.size[rootY]
            else:
                self.root[rootX] = rootY
                self.size[rootY] += self.size[rootX]


def main():
    n = int(input())
    seq = list(map(int, input().split()))
    forest  = UnionFind(n)
    for i in range(n):
        forest.union(i, seq[i] - 1)
    
    tree_numbers = set()
    for i in range(n):
        tree_numbers.add(forest.find(i))
    
    print(len(tree_numbers))

if __name__ == '__main__':
    main()

To track the valid parenthesis strings, we can use a stack. When encountering an opening bracket $$$($$$, we add its index to the stack. If it's a closing bracket $$$)$$$, we remove the last unpaired opening bracket. Whenever we remove the index of an opening bracket $$$i$$$, we can observe that the substring from $$$s_i$$$ to the current index forms a balanced bracket sequence. This is because when we remove an unpaired opening bracket, the substring between the removed index and the current index has matching opening and closing brackets. Thus, we unite the two indices to mark this valid substring as part of the connected components in Athanasius's graph. This process ensures that we account for all balanced bracket sequences in the graph construction. Additionally, if the current bracket is a closing bracket $$$)$$$ and the next bracket (current index plus one) is an opening bracket $$$($$$, we unite them. This is because the current bracket marks the end of a balanced bracket sequence, and the next bracket marks the start of another balanced bracket sequence, and two balanced brackets together form a balanced bracket sequence.

class UnionFind:
	def __init__(self, size):
    		self.parent = list(range(size))
    		self.rank = [0] * size

	def find(self, element):
            if self.parent[element] != element:
                    self.parent[element] = self.find(self.parent[element])
            return self.parent[element]

	def union(self, element_a, element_b):
            root_a, root_b = self.find(element_a), self.find(element_b)
            if root_a != root_b:
                if self.rank[root_a] > self.rank[root_b]:
                    self.parent[root_b] = root_a
                elif self.rank[root_a] < self.rank[root_b]:
                    self.parent[root_a] = root_b
                else:
                    self.parent[root_a] = root_b
                    self.rank[root_b] += 1

def solve():
	num_pairs = int(input())
	brackets = input().strip()
	uf = UnionFind(2 * num_pairs)
	stack = []
	for i, bracket in enumerate(brackets):
            if bracket == "(":
                    stack.append(i)
            else:
                top = stack.pop()
                uf.union(i, top)
                if i + 1 < 2 * num_pairs and brackets[i + 1] == "(":
                    uf.union(i, i + 1)
	num_connected_components = sum(1 for i, parent in enumerate(uf.parent) if i == parent)
	print(num_connected_components)

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

In this problem we are given a disjoint set union process with $$$n−1$$$ steps, merging $$$n$$$ initial $$$1$$$-element sets into one $$$n$$$-element set. We have to put elements into a linear array of cells, so that the cells to be joined at each step of the process were immediate neighbours (i.e. not separated by other cells).

This problem can be solved in $$$O(nlogn)$$$ via standard disjoint-set data structure, additionally storing lists of elements in each set.

The simplest solution is storing mapping from item to id (representative) of its current set, and the inverse mapping from set to the list of its elements when we have to merge two sets A and B, we make the smaller set part of the larger set and update mappings and concatenating the lists can be done in $$$O(min(|A|,|B|)))$$$.

This gives us $$$O(nlogn)$$$: element can not change its set more than $$$logn$$$ times, because the change leads to (at least) doubling of the element's set size.

import sys
n = int(sys.stdin.readline().strip())
parent = {}
elem = [[] for _ in range(n + 1)]

for i in range(1, n + 1):
    elem[i].append(i)
    parent[i] = i
size = [1] * (n + 1)

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

def union(x, y):
    par_x = find(x)
    par_y = find(y) 
    if par_x != par_y:
        if size[par_x] >  size[par_y]:
            parent[par_y] = par_x
            elem[par_x].extend(elem[par_y])
            size[par_x] += size[par_y]
        else:
            parent[par_x] = par_y
            elem[par_y].extend(elem[par_x])
            size[par_y] += size[par_x]
for _ in range(n - 1):
    x, y = map(int, sys.stdin.readline().strip().split())
    union(x, y)

print(*elem[find(1)])

Let's sort the edges by their weight in descending order and merge the vertices in that order. Whenever you get an already merged vertices, it means the new edge will create cycle; we can update our answer to that edge. Finally, to get the cycle, we can do DFS from either end of that edge until we get to the other end.

from collections import defaultdict
from sys import stdin


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

class DSU:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, v):
        while v != self.p[v]:
            self.p[v] = self.p[self.p[v]]
            v = self.p[v]
        return v
    
    def merge(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.size[pu] < self.size[pv]:
            pu, pv = pv, pu
        self.size[pu] += self.size[pv]
        self.p[pv] = pu
        return True

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    edges = []
    adj = defaultdict(list)
    for __ in range(M):
        u, v, w = map(int, input().split())
        u, v = u - 1, v - 1
        edges.append((w, u, v))
        adj[u].append(v)
        adj[v].append(u)

    edges.sort(key=lambda edge: edge[0], reverse=True)
    dsu = DSU(N)
    for w, u, v in edges:
        if not dsu.merge(u, v):
            ans = (w, u, v)

    min_w, st, end = ans
    stk = [st]


    # DFS to get the cycle
    p = [-1]*N
    p[st] = st
    while stk:
        v = stk.pop()
        for ch in adj[v]:
            if v == st and ch == end: continue
            if ch == end:
                p[ch] = v
                stk = []
                break
            if p[ch] == -1:
                p[ch] = v
                stk.append(ch)
    v = end
    path = []
    while p[v] != v:
        path.append(v)
        v = p[v]
    path.append(st)

    print(min_w, len(path))
    for i in range(len(path)):
        path[i] += 1
    print(*path)

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)
        

Initialize three variables $$$chest$$$, $$$biceps$$$, and $$$back$$$ to $$$0$$$, representing the total repetitions for each muscle group. Loop through the repetitions of exercises, and for each exercise: If the $$$index$$$ is divisible by $$$3$$$ (chest exercises), add the repetitions to the $$$chest$$$ variable. If the $$$index$$$ modulo $$$3$$$ is $$$1$$$ (biceps exercises), add the repetitions to the $$$biceps$$$ variable. If the $$$index$$$ modulo $$$3$$$ is $$$2$$$ (back exercises), add the repetitions to the $$$back$$$ variable Compare the values of $$$chest$$$, $$$biceps$$$, and $$$back$$$ to determine which muscle group has the highest total repetitions.

Time Complexity: $$$O(n)$$$, $$$n$$$ is input size

Space Complexity: $$$O(1)$$$

    def main():
    n = int(input())
    routine = list(map(int, input().split()))

    exercises = [0, 0, 0]
    for turn in range(n):
        exercises[turn % 3] += routine[turn]
    
    if exercises[0] > exercises[1] and exercises[0] > exercises[2]:
        print('chest')
    elif exercises[1] > exercises[2]:
        print('biceps')
    else:
        print('back')
    
if __name__ == '__main__':
    main()

Since we know the start of the path, we can begin our DFS or BFS from 0 while tracking the distance covered so far. Whenever we add a new node to our path, we include the distance between the parent node and the current node, maximizing our answer because we seek the maximum distance. Finally, output the maximum distance that we found.

V = int(input())
adj = [[] for __ in range(V)]

for _ in range(V - 1):
    u, v, c = list(map(int, input().split()))
    adj[u].append((v, c))
    adj[v].append((u, c))

stack = [(0, 0)]
visited = set([0])
max_cost = 0

while stack:
    curr, cost = stack.pop()
    max_cost = max(max_cost, cost)

    for ed, nxt_cost in adj[curr]:
        if ed not in visited:
            visited.add(ed)
            stack.append((ed, cost + nxt_cost))

print(max_cost)

Consider the process from the end, we will "delete" any subtree from the tree, whose color of the ancestor of the highest vertex differs from the color of the highest vertex and the colors of all vertices in the subtree are the same. Thus, we can show that the answer is the number of edges whose ends have different colors + 1.

from collections import deque
from sys import stdin


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

N = int(input())

parents = list(map(int, input().split()))
color = list(map(int, input().split()))

adj = [[] for _ in range(N)]
for ch, p in enumerate(parents, 1):
    adj[p - 1].append(ch)

q = deque([(0, color[0])])
ans = 1

while q:
    v, c = q.popleft()
    for ch in adj[v]:
        q.append((ch, color[ch]))
        ans += (color[ch] != c)
print(ans)

Let's label the diagonal that goes from the top-left to the bottom-right as "diagonal 1" and the diagonal that goes from the bottom-left to the top-right as "diagonal 2". Any cell $$$s_{i,j}$$$ can be visited in these two different diagonals. If the cell was visited with diagonal 1 with a cost of $$$d$$$, all the cells it can reach in diagonal 2 will have a cost of $$$d + 1$$$. Similarly, if the cell was visited with diagonal 2, the cells it can reach on diagonal 1 will have a cost of $$$d + 1$$$. Since the cost of the reachable cells differs based on the diagonal that their parent was visited from, we need to calculate the shortest path for each visited cell for both diagonals.

To calculate the shortest path, we can use BFS starting at the current position of the bishop for both diagonals in our queue. For every element in the queue, if it was visited with diagonal 1, since the cell that visited it will visit all the nodes in that diagonal, we only need to calculate for diagonal 2, and vice versa. While we are calculating for one diagonal, we will calculate for all nodes until we encounter an obstacle, reach a cell that was visited with that diagonal, go out of bounds, or reach the target cell. We return the answer when we reach the target or -1 if we can't reach it.

from collections import deque
from sys import stdin

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

N = int(input())
start_x, start_y = map(int, input().split())
target_x, target_y = map(int, input().split())

start_x -= 1
start_y -= 1
target_x -= 1
target_y -= 1

grid = []
for _ in range(N):
	grid.append(input())

visited = [[[False, False] for _ in range(N)] for _ in range(N)]

queue = deque([(start_x, start_y, 1, 1), (start_x, start_y, -1, 1)])

moves = 0
while queue:
	queue_length = len(queue)
	for _ in range(queue_length):
    	x, y, dx, dy = queue.popleft()
    	if x == target_x and y == target_y:
        	print(moves)
        	exit()
    	visited[x][y][0] = visited[x][y][1] = True
    	is_diagonal = (dx == dy)
   	 
    	for direction in [1, -1]:
        	for i in range(1, 2 * N):
            	nx = x + i * dx * direction
            	ny = y + i * dy * direction
            	if nx < 0 or nx >= N or ny < 0 or ny >= N or grid[nx][ny] == '#' or visited[nx][ny][is_diagonal]:
                	break
            	if not visited[nx][ny][0] and not visited[nx][ny][1]:
                	queue.append((nx, ny, -dx, dy))
            	visited[nx][ny][is_diagonal] = True
	moves += 1
print(-1)

Let's try to solve the problem for odd numbers and then just run the same algorithm with even numbers.

In this problem, we have directed graph consisting of $$$n$$$ vertices (indices of the array) and at most $$$2n−2$$$ edges. Our problem is to find for every vertex the nearest vertex having the opposite parity. Let's try to solve the problem for odd numbers and then just run the same algorithm with even numbers.

We have multiple odd vertices and we need to find the nearest even vertex for each of these vertices. This problem can be solved with the standard and simple but pretty idea. Let's inverse our graph and run a multi-source breadth-first search from all even vertices. The only difference between standard bfs and multi-source bfs is that the second one have many vertices at the first step (vertices having zero distance).

Now we can notice that because of bfs every odd vertex of our graph has the distance equal to the minimum distance to some even vertex in the initial graph. This is exactly what we need. Then just run the same algorithm for even numbers and print the answer.

Time complexity: $$$O(n)$$$ .

import sys
from collections import defaultdict, deque

n = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().strip().split()))

graph = defaultdict(list)

for i in range(n):
    left, right =  i - arr[i], i + arr[i]
    if left > -1:
        graph[left].append(i)
    if right < n:
        graph[right].append(i)
    
def bfs(start, _end):
    _value = [-1] * n
    queue = deque()
    for num in start:
        queue.append(num)
        _value[num] = 0
    while queue:
        cur = queue.popleft()
        for to in graph[cur]:
            if _value[to] == -1:
                _value[to] = _value[cur] + 1
                queue.append(to)
    for num in _end:
        ans[num] = _value[num]

odd = []
even = []

for i, num in enumerate(arr):
    if num % 2:
        odd.append(i)
    else:
        even.append(i)

ans = [-1] * n

bfs(odd, even)
bfs(even, odd)
print(*ans)
   
    

There are two cases we need to check:

1. If there is more than one color in a row. We can check this in many ways. We can put a row in a set and see if it has a length of one. OR, we can check if consecutive colors in a row are the same.
2. If there are consecutive rows with the same color. For each square in a row we can see if it has the same color as the one above it (i.e. on the previous row).

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

n, m = map(int, input().split()) # n = rows, m = cols

flag = []
for _ in range(n):
    row = input()
    flag.append(row)


yes = True
for row in range(n):
    for col in range(1, m):
        # check if we have different colors in a row
        if flag[row][col] !=  flag[row][col - 1]:
            yes = False
            break
        
        # check if we have similar consecutive rows
        if row > 0 and flag[row][col] == flag[row - 1][col]:
            yes = False
            break
    
    if not yes:
        break

print('YES' if yes else 'NO')

Let's look at the degrees of each node.

To form a ring topology, each node must have a degree of $$$2$$$. For a bus topology, the starting and ending nodes must have a degree of $$$1$$$, while the other $$$n - 2$$$ nodes will have a degree of $$$2$$$. In a star topology, one node must have a degree of $$$n - 1$$$, while the other $$$n - 1$$$ nodes will only have a degree of $$$1$$$. If the graph doesn't satisfy one of the above conditions, it is an unknown topology.

n,k = list(map(int,input().split()))
degree = [0 for i in range(n)]
for i in range(k):
    x,y = list(map(int,input().split()))
    x -= 1
    y -= 1
    
    #increase the degrees of both nodes
    degree[x] += 1
    degree[y] += 1

#count the occurrences of the degrees   
count = Counter(degree)

if count[2] == n:
    print('ring topology')
elif count[1] == 2 and count[2] == (n - 2):
    print('bus topology')
elif count[1] == n - 1 and count[n - 1] == 1:
    print('star topology')
else:
    print("unknown topology")

The tree itself is bipartite so we can run a dfs to partition the tree into the $$$2$$$ sets (called bicoloring), We can't add an edge between any $$$2$$$ nodes in the same set and we can add an edge between every $$$2$$$ nodes in different sets, so let the number of nodes in the left set be $$$l$$$ and the number of nodes in the right set be $$$r$$$, The maximum number of edges that can exist is $$$l \cdot r$$$, but $$$n - 1$$$ edges already exist so the maximum number of edges to be added is $$$l \cdot r - (n - 1)$$$.

Time complexity : $$$O(n)$$$.

from sys import stdin


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

N = int(input())
adj = [[] for _ in range(N)]

for _ in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

color = [-1]*N
color[0] = 0
stack = [0]

cnt = [0]*2

while stack:
    v = stack.pop()
    parent_color = color[v]
    child_color = 1 - parent_color
    cnt[parent_color] += 1

    for ch in adj[v]:
        if color[ch] == -1:
            color[ch] = child_color
            stack.append(ch)

print(cnt[0]*cnt[1] - (N - 1))

We know that node $$$1$$$ is the root, hence it always won’t have any ancestor. All other nodes might have sometimes not fixed ancestors, but we know for sure, for beginning, node 1 won’t have any unfixed ancestor (because it won’t have any). So, for beginning we can start with node $$$1$$$. More, suppose node $$$1$$$ is unfixed. The only way to fix it is to make an operation on it. Since it’s unfixed and this is the only way to fix it, you’ll be obligated to do this operation. This means, in an optimal sequence of operations, you’ll be obligated to do this operation, too.

Generally, suppose all ancestors of node $$$x$$$ are fixed. We get the current value of node $$$x$$$ after the operations done on ancestors of $$$x$$$. If the current value is not the expected one, we’ll have to do an operation on node $$$x$$$ (this is the only way to fix the node $$$x$$$). Now, after node $$$x$$$ is fixed, we can process sons of it. This strategy guarantees minimal number of operations, because we do an operation only when we’re forced to do it.

How to get $$$O(N)$$$? Suppose we are at node $$$x$$$ and want to know its current value after operations done for its ancestors. Obviously, it is defined by initial value. If we know number of operations done so far by even levels for its ancestors, number of operations done so far by odd levels and current level, we can determine the current value. Suppose these values are (initial_value, odd_times, even_times, level). We observe that $$$2$$$ operations cancel each other, so we can take this number modulo $$$2$$$. If level % 2 = 0, then only even_times will matter, and current_value = (initial_value + even_times) % 2. Otherwise, current_value = (initial_value + odd_times) % 2.

import sys
from collections import defaultdict
n = int(sys.stdin.readline().strip())
graph = defaultdict(list)

for i in range(n - 1):
    u, v = map(int, sys.stdin.readline().strip().split())
    graph[u].append(v)
    graph[v].append(u)
init = list(map(int, sys.stdin.readline().strip().split()))
goal = list(map(int, sys.stdin.readline().strip().split()))
stack = [(1, 1, 0, 0, 0)]
ans = []

while stack:
    node, par, level, even_op, odd_op = stack.pop()
    if level % 2 == 0:
        if even_op % 2:
            if 1 - init[node - 1] != goal[node - 1]:
                ans.append(node)
                even_op = 1 -even_op
        else:
            if init[node - 1] != goal[node - 1]:
                ans.append(node)
                even_op = 1 -even_op
    else:
        if odd_op % 2:
            if 1 - init[node - 1] != goal[node - 1]:
                ans.append(node)
                odd_op = 1 -odd_op
        else:
            if init[node - 1] != goal[node - 1]:
                ans.append(node)
                odd_op = 1 -odd_op
    for el in graph[node]:
        if el != par:
            stack.append((el, node, level + 1, even_op, odd_op))
print(len(ans))
for a in ans:
    print(a)

Replace the empty cells with walls if they are adjacent to bad cells

Take the escape $$$(n,m)$$$ as the source node to perform depth-first-search (DFS) traversal.

Here’s the step-by-step process:

1. Represent the graph in a grid as a graph representation.
2. Identify all the good, bad, and empty cells.
3. Replace the empty cells with walls if they are adjacent to bad cells.
4. Initialize a visited set to track visited nodes.
5. Take the cell $$$(n,m)$$$ as a source node and perform a depth-first search (DFS) traversal.
6. Once the traversal is finished, check if all good cells exist in the visited set and none of the bad cells exist in the visited set.
7. If some (one or more) good cells do not exist in the visited set, it means we can’t traverse to all the good cells, and all of the good people can’t escape.
8. If some (one or more) bad cells exist in the visited set, it means we can’t block all bad cells, and they can escape.

Time Complexity: $$$O(N * M)$$$, where $$$N$$$ is the number of rows and $$$M$$$ is the number of columns in the maze.

Space Complexity: $$$O(N * M)$$$

def inBound(row, col, n, m, visited, graph):
    return 0 <= row < n and 0 <= col < m and (row, col) not in visited and graph[row][col] != '#'

def main():
     for _ in range(int(input())):
        n, m = map(int, input().split())
        graph = []

        for _ in range(n):
            graph.append(list(input()))
        
        direc = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        good, bad, empty = [], [], []

        # Find the good, bad and empty cells
        for row in range(n):
            for col in range(m):
                if graph[row][col] == 'G':
                    good.append((row, col))
                elif graph[row][col] == 'B':
                    bad.append((row, col))
                elif graph[row][col] == '.':
                    empty.append((row, col))

        # Replace the empty cells with walls if they are adjacent to bad cells
        for row, col in empty:
            for i, j in direc:
                _row, _col = row + i, col + j
                if 0 <= _row < n and 0 <= _col < m and graph[_row][_col] == 'B':
                    graph[row][col] = '#'
                    break 

        # Check if the good cells are reachable and the bad cells are not reachable
        stack = [(n - 1, m - 1)]
        visited = set()
        while stack:
            row, col = stack.pop()
            if not inBound(row, col, n, m, visited, graph):
                continue
            visited.add((row, col))
            for i, j in direc:
                _row, _col = row + i, col + j
                stack.append((_row, _col))

        ans = 'Yes'
        for cell in good:
            if cell not in visited:
                ans = 'No'
                break
        
        for cell in bad:
            if cell in visited:
                ans = 'No'
                break

        print(ans)

if __name__ == '__main__':
    main()

Consider representing the permutation as a directed graph, where an edge exists from node $$$i$$$ to node $$$j$$$ if $$$p_i = j$$$.

Note that all connected components in this graph are simple cycles.

To begin with, let's understand why the string will return to its original form. In fact, the graph that the permutation sets consists of simple cycles and it turns out that after a certain number of operations, each character will return to its place.

Consider each cycle as a string that is cyclically shifted every turn. It may seem that the answer is — lcm (the smallest common multiple) of the cycle lengths, but to become equal to the initial string, it is not necessary to go through the entire cycle. We can calculate the length of the minimum suitable shift $$$k_j$$$ in $$$O(len)$$$ using built in function. Note that after $$$k_j$$$ operations, the cycle will return to its original form and this will happen again after $$$k_j$$$.

operations.

The answer will be lcm of all $$$k_j$$$, since each cycle individually comes to its original form after the number of operations is a multiple of its $$$k_j$$$.

import sys
from math import gcd
 
def solve():
	# Read input for the number of elements, string, and array of integers
	n = int(sys.stdin.readline().strip())
	s = sys.stdin.readline().strip()
	a = list(map(int, sys.stdin.readline().split()))
 
	lcm = 1
	vis = [0] * n
	for i in range(n):
    	if vis[i]:
        	continue
    	cur = []
    	ind = i
    	# Traverse the cycle starting from current index
    	while not vis[ind]:
        	cur.append(s[ind])
        	vis[ind] = 1
        		ind = a[ind] - 1
    	# Create a search string by repeating current cycle twice
    	search = "".join(cur + cur)
    	# Remove the first character (repetition), if we dont remove it the answer will always be 0
    	search = search[1:]  
    	# Find the starting index of the cycle
    	index = search.find("".join(cur)) + 1  
    	lcm = (lcm* index) // gcd(lcm, index)
	return lcm
 
if __name__ == "__main__":
 
	t = int(sys.stdin.readline().strip())
	for _ in range(t):
    	# Call solve() for each test case and print the result
    	result = solve()
    	print(result)

Consider the substring of $$$s$$$ from the second character to the last, or $$$s_2s_3⋯s_n$$$. If it's not palindrome, then the answer must be $$$n−1$$$. What if it's palindrome? This implies that $$$s_2=s_n, s_3=s_{n−1}$$$, and so on. Meanwhile, the fact that $$$s$$$ is palindrome implies $$$s_1=s_n, s_2=s_{n−1}$$$, etc. So we get $$$s_1=s_n=s_2=s_{n−1}=⋯$$$ or that all characters in $$$s$$$ is the same. In this situation, every subsequence of $$$s$$$ is palindrome of course, so the answer should be $$$−1$$$.

import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
    s = sys.stdin.readline().strip()
    if len(set(list(s))) == 1:
        print(- 1)
    else:
        print(len(s) - 1)

Every number can be represented as a product of prime numbers.

The only even prime number is 2.

We divide the given number by 2 until we can't. If the number that we get at the end is 1, that means the number doesn't have an odd divisor except 1. Otherwise, the number we found is either a prime number itself or divisible by another prime number other than 2, which is an odd number.

t = int(input())

for _ in range(t):
    n = int(input())
    while n > 1:
        n /= 2
    
    if n  == 1:
        print("NO")
    else:
        print("YES")
   

If you use LCM function on all numbers, you might get TLE (as the number might get big).

Any positive integer number can be factorized and written as $$$2^a·3^b·5^c·7^d·...$$$

We can multiply given numbers by $$$2$$$ and $$$3$$$ so we can increase $$$a$$$ and $$$b$$$ for them. So we can make all $$$a$$$ and $$$b$$$ equal by increasing them to the same big value (e.g. $$$100$$$). But we can't change powers of other prime numbers so they must be equal from the beginning. We can check it by diving all numbers from input by two and by three as many times as possible. Then all of them must be equal.

Alternative solution is to calculate GCD of given numbers. Answer is "YES" if and only if we can get each number by multiplying GCD by $$$2$$$ and $$$3$$$. Otherwise, some number had different power of prime number other than $$$2$$$ and $$$3$$$.

from sys import stdin


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

N = int(input())
a = list(map(int, input().split()))

for i in range(N):
    while a[i]%2 == 0:
        a[i] //= 2
    while a[i]%3 == 0:
        a[i] //= 3

for i in range(1, N):
    if a[i] != a[0]:
        print("No")
        exit()
print("Yes")

For each index $$$i∈[1,n]$$$ let's try to find which $$$d$$$ we should use in order to make $$$i-th$$$ element of $$$c$$$ equal to zero. If $$$a_i=0$$$, then $$$c_i=b_i$$$ no matter which $$$d$$$ we choose. So we should just ignore this index and add $$$1$$$ to the answer if $$$b_i=0$$$.

Otherwise, we should choose $$$d=−b_i/a_i$$$. Let's calculate the required fraction for each index, and among all fractions find one that fits most indices (this can be done, for example, by storing all fractions in a dictionary).

The only thing that's left to analyze is how to compare the fractions, because floating-point numbers may be not precise enough. Let's store each fraction as a pair of integers $$$(x,y)$$$, where $$$x$$$ is the numenator and $$$y$$$ is the denominator. We should normalize each fraction as follows: firstly, we reduce it by finding the greatest common divisor of $$$x$$$ and $$$y$$$, and then dividing both numbers by this divisor. Secondly, we should ensure that numenator is non-negative, and if numenator is zero, then denominator should also be non-negative (this can be achieved by multiplying both numbers by −1).

import sys
from collections import Counter
from math import gcd
n = int(sys.stdin.readline().strip())
a =list(map(int, sys.stdin.readline().strip().split()))
b =list(map(int, sys.stdin.readline().strip().split()))
count = Counter()
ans = 0
for i in range(n):
    if a[i] == 0:
        if b[i] == 0:
            ans += 1
    else:
        x = b[i] // (gcd(abs(a[i]), abs(b[i])))
        y = a[i] // (gcd(abs(a[i]), abs(b[i])))
        if b[i] < 0:
            x *=  -1
            y *= -1
        elif b[i] == 0 and a[i] < 0:
            y *=  -1
        count[(x, y)] += 1
if len(count) == 0:
    print(ans)
else:
    print(ans + max(count.values()))
    

When is the answer $$$-1$$$?

What Happens when if we want to change all elements to $$$x$$$ and:

1. If $$$a_i > k$$$ and $$$x \leq k$$$:

2. If $$$a_i < k$$$ and $$$x \geq k$$$:

3. If $$$a_i = k$$$ and $$$x \neq k$$$:

Imagine we want to transform every number on the blackboard into $$$x$$$. For each $$$a_i$$$, until $$$a_i$$$ becomes $$$x$$$, we will split $$$a_i$$$ into two parts: $$$a_i + k = x$$$ and $$$a_i + k - x$$$. In other words, $$$a_i = a_i + k - x$$$, and we add $$$x$$$ at the end of the blackboard. For subsequent operations, we focus only on $$$a_i$$$.

We can observe three cases:

1. If $$$a_i > k$$$ and $$$x \leq k$$$: $$$a_i + k - x > a_i$$$, so $$$a_i$$$ keeps increasing, making it unsolvable.
2. If $$$a_i < k$$$ and $$$x \geq k$$$: $$$a_i + k - x < a_i$$$, so $$$a_i$$$ keeps decreasing and won't reach $$$x$$$, also unsolvable.
3. If $$$a_i = k$$$ and $$$x \neq k$$$: if $$$x < k$$$, $$$a_i$$$ keeps increasing. And if $$$x > k$$$, $$$a_i$$$ keeps decreasing and won’t reach $$$x$$$, so it’s unsolvable.

Therefore, for all $$$i, 1 \leq i \leq n$$$ if $$$a_i = k$$$, $$$x$$$ should be $$$k$$$; if $$$a_i > k$$$, $$$x$$$ should be $$$> k$$$; if $$$a_i < k$$$, $$$x$$$ should be $$$< k$$$; otherwise, we won’t have an answer and print $$$-1$$$.

Now, to make the solution efficient, we aim to minimize the number of operations required.

You have to split each $$$a_i$$$ into $$$p_i$$$ pieces equal to $$$x$$$, and their sum must be equal to $$$a_i + k(p_i - 1) = a_i + k \cdot p_i - k $$$

$$$ a_i + k \cdot p_i - k = (a_i - k) + k \cdot p_i $$$

$$$(a_i - k) + k \cdot p_i = x \cdot p_i$$$.

Then, $$$(a_i - k) = (x - k) \cdot p_i$$$, so $$$x - k$$$ must be a divisor of every $$$ a_i - k$$$.

Since we want to minimize the number of operations (i.e., $$$p_i$$$), and since $$$p_i = (a_i - k) / (x - k)$$$, we want to make $$$x - k$$$ the largest number that divides all $$$a_i - k$$$.

import math, sys


def solve():
    n, k = map(int, sys.stdin.readline().strip().split())
    a = list(map(int, sys.stdin.readline().strip().split()))
    
    if a.count(a[0]) == n:
        return 0

    for x in a:
        if (x >= k and a[0] <= k) or (x <= k and a[0] >= k):
            return -1
    gcd = abs(k - a[0])
    for i in a:
   	gcd = math.gcd(gcd, abs(k - i))
    
    ans = 0
    for i in a:
   	ans += (abs(k - i) // gcd - 1)
    
    return ans

if __name__ == "__main__":
    t = int(sys.stdin.readline().strip())
    for _ in range(t):
   	print(solve())

Since we can only utilize either the length or width of all the blankets, the best choice for creating the longest possible rope is to first utilize all the blankets and use the longest side (length or width) of each blanket.

• Time Complexity: $$$O(n)$$$
• Space Complexity: $$$O(1)$$$

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


for _ in range(int(input())):
    n, h = map(int, input().split())
   
    rope = 0
    for i in range(n):
        l, w = map(int, input().split())
        rope += max(l, w)
   
    if rope >= h:
        print('YES')
    else:
        print('NO')

Output binary search.

The key insight is that if we have a wagon size greater than or equal to $$$\max(d_1, d_2, \dots, d_n)$$$, we only need to go once for every village. Hence, the sum of all $$$a_i$$$ is the minimum achievable time to deliver the water with any size.

If $$$\sum_{i=1}^{n} a_i$$$ is already greater than $$$k$$$, we can't make Empress Taytu happy with any size. If not, starting from 1 (left) up to $$$\max(d_1, d_2, \dots, d_n)$$$ (right), we can perform a binary search by checking whether it's achievable with a given size within $$$k$$$ hours.

For a single village, we can calculate the number of trips the wagon has to make by ceil dividing its demand by the wagon size. Then, we can calculate the total time needed for one village by multiplying the number of trips with the time it takes for one trip ($$$a_i$$$). After adding the total time for all villages, we will check if it is less than or equal to $$$k$$$. Overall, the complexity of the checker is $$$O(n)$$$.

The complexity of the binary search algorithm used in this solution is $$$O(\log(\max(d_1, d_2, \dots, d_n)))$$$. Since we need to check for each possible size of the wagon, the overall complexity of the algorithm is $$$O(n \log m)$$$, where $$$m = \max(d_1, d_2, \dots, d_n)$$$.

• Space Complexity: $$$O(1)$$$

from math import ceil
from sys import stdin


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

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())
    d = list(map(int, input().split()))
    a = list(map(int, input().split()))

    if sum(a) > K:
        print(-1)
        continue

    def checker(size):
        time = 0
        for i in range(N):
            time += ceil(d[i]/size)*a[i]
        return time <= K
    
    left = 1
    right = max(d)
    while left <= right:
        mid = left + (right - left)//2
        if checker(mid):
            right = mid - 1
        else:
            left = mid + 1
    print(left)

Observation: After an increment operation, there is always a corresponding decrement operation.

Let's represent the characters with numerical values, such as their ASCII values. During an increment operation, the ASCII value of that character increases by $$$1$$$, and during a decrement operation, it decreases by $$$1$$$. Importantly, after an increment operation, the total sum of ASCII values of the word decreases by $$$1$$$, and after a decrement operation, the total sum increases by $$$1$$$. However, since one operation combines both increment and decrement, the total ASCII sum remains unchanged.

Therefore, to decrypt the message, we only need to check if there exists a substring with a size equal to the size of the sensitive word (let's denote it as $$$m$$$) and the sum of ASCII values of its characters is equal to that of the sensitive word. For this, we can employ a fixed-size sliding window approach with size $$$m$$$.

• Time Complexity: $$$O(n)$$$ where $$$n$$$ is the size of the decrypted message.
• Space Complexity: $$$O(1)$$$

from sys import stdin


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

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    s = input()
    w = input()

    target = 0
    window_sum = 0
    for i in range(M):
        target += ord(w[i])
        window_sum += ord(s[i])
    
    found = False
    for i in range(M, N):
        if window_sum == target:
            found = True
            break
        window_sum += ord(s[i])
        window_sum -= ord(s[i - M])
    
    if window_sum == target or found:
        print("YES")
    else:
        print("NO")

In the first round, each group consists of two teams. Then, in the second round, every two consecutive groups are merged, and so on. This problem resembles a typical divide and conquer approach. Now, the question is, given the left group and the right group, how can we merge them and calculate the number of wins for every team efficiently?

One possible solution is to perform a binary search on the right team for each team in the left group, determining the number of players with strength strictly less than the current player's strength. Repeat this process for all players in the right group. Then, combine the two arrays using two pointers. The time complexity for this solution is $$$O(2^n * log^2(2^n))$$$, where $$$2^n$$$ is the size of the array.

Another approach is to use two pointers to calculate the wins. After calculating and updating both arrays, we can merge them together. This approach has a time complexity of $$$O(2^n*log(2^n)))$$$.

• Space Complexity: $$$O(2^n)$$$

def mergeSort(arr,l,r):
    if l == r:
   	 return
    
    # get the mid point of the current array and merge sort it
    mid = (l + r)//2
    mergeSort(arr,l,mid)
    mergeSort(arr,mid + 1, r)
    # merge the two halves after sorting them and calculating the answer
    merge(arr,l,mid,r)
 
def merge(arr,l,mid, r):
    # wins array to hold the number of wins each team have
 
    wins = [0]*(r - l + 1)
    # array to hold merged list
    merged = []
    
    # calculate the wins for the first group
    ptr = mid + 1
 
    # for every element of the first group
    for i in range(l,mid + 1):
   	 # move the second groups point to an element which is greater or equal to it
  	 
   	 while ptr <= r and arr[ptr][1] < arr[i][1]:
   		 ptr += 1
 
   	 # the total numbe of wins for the current element
   	 #is the nubmer of element in the second group
   	 #that is lower than it
   	 wins[i - l] = ptr - (mid + 1)
 
    # same thing for the second group
    ptr = l
    for i in range(mid + 1,r+1):
   	 while ptr <= mid and arr[ptr][1] < arr[i][1]:
   		 ptr += 1
   	 wins[i - l] = ptr - l
 
    # merge the two groups based on the new value
    pt1 = l
    pt2 = mid + 1
 
    while pt1 <= mid or pt2 <= r:
   	 if (pt2 > r) or (pt1 <= mid and arr[pt1][1] + wins[pt1 - l] < arr[pt2][1] + wins[pt2 - l]):
   		 arr[pt1][1] += wins[pt1 - l]
   		 merged.append(arr[pt1])
   		 pt1 += 1
   	 else:
   		 arr[pt2][1] += wins[pt2 - l]
   		 merged.append(arr[pt2])
   		 pt2 += 1
 
    arr[l:r + 1] = merged
 
 
 
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    arr = [[i,j] for i,j in enumerate(arr)]
    mergeSort(arr,0,2**n - 1)
    ans = [i[1] for i in sorted(arr,key = lambda x: x[0])]
    
    print(*ans)
 
t = int(input())
for _ in range(t):
    solve()

Find the time each gun explodes then you can take the maximum one.

Use monotonic stack to track the damage a gun receives for a gun behind him.

To determine the time it takes for each gun to explode, we can employ a monotonic stack approach. Starting from the first gun, which we know for sure will explode at infinity, we can represent each gun as a tuple $$$(t_i, p_i)$$$, where $$$t_i$$$ is the life of the $$$i$$$-th gun and $$$p_i$$$ is its power. These tuples are then pushed onto the stack.

For each gun $$$i$$$, we can understand that it receives a hit from the last gun on the stack. The damage it receives can be calculated as stack[-1][-1] * (stack[-1][0] - d), where stack[-1][0] and stack[-1][-1] represent the life and power of the gun at the end of the stack, respectively. Here, $$$d$$$ represents the duration of gun $$$i$$$ before it encounters the gun at the end of the stack. If the gun at the end of the stack cannot reduce the health of gun $$$i$$$ to zero, we decrement the received damage with the gun's health and pop from the stack.

• Time Complexity: $$$O(n)$$$
• Space Complexity: $$$O(n)$$$

import sys
from math import ceil, inf
input = lambda : sys.stdin.readline().strip()


for t in range(int(input())):
    n = int(input())
    health = list(map(int, input().split()))
    power = list(map(int, input().split()))


    stack = [(inf, power[0])]
    ans = 0
    for i in range(1, n):
        duration = 0
        while health[i] - (stack[-1][0] - duration)*stack[-1][-1] > 0:
            t, p = stack.pop()


            health[i] -= (t-duration)*p
            duration += (t-duration)
       
        duration += ceil(health[i]/stack[-1][-1])
        stack.append((duration, power[i]))
        ans = max(ans, duration)
   
    print(ans)

Topic: Greedy

What is the maximum number of points for the $$$(k + 1)$$$-th team?

If $$$k$$$ equals $$$n$$$ (the last position), the answer is $$$0$$$ since $$$0$$$ points are needed to secure the last position.

Let's calculate for other positions:

Firstly, let's determine the maximum number of points the $$$(k + 1)$$$-th team can have. To maximize this, the first $$$(k + 1)$$$ teams will win all matches against the remaining $$$n - (k + 1)$$$ teams, resulting in the first $$$(k + 1)$$$ teams having points equal to $$$(n - (k + 1)) \cdot 3$$$.

Now, our task is to maximize the points of both the $$$k$$$-th and $$$(k + 1)$$$-th teams. To achieve this, we focus on the remaining matches involving the $$$k$$$ teams (excluding the $$$(k + 1)$$$-th team). Since we aim to maximize the minimum points within these $$$k$$$ teams, we need to maximize the minimum points in the remaining matches.

For $$$k = 2$$$, there is only $$$k - 1 = 1$$$ match remaining for a team. If a team wins, the other team will have $$$0$$$ points, resulting in a minimum of $$$0$$$ points. However, to maximize the minimum points, it's better if the match ends in a draw, resulting in a minimum of $$$1$$$ point. For $$$k = 3$$$, there are $$$k - 1 = 2$$$ matches remaining for a team. If a team wins one and loses one, all teams will have $$$3$$$ points, resulting in a minimum of $$$3$$$ points. However, if one team wins both matches, the minimum points will be $$$0$$$ or $$$1$$$.

We observe that if a match ends in a win or a loss, the overall points are $$$3$$$, whereas if it is a draw, it is $$$2$$$ (with $$$1$$$ point for each team). We aim to avoid losing points in a draw. The issue arises when there is only one match remaining and it's either a win or a loss, resulting in a minimum of $$$0$$$ points. However, with a draw, the minimum is $$$1$$$ point. For two matches, we can achieve an overall of $$$6$$$ points with wins, distributing $$$3$$$ points to each team.

Hence, to maximize the minimum points within the $$$k$$$ teams, we have $$$(k - 1)$$$ matches for each team. If $$$(k - 1)$$$ is even, the team wins $$$\frac{k - 1}{2}$$$ matches and loses $$$\frac{k - 1}{2}$$$ matches. If $$$(k - 1)$$$ is odd, the team wins $$$\frac{k - 2}{2}$$$ matches, loses $$$\frac{k - 2}{2}$$$ matches, and draws $$$1$$$ match. Generally (for even or odd), the points it can obtain is $$$\left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2$$$.

Now, both the $$$k$$$-th and $$$(k + 1)$$$-th teams have $$$(n - (k + 1)) \cdot 3 + \left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2$$$ points. The only match remaining is between them. We can secure the $$$k$$$-th team in the $$$k$$$-th position by ensuring it wins the match against the $$$(k + 1)$$$-th team. However, if both teams have the same number of points, they will both secure the $$$k$$$-th position. Therefore, to minimize the points required to guarantee the $$$k$$$-th position, the match should end in a draw. Finally, the $$$k$$$-th team will have $$$(n - (k + 1)) \cdot 3 + \left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2 + 1$$$ point.

• Time Complexity: $$$O(1)$$$
• Space Complexity: $$$O(1)$$$

from sys import stdin


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

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())

    if N == K:
        print(0)
        continue

    ans = (N - (K + 1))*3 + ((K - 1)//2)*3 + (K - 1)%2 + 1
    print(ans)

Scan the digits from left to right. Insert the new digit before the first digit smaller than it because placing it before a smaller digit maximizes the overall value by ensuring that the new digit occupies a higher significant position in the resulting number. This positioning ensures that the number formed is as large as possible. If no smaller digit is found, append the new digit at the end.

for i in range(int(input())):
    n, d = list(map(int, input().split()))
    s = input()
 
    flag = True
    for i in range(len(s)):
        if int(s[i]) < d:
            print(s[:i] + str(d) + s[i:])
            flag = False
            break
    
    if flag:
        print(s + str(d))

We can precalculate a prefix sum array $$$sum$$$ over the piles. I.e. $$$sum_{i} = a_{1} + a_{2} + ... + a_{i}$$$. We can now perform a binary search for each query $$$q_{i}$$$ to find the result $$$j$$$ with the properties $$$sum_{j - 1} < q_{i}$$$ and $$$sum_{j} ≥ q_{i}$$$.

Time complexity $$$O(n + m·log(n))$$$

n = int(input())
a = list(map(int, input().split()))
m = int(input())
q = list(map(int, input().split()))


prefix_sum = [0]
for pile in a:
    prefix_sum.append(prefix_sum[-1] + pile)


for label in q:
    low = 0
    high = n

    while low <= high:
        mid = low + (high - low)//2
        if prefix_sum[mid] < label:
            low = mid + 1
        
        else:
            high = mid - 1
    
    print(low)

We are given $$$s$$$ spaceships, each with an attacking power $$$a_i$$$, and $$$b$$$ bases, each with a defensive power $$$d_j$$$ and gold $$$g_j$$$.

We are asked to output for each spaceship, the sum of the gold of the bases it can attack, that is: $$$res(i) = \sum g_j, ∀_j : a_i ≥ d_j$$$

An $$$O(sb)$$$ solution would not pass the time limit. Instead the intended solution is to sort the bases by their defensive power, and the ships by their attacking power, in increasing order. Then, we can use the fact that if a weaker ship can attack a base, so can a stronger ship. This way we only have to iterate once over all the bases. The overall complexity reduces to $$$O((s) log (s) + (b) log (b))$$$.

Another solution of that would pass the time limit would be to sort the bases in increasing order of their defensive strength. Then, compute the prefix sum of the gold (that is, $$$prefix[j]$$$ would hold the sum of gold of all the bases from $$$0...j$$$). Finally, for each ship, perform a binary search over the prefix sum and the bases arrays to compute how much gold it could steal.

Overall complexity: $$$O((s) log (b) + (b) log (b))$$$.

from bisect import bisect_right
from sys import stdin


def input(): return stdin.readline()[:-1]


S, B = map(int, input().split())
a = list(map(int, input().split()))
dg = []
for _ in range(B):
    d, g = map(int, input().split())
    dg.append((d, g))

dg.sort()
pref_sum = [0]
cur_sum = 0
ds = []
for d, g in dg:
    ds.append(d)
    cur_sum += g
    pref_sum.append(cur_sum)

ans = []
for ai in a:
    idx = bisect_right(ds, ai)
    ans.append(pref_sum[idx])
print(*ans)

Since we are sure that if $$$x$$$ can be the answer to the problem, then every value below $$$x$$$ can be the answer, So we can use binary search on the answer to solve the problem.

To check whether some value $$$x$$$ can be a valid solution, we have to sum all our gains that come from values greater than $$$x$$$. We can calculate the gain for one value by taking its difference with $$$x$$$. Let's say its difference is $$$diff$$$. Our gain will be $$$diff - (diff * k / 100)$$$. We can do the same for all values greater than $$$x$$$ and add the results; that will be our total gain. We also need to calculate the total need. We can do that for values less than $$$x$$$ by taking their difference with $$$x$$$ and adding those values. Then, we can compare if our total gain is greater than or equal to our total need. In that case, it can be considered valid.

import sys
n, k = map(int, sys.stdin.readline().strip().split())
nums = list(map(int, sys.stdin.readline().strip().split()))

def chekcker(x):
    gain = 0
    need = 0
    for num in nums:
        if num > x:
            diff = num - x
            gain += (diff - diff * k / 100)
        if num < x:
            need  += (x - num)
    
    return gain >= need

low = min(nums)
high = max(nums)
while high  - low > 10 ** -7:
    mid = (high + low) / 2
    if chekcker(mid):
        low = mid
    else:
        high = mid
print(high)

We can Break two sections of the wall in three different ways.

1. Break two sections with more than one section between them.i.e., $$$(i, j), i + 2 < j$$$.

2. Break two sections with only one section between them, i.e., $$$(i, i+ 2)$$$.

3. Break two sections with no section between them, i.e., $$$(i, i + 1)$$$.

We can Break two sections of the wall in three different ways.

1. Break two sections with more than one section between them.i.e., $$$(i, j), i + 2 < j$$$.

2. Break two sections with only one section between them, i.e., $$$(i, i+ 2)$$$.

3. Break two sections with no section between them, i.e., $$$(i, i + 1)$$$.

If there is more than one section between the two we want to break, then any shot hits only one of these sections, so each shot should be aimed at one of those sections, and we break them independently. Since one doesn’t affect the other, we could just pick the two minimum and try to break them independently, let's say their strength is $$$a_i$$$ and $$$a_j$$$, the total is going to be $$$\lceil\frac{a_i}{2}\rceil + \lceil\frac{a_j}{2}\rceil$$$.

If there is only one section between them, if we shoot at the section between them, we deal 1 damage to both sections; if we shoot at one of those sections, we deal 2 damage to it and 0 damage to the other section. So, each shot distributes 2 damage between these two sections the way we want to distribute it, and the number of shots required to break these two sections is $$$\lceil\frac{a_i + a_{i+2}}{2}\rceil$$$.

The case when we try to break two adjacent sections is the trickiest one. Let's say that these sections are $$$i$$$ and $$$i+1$$$, $$$x=\max(a_i, a_{i+1})$$$, and $$$y=\min(a_i, a_{i+1})$$$. If we target one of these sections, we deal 2 damage to it and 1 damage to the other section. Let's try to run the following algorithm: shoot at the section with higher durability until both of them break. It can be slow, but we can see that after the first $$$x-y$$$ shots, the durabilities of the sections become equal, and each pair of shots after that deals 3 damage to both sections. So, we can model the first $$$x-y$$$ shots, subtract $$$2(x-y)$$$ from $$$x$$$ and $$$(x-y)$$$ from $$$y$$$, and then we'll need $$$\lceil\frac{x+y}{3}\rceil$$$ shots. The only case when this doesn't work is if we break both sections before we equalize their durabilities; it means that $$$2y \leq x$$$, and we need to do only $$$\lceil\frac{x}{2}\rceil$$$ shots.

from math import ceil
def check(a, mid):
	n = len(a)
	local_min = a[0]

	for i in range(1, n - 1):
    	   x = max(a[i], a[i - 1])
    	   y = min(a[i], a[i - 1])

    	   # case one using the two min values
    	   if (ceil(local_min / 2) + ceil(a[i] / 2)) <= mid:
        	return True

    	   # case two using i, i + 2
    	   elif (ceil((a[i - 1] + a[i + 1]) / 2)) <= mid:
        	return True

    	   # case 3 using i, i + 1
    	   elif max(ceil(x / 2), ceil((x + y) / 3)) <= mid:
        	return True

    	   # update local min
    	   local_min = min(local_min, a[i])

	return False


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	low, high, ans = 1, max(a), float('inf')
	a.append(1e7)
	while low <= high:
    	   mid = low + (high - low) // 2
    	   if check(a, mid):
        	ans = min(ans, mid)
        	high = mid - 1
    	   else:
        	low = mid + 1

	print(ans)


if __name__ == "__main__":
	solve()

To solve this problem you need to understand that friends must meet in the middle point of the given points, so friends who live in the leftmost and in the rightmost points must go to the middle point. Because of that the answer equals to $$$max(x_1, x_2, x_3) - min(x_1, x_2, x_3)$$$.

Total complexity: $$$O(n)$$$

import sys
a,b, c = map(int, sys.stdin.readline().strip().split())
print(max(a,b,c) - min(a, b, c))

Idea is a simple greedy, buy needed meat for i - th day when it's cheapest among days 1, 2, ..., n..

import sys
n = int(sys.stdin.readline().strip())
mi  =  float("inf")
ans= 0
for _ in range(n):
    a, b  = map(int, sys.stdin.readline().strip().split())
    mi = min(mi, b)
    ans += (a*mi)
print(ans)

Since $$$1≤a_i≤10^3$$$ for all $$$i$$$, let set $$$a_0=0$$$ and $$$a_n+1=1001$$$. For every $$$i$$$,$$$j$$$ such that $$$0≤i<j≤n+1$$$, if $$$a_j−j=a_i−i$$$ then we can erase all the elements between $$$i$$$ and $$$j$$$ (not inclusive). \

import sys
n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))
nums = [0] + nums + [1001]
ans = 0
left = 0
for  i in range(1, n + 2):
    if nums[i] - nums[i - 1]> 1:
        left = i
    ans = max(ans, i - left - 1)
print(ans)

The first observation is that the new Hamming distance may not be less than the old one minus two, since we change only two characters. So the task is to actually determine, if we can attain decrease by two, one or can’t attain decrease at all.

The decrease by two is possible if there are two positions with the same two letters in two strings but that appear in different order (like “double” <-> “bundle”).

If there are no such positions, then we just need to check that we may decrease the distance. This can be done by just “fixing” the character that stands on the wrong position, like in “permanent” <-> “pergament” (here n stands in wrong pair with m, and there is also unmatched m, so we may fix this position).

Otherwise, the answer is to keep everything as it is. Implementation can be done by keeping for each pair (x, y) of symbols position where such pair appears in S and T and then by carefully checking the conditions above.

from sys import stdin


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

N = int(input())
s = input()
t = input()

humming = 0
mismatches = {}
t_mismatches = {}
s_mismatches = {}

two = None
one = None

for i in range(N):
    if s[i] != t[i]:
        if not two:
            if (t[i], s[i]) in mismatches:
                two = (mismatches[(t[i], s[i])], i)
            elif not one:
                if s[i] in s_mismatches:
                    one = (s_mismatches[s[i]], i)
                elif t[i] in t_mismatches:
                    one = (t_mismatches[t[i]], i)
                t_mismatches[s[i]] = i
                s_mismatches[t[i]] = i

            mismatches[(s[i], t[i])] = i
        humming += 1

if two:
    print(humming - 2)
    print(two[0] + 1, two[1] + 1)
elif one:
    print(humming - 1)
    print(one[0] + 1, one[1] + 1)
else:
    print(humming)
    print(-1, -1)

First, let's find the longest regular bracket Substring using a stack. To do that, Let's introduce a variable to store the index of the last unregular substring and let's iterate through the string. If the character is "$$$($$$", we will append its index to the stack. If the character is "$$$)$$$", we have three cases:

1. If the stack is empty, it means the substring up to this point is not regular, and we will update our 'last unregular' variable to this index.
2. After popping the last value from the stack, if the stack is empty, we know the substring that starts from the last unregular $$$index + 1$$$ to this position is regular.
3. After popping the last value from the stack, if there is still a value on the stack, it means the substring that starts from the $$$index$$$ (that is on the top of the stack) $$$+ 1$$$ to this position is regular. So, every time we find a regular sequence, we will take the maximum. The next step is to count how many regular substrings there are with this maximum value, using the same approach again

s = input()
longest = 0
stack = []
last = -1
for i, ch in enumerate(s):
    if ch == "(":
        stack.append(i)
    else:
        if stack:
            stack.pop()
            if stack:
                longest = max(longest, i - stack[-1])
            else:
                longest = max(longest, i - last)
        else:
            last = i
res= 0
last = -1
stack = []
for i, ch in enumerate(s):
    if ch == "(":
        stack.append(i)
    else:
        if stack:
            stack.pop()
            if stack:
                if (i - stack[-1]) == longest:
                    res += 1
            else:
                if i - last == longest:
                    res += 1
        else:
            last = i
if longest == 0:
    print(0, 1)
else:
    print(longest, res)

If the total number of occurrences of some character $$$c$$$ is not a multiple of $$$n$$$, then it is impossible to make all $$$n$$$ strings equal — because then it is impossible for all $$$n$$$ strings to have the same number of $$$c$$$.

On the other hand, if the total number of occurrences of every character $$$c$$$ is a multiple of $$$n$$$, then it is always possible to make all $$$n$$$ strings equal. To achieve this, for every character $$$c$$$ we move exactly ((the total number of occurrences of $$$c$$$) / $$$n$$$) characters $$$c$$$ to the end of each string, and by the end we will have all n strings equal each other.

# it's recommended to use sys.stdin.readline().strip() for faster input processing
import sys
from collections import Counter
t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    strings = []
    for i in range(n):
        strings.append(sys.stdin.readline().strip())
    count =Counter()
    for i in range(n):
        for ch in strings[i]:
            count[ch] += 1
    ans = "YES"
    for key in count:
        if count[key] % n:
            ans = "NO"
            break
    print(ans)

To solve this problem efficiently, we can use stack. Here's the step-by-step process:

Initialize an empty stack. Iterate through each character in the input string. If the stack is not empty and the current character is equal to the top of the stack, pop the top character from the stack. Otherwise, push the current character onto the stack. After iterating through all characters, join the characters remaining in the stack to form the final string without adjacent duplicates.

Time Complexity: $$$O(n)$$$, where n is the length of the input string.

Space Complexity: $$$O(n)$$$ This is because the stack can potentially store all characters of the string in the worst case scenario (no adjacent duplicates to remove).

chars = input()
stack = []

for char in chars:
    if stack and stack[-1] == char:
        stack.pop()
    else:
        stack.append(char)
print(''.join(stack))

What's the lower bound for the amount of blocks for the answer to be YES?

Check the predicate for every prefix.

Let's consider the smallest amount of blocks we need to make the first $$$i$$$ heights ascending. As heights are non-negative and ascending the heights should look like $$$0,1,2,3,...,i−1$$$, so the minimum sum is $$$\frac{(i−1) \cdot i}{2}$$$. It turns out that this is the only requirement. If it's not the case for every prefix the answer is NO because we can't make some prefix ascending. Otherwise the answer is YES because you can move the blocks right till there is at least $$$i$$$ blocks in the $$$i$$$-th stack and this would make the heights ascending.

from sys import stdin

def input(): return stdin.readline()[:-1]


T = int(input())
for _ in range(T):
    N = int(input())
    a = list(map(int, input().split()))
    need = 0
    have = 0
    ans = True
    for j in range(N):
        need += j
        have += a[j]
        if have < need:
            ans = False
    if ans:
        print("YES")
    else:
        print("NO")

It looks like Tikursew should only reorder the boxes when he has to (i.e. he gets a remove operation on a number which isn't at the top of the stack). The proof is simple: reordering when Tikursew has more boxes is always not worse than reordering when he has less boxes, because Tikursew can sort more boxes into the optimal arrangement. Therefore, our greedy algorithm is as follows: simulate all the steps until we need to reorder, and then we resort the stack in ascending order from top to bottom.

This has complexity $$$O(n^2 log n)$$$. However, we can speed this up if we note that whenever we reorder boxes, any box currently on the stack can be put in an optimal position and we can pretty much forget about it. So whenever we reorder, we can just clear the stack as well and continue. This gives us $$$O(n)$$$ complexity because every element is added and removed exactly once.

# If you use input() to get input, you might encounter TLE (Time Limit Exceeded). Instead,
# it's recommended to use sys.stdin.readline().strip() for faster input processing
import sys
n = int(sys.stdin.readline().strip())
stack = []
ans = 0
cur = 1
for _ in range(2 * n):
    s = list(map(str, sys.stdin.readline().strip().split()))
    if s[0][0] == 'a':
        stack.append(int(s[1]))
    else:
        if stack:
            if cur != stack[-1]:
                ans += 1
                stack = []
            else:
                stack.pop()
        cur += 1
print(ans)

What if the maximum number is at the front of the deque?

It can be noted that if the deque has the largest element of the deque in the first position, then during the next operations it will remain in the first position, and the second one will be written to the end each time, that is, all the elements of the deque starting from the second will move cyclically left.

• Let's go over the deque and find the largest element by value. We will perform the operation described in the statements until the maximum position is in the first position and save the elements in the first and second positions by the operation number. In order to pre-calculate all pairs until the moment when the maximum position is found, it is enough to make no more than one pass through the deque, since in the worst case, the maximum element can be located at the end of the deque.
• Denote as $$$maxIndex$$$ the position of the maximum element. Then if $$$m_{j} < maxIndex$$$, simply return a pair of numbers from the pre-calculated array.
• Otherwise $$$A$$$ is equal to the maximum element, and $$$B$$$ is equal to the deque element with the index $$$((m_{j} − (maxIndex + 1)) \mod{(n−1)}) + 1$$$ in $$$0-indexing$$$ (since we performed the operations until the moment when the maximum position is in the first position, this maximum element is now recorded in the first position).

from collections import deque

n, q = map(int, input().split())
a = deque(map(int, input().split()))
if not q:
    exit()

queries = []
for _ in range(q):
    queries.append(int(input()))

# precalc stores the pre-calculated values of A and B until the maximum number is fixed at the first position
precalc = [[0, 0] for _ in range(n + 1)]
_max = max(a)
maxIndex = 0 

while a[0] != _max:
    A, B = a.popleft(), a.popleft()
    precalc[maxIndex + 1] = [A, B]
    if A > B:
        a.appendleft(A)
        a.append(B)
    else:
        a.appendleft(B)
        a.append(A)

    maxIndex += 1

ans = []
for m in queries:
    if m > maxIndex:
        ans.append([_max, a[(m - (maxIndex + 1))%(n - 1) + 1]])
    else:
        ans.append(precalc[m])
    

for pair in ans:
    print(*pair)

For each $$$i$$$, find the largest $$$j$$$ that $$$a_j$$$ < $$$a_i$$$ and show it by $$$l_i$$$ (if there is no such $$$j$$$, then $$$l_i = 0$$$).

Also, find the smallest $$$j$$$ that $$$a_j < a_i$$$ and show it by $$$r_i$$$ (if there is no such $$$j$$$, then $$$r_i = n + 1$$$).

This can be done in $$$O(n)$$$ with a stack. Consider that you are asked to print $$$n$$$ integers, $$$ans_1, ans_2, ..., ans_n$$$. Obviously, $$$ans_1 ≥ ans_2 ≥ ... ≥ ans_n$$$.

For each $$$i$$$, we know that $$$a_i$$$ can be minimum element in groups of size $$$1, 2, ..., r_i - l_{i - 1}$$$.

Se we need a data structure for us to do this:

We have array $$$ans_1, ans_2, ..., ans_n$$$ and all its elements are initially equal to $$$0$$$. Also, $$$n$$$ queries. Each query gives $$$x, val$$$ and want us to perform $$$ans_1 = max(ans_1, val), ans_2 = max(ans_2, val), ..., ans_x = max(ans_x, val)$$$. We want the final array.

This can be done in $$$O(n)$$$ with a maximum prefix sum (keeping maximum instead of sum).

Time complexity: $$$\mathcal{O}(n)$$$.

from sys import stdin


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

N = int(input())
a = list(map(int, input().split()))

ans = [0]*N

mono_stk = [(0, -1)]
for i, n in enumerate(a):
    while mono_stk[-1][0] >= n:
        prev_n, prev_i = mono_stk.pop()
        prev_prev_i = mono_stk[-1][1]
        prev_window = i - prev_prev_i - 2
        ans[prev_window] = max(ans[prev_window], prev_n)
    cur_window = i - mono_stk[-1][1] - 1
    ans[cur_window] = max(ans[cur_window], n)
    mono_stk.append((n, i))

while len(mono_stk) > 1:
    n, i = mono_stk.pop()
    prev_i = mono_stk[-1][1]
    cur_window = N - prev_i - 2
    ans[cur_window] = max(ans[cur_window], n)

prev = min(a)
for i in range(N - 1, -1, -1):
    ans[i] = max(prev, ans[i])
    prev = ans[i]
print(*ans)   

Let's sort the numbers in ascending order. It becomes immediately clear that it is not profitable for us to increase the numbers that are equal to the last number (the maximum of the array). It turns out that every time you need to take such a subset of the array, in which all the numbers, except the maximums. And once for each operation, the numbers in the subset are increased by one, then how many times can the operation be performed on the array? Accordingly $$$max(a)−min(a)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    print(max(nums) - min(nums)) 

We can iterate through the elements of $$$a$$$ and $$$b$$$ simultaneously. For each element $$$a_i$$$, we consider the following cases:

1. If $$$a_i = b_i$$$, no operation is needed, and we move on to the next element.

2. If $$$a_i > b_i$$$, we need to decrease $$$a_i$$$ to match $$$b_i$$$. Since the elements of $$$a$$$ can only be $$$-1$$$, $$$0$$$, or $$$1$$$, the only way to decrease $$$a_i$$$ is by finding an element $$$a_j < i$$$ such that $$$a_j = -1$$$. Subtracting $$$1$$$ from $$$a_i$$$ and adding $$$1$$$ to $$$a_j$$$ does not change the sum of $$$a_i$$$ and $$$a_j$$$, but it decreases $$$a_i$$$ by $$$1$$$. If such an element $$$a_j$$$ does not exist, then it's impossible to transform $$$a$$$ into $$$b$$$.

3. If $$$a_i < b_i$$$, we need to increase $$$a_i$$$ to match $$$b_i$$$. Similarly, the only way to increase $$$a_i$$$ is by finding an element $$$a_j < i$$$ such that $$$a_j = 1$$$. Adding $$$1$$$ to $$$a_i$$$ and subtracting $$$1$$$ from $$$a_j$$$ does not change the sum of $$$a_i$$$ and $$$a_j$$$, but it increases $$$a_i$$$ by $$$1$$$. If such an element $$$a_j$$$ does not exist, then it's impossible to transform $$$a$$$ into $$$b$$$.

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
    
	vals = set()
	ans = True
	for i in range(n):
    	if a[i] != b[i]:
        	if b[i] - a[i] > 0:
            	if 1 not in vals:
                	ans = False
                	break
        	else:
            	if -1 not in vals:
                	ans = False
                	break
    	vals.add(a[i])
	print("YES" if ans else "NO")

First, we can filter out the numbers that have appeared at least $$$k$$$ times in the array and sort them in ascending order.

We will keep track of the start and end of the current range as we iterate through the sorted list. Additionally, we keep track of the maximum range found so far.

Next, We maintain a current range while iterating through the sorted list of numbers. If a number $$$a_i$$$​ is consecutive to the previous number $$$a_{i−1}$$$ $$$i.e.$$$ $$$( a_i = a_{i -1} + 1)$$$, it is part of the current range. Otherwise, $$$a_i​$$$ marks the start of a new range. We keep track of the maximum range found so far as we iterate through the list.

But, when using a hash table data structure, there's a risk of encountering test cases deliberately crafted to induce collisions. In such scenarios, the worst-case time complexity for retrieval and insertion operations could O(n), impacting the overall time complexity of the solution, which could become O(n2). To remove this risk ,one possible solution is employing XOR with a random number during both insertion and retrieval from the hash table. By XORing each number with a randomly generated value before inserting it into the hash table, we can create unique hash values for each number. This process helps distribute the numbers evenly across the hash table. Similarly, during retrieval, XORing the search key with the same random number allows us to accurately locate the corresponding entry in the hash table.

from collections import Counter
from random import randint

for _ in range(int(input())):
   n, k = map(int, input().split())
   numbers = list(map(int, input().split()))
   rand = randint(10000, 10**10)
   c = Counter([a ^ rand for a in numbers])
   filtered_numbers = [a ^ rand for a in c.keys() if c[a] >= k]
   filtered_numbers.sort()
 
   max_span = -1
   start = end = None
   current_start = current_end = None

   for num in filtered_numbers:
   	if current_end is None or num != current_end + 1:
       	if current_start is not None and current_end is not None:
           	span = current_end - current_start
           	if span > max_span:
               	max_span = span
               	start = current_start
               	end = current_end

       	current_start = current_end = num
   	else:
       	current_end = num

   if current_start is not None and current_end is not None:
   	span = current_end - current_start
   	if span > max_span:
       	max_span = span
       	start = current_start
       	end = current_end
   if start:
   	print(start, end)
   else:
   	print(-1)

Let's consider two sequences of digits: $$$e_1,e_2,…,e_k$$$ and $$$o_1,o_2,…,o_m$$$, there $$$e_1$$$ is the first even digit in $$$a$$$, $$$e_2$$$ is the second even digit and so on and $$$o_1$$$ is the first odd digit in $$$a$$$, $$$o_2$$$ is the second odd digit and so on.

Since you can't swap digits of same parity, the sequence $$$e$$$ of even digits of $$$a$$$ never changed. Sequence $$$o$$$ of odd digits of $$$a$$$ also never changed. So the first digit in the answer will be equal to $$$e_1$$$ or to $$$o_1$$$. And since we have to minimize the answer, we have to chose the $$$min(e_1,o_1)$$$ as the first digit in answer and them delete it from the corresponding sequence (in this way sequence $$$e$$$ turn into $$$e_2,e_3,…,e_k$$$ or sequence $$$o$$$ turn into $$$o_2,o_3,…,o_m$$$). Second, third and followings digits need to choose in the same way.

from sys import stdin


def input(): return stdin.readline()[:-1]

T = int(input())
for _ in range(T):
    num = input()
    evens = []
    odds = []
    for digit in num:
        if int(digit)%2 == 1:
            odds.append(digit)
        else:
            evens.append(digit)
    
    ans = []
    p1 = p2 = 0
    len_evens = len(evens)
    len_odds = len(odds)
    while p1 < len_evens and p2 < len_odds:
        if evens[p1] < odds[p2]:
            ans.append(evens[p1])
            p1 += 1
        else:
            ans.append(odds[p2])
            p2 += 1
    ans.extend(evens[p1:])
    ans.extend(odds[p2:])
    
    print(*ans, sep="")

To ensure that all rows and columns form palindromes, each cell $$$a_{i,j}$$$ should be equal to $$$a_{n−i−1,j}$$$, $$$a_{n−i−1,j}$$$​, $$$a_{i,m−j−1}$$$, as well as $$$a_{n−i−1,m−j−1}$$$.

so the problem is reduced to finding the optimal number for each four of numbers (maybe less for some positions in the matrix). This number is the median of these numbers (the average of the sorted set). This can be proved by induction. Here is the link for the proof. The answer will be the sum of the differences between the median of the "four" and each number in the "four" for all "fours".

for _ in range(int(input())):
   n,m = map(int,input().split())
   mat = [list(map(int,input().split())) for i in range(n)]
   tot = 0
   for i in range(n):
   	for j in range(m):
       	mid_point = sorted([mat[i][j],mat[i][m-j-1],mat[n-i-1][j],mat[n-i-1][m-j-1]])[2]
       	tot += abs(mat[i][j]-mid_point)
   print(tot)    

Make a copy of the array $$$s$$$: call it $$$t$$$. Sort $$$t$$$ in non-decreasing order, so that $$$t_1$$$ is the maximum strength and $$$t_2$$$ — the second maximum strength.

Then for everyone but the best person, they should compare with the best person who has strength $$$t_1$$$. So for all $$$i$$$ such that $$$s_i≠t_1$$$, we should output $$$s_i−t_1$$$. Otherwise, output $$$s_i−t_2$$$ — the second highest strength, which is the next best person.

t = int(input())
for _ in range(t):
    n = int(input())
    s = list(map(int, input().split()))
    t = sorted(s)
    for i in range(n):
        if s[i] != t[-1]:
            s[i] = s[i] - t[-1]
        else:
            s[i] = s[i] - t[-2]
    print(*s)

We precalculate some array $$$A_{i}$$$, that $$$A_{i} = 1$$$, if $$$s_{i} = s_{i + 1}$$$, else $$$A_{i} = 0$$$. Now for any query ($$$l$$$, $r$), we need to find sum of $$$A_{i}$$$, such that $$$(l ≤ i < r)$$$. It has not become a range sum query problem. To solve this problem, we can precalculate a prefix sum array $$$Sum$$$, where $$$Sum_{i} = A_{1} + A_{2} + ... + A_{i}$$$. Then the sum of the interval ($$$l$$$, $$$r$$$) is $$$Sum_{r} — Sum_{l-1}$$$.

s = input()
m = int(input())
queries = []

for _ in range(m):
    queries.append(list(map(int, input().split())))

pref = [0]
for indx in range(len(s) - 1):
    if s[indx] == s[indx + 1]:
        pref.append(pref[-1] + 1)
    
    else:
        pref.append(pref[-1])


for left, right in queries:
    print(pref[right - 1] - pref[left - 1])

Sort the array in ascending order.

To solve this problem efficiently, we can use a sorting and greedy approach. Here's the step-by-step process:

1. Sort the given input array in ascending order.
2. It iterates through the sorted array. For each value, check if the current serving time is greater than the total waiting time of the current person (the sum of the previous satisfied customer's serving time ) . If it is, it means the person is satisfied. Otherwise, the person is not satisfied and will leave the queue automatically.

Time Complexity: O(n), n is the size of the queue.

Space Complexity: O(1)

    n = int(input())
    time = sorted(map(int, input().split()))

    ans = waitTime = 0
    for i in range(n):
        if waitTime <= time[i]:
            ans += 1
            waitTime += time[i]
    
    print(ans)

If there is at least a prefix or a suffix with non-positive sum, we can delete that prefix/suffix and end up with an array with sum $$$≥$$$ the sum of the whole array. So, if that's the case, the answer is "NO".

Otherwise, all the segments that Aman can choose will have a sum $$$<$$$ than the sum of the whole array because the elements that are not in the segment will always have a strictly positive sum. So, in that case, the answer is "YES".

Time complexity: O(n)

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    total_sum = 0
    for num in a:
        total_sum += num
        if total_sum <= 0:
            return False
    total_sum = 0
    for i in range(n - 1, -1, -1):
        total_sum += a[i]
        if total_sum <= 0:
            return False
    return True

T = int(input())
for _ in range(T):
    if solve():
        print("YES")
    else:
        print("NO")

Let's prove that for an array $$$a$$$ that was created by using a number of operations, with a sum of elements $$$s$$$ we can add into $$$a$$$ any number $$$x$$$ $$$(1≤x≤s)$$$.

Suppose that it is true that in the array $$$a$$$ with some length $$$l$$$ we introduce a number $$$x$$$ $$$(1≤x≤suma)$$$. Then after introducing we can create using the initial elements of the array any number $$$b$$$ $$$(1≤b≤suma)$$$ and using the element $$$x$$$ and some subset of the initial elements we can create any number $$$b$$$ $$$(x≤b≤suma+x)$$$, and because $$$x≤suma$$$ we proved that for the new array of length $$$l+1$$$ we can still create any number between $$$1$$$ and $$$suma+x$$$.

So we just need to verify if our array satisfies the above condition. We sort the array and check for every element whether the total sum so far is less than the current element. If that is the case for any of the elements our answer is ‘NO’ otherwise ‘YES’.

t = int(input())
for i in range(t):
    n = int(input())
    nums = list(map(int,input().split()))
    nums.sort()
    pos = 1
    if nums[0] != 1:
        pos = 0
    total = 1
    for i in range(1,n):
        if nums[i] > total:
            pos = 0
            break
        total += nums[i]
    if pos:
        print("YES")
    else:
        print("NO")

How would you solve count subarrays with sum equal to $$$k$$$ optimally using the concept of prefix sum?

We will keep track of the prefix product.

Lets call the current prefix product $$$currentPrefix$$$.
If $$$currentPrefix$$$ is positive,

1. If we have seen another positive prefix before, it means that the segment of the currentPrefix excluding the previous prefix would give us a positive product, because $$$(+)*(+) = (+)$$$. The amount of previous positive prefixes tells us how many segments with positive product we can have at the current prefix.
2. Similarly, if we have seen a negative prefix before, it means that the remaining part of the current segment has to be negative, because $$$(-)*(-) = (+)$$$.

In the same manner, if $$$currentPrefix$$$ is negative,

1. We increment the negative product segments by the number of previous positive prefixes, because $$$(+)*(-) = (-)$$$.
2. We increment the positive product segments by the number of previous negative prefixes, because $$$(-)*(+) = (-)$$$.

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

pos_prefixes = 1 # as an identity, to take into account a whole prefix
neg_prefixes = 0

pos_seg_count = 0
neg_seg_count = 0

prefix = 1

for num in a:
    prefix *= (num//abs(num)) # we only want the sign, not the magnitude

    if prefix > 0:
        pos_seg_count += pos_prefixes
        neg_seg_count += neg_prefixes
        pos_prefixes += 1
        
    else:
        pos_seg_count += neg_prefixes
        neg_seg_count += pos_prefixes
        neg_prefixes += 1

print(neg_seg_count, pos_seg_count)

Make a copy of the array $$$s$$$: call it $$$t$$$. Sort $$$t$$$ in non-decreasing order, so that $$$t_1$$$ is the maximum strength and $$$t_2$$$ — the second maximum strength.

Then for everyone but the best person, they should compare with the best person who has strength $$$t_1$$$. So for all $$$i$$$ such that $$$s_i≠t_1$$$, we should output $$$s_i−t_1$$$. Otherwise, output $$$s_i−t_2$$$ — the second highest strength, which is the next best person.

t = int(input())
for _ in range(t):
    n = int(input())
    s = list(map(int, input().split()))
    t = sorted(s)
    for i in range(n):
        if s[i] != t[-1]:
            s[i] = s[i] - t[-1]
        else:
            s[i] = s[i] - t[-2]
    print(*s)

We precalculate some array $$$A_{i}$$$, that $$$A_{i} = 1$$$, if $$$s_{i} = s_{i + 1}$$$, else $$$A_{i} = 0$$$. Now for any query ($$$l$$$, $r$), we need to find sum of $$$A_{i}$$$, such that $$$(l ≤ i < r)$$$. It has not become a range sum query problem. To solve this problem, we can precalculate a prefix sum array $$$Sum$$$, where $$$Sum_{i} = A_{1} + A_{2} + ... + A_{i}$$$. Then the sum of the interval ($$$l$$$, $$$r$$$) is $$$Sum_{r} — Sum_{l-1}$$$.

s = input()
m = int(input())
queries = []

for _ in range(m):
    queries.append(list(map(int, input().split())))

pref = [0]
for indx in range(len(s) - 1):
    if s[indx] == s[indx + 1]:
        pref.append(pref[-1] + 1)
    
    else:
        pref.append(pref[-1])


for left, right in queries:
    print(pref[right - 1] - pref[left - 1])

Sort the array in ascending order.

To solve this problem efficiently, we can use a sorting and greedy approach. Here's the step-by-step process:

1. Sort the given input array in ascending order.
2. It iterates through the sorted array. For each value, check if the current serving time is greater than the total waiting time of the current person (the sum of the previous satisfied customer's serving time ) . If it is, it means the person is satisfied. Otherwise, the person is not satisfied and will leave the queue automatically.

Time Complexity: O(n), n is the size of the queue.

Space Complexity: O(1)

    n = int(input())
    time = sorted(map(int, input().split()))

    ans = waitTime = 0
    for i in range(n):
        if waitTime <= time[i]:
            ans += 1
            waitTime += time[i]
    
    print(ans)

If there is at least a prefix or a suffix with non-positive sum, we can delete that prefix/suffix and end up with an array with sum $$$≥$$$ the sum of the whole array. So, if that's the case, the answer is "NO".

Otherwise, all the segments that Aman can choose will have a sum $$$<$$$ than the sum of the whole array because the elements that are not in the segment will always have a strictly positive sum. So, in that case, the answer is "YES".

Time complexity: O(n)

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    total_sum = 0
    for num in a:
        total_sum += num
        if total_sum <= 0:
            return False
    total_sum = 0
    for i in range(n - 1, -1, -1):
        total_sum += a[i]
        if total_sum <= 0:
            return False
    return True

T = int(input())
for _ in range(T):
    if solve():
        print("YES")
    else:
        print("NO")

Track the maximum value encountered.

Initializes the answer $$$ans$$$ as $$$YES$$$ assuming initially that it's possible to reach every position. Iterates over the given input array in the sequence (except the last one) using a loop. At each position, update the maximum value encountered so far $$$currMax$$$ among the first $$$i$$$ elements. If $$$currMax$$$ becomes greater than $$$(i + 1)$$$ (indicating there's a gap between the maximum reachable position and the current position), and the corresponding rule for that position is $$$0$$$, update the answer to $$$NO$$$ and break out of the loop.

Time Complexity: O(n), n is the size of the input array. Space Complexity: O(1)

    n = int(input())
    nums = list(map(int, input().split()))
    rules = input()

    ans = 'YES'
    currMax = 0
    for i in range(n - 1):
        currMax = max(currMax, nums[i])
        if currMax > i + 1 and rules[i] == '0':
            ans = 'NO'
            break

    print(ans)

How would you solve count subarrays with sum equal to $$$k$$$ optimally using the concept of prefix sum?

We will keep track of the prefix product.

Lets call the current prefix product $$$currentPrefix$$$.
If $$$currentPrefix$$$ is positive,

1. If we have seen another positive prefix before, it means that the segment of the currentPrefix excluding the previous prefix would give us a positive product, because $$$(+)*(+) = (+)$$$. The amount of previous positive prefixes tells us how many segments with positive product we can have at the current prefix.
2. Similarly, if we have seen a negative prefix before, it means that the remaining part of the current segment has to be negative, because $$$(-)*(-) = (+)$$$.

In the same manner, if $$$currentPrefix$$$ is negative,

1. We increment the negative product segments by the number of previous positive prefixes, because $$$(+)*(-) = (-)$$$.
2. We increment the positive product segments by the number of previous negative prefixes, because $$$(-)*(+) = (-)$$$.

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

pos_prefixes = 1 # as an identity, to take into account a whole prefix
neg_prefixes = 0

pos_seg_count = 0
neg_seg_count = 0

prefix = 1

for num in a:
    prefix *= (num//abs(num)) # we only want the sign, not the magnitude

    if prefix > 0:
        pos_seg_count += pos_prefixes
        neg_seg_count += neg_prefixes
        pos_prefixes += 1
        
    else:
        pos_seg_count += neg_prefixes
        neg_seg_count += pos_prefixes
        neg_prefixes += 1

print(neg_seg_count, pos_seg_count)

Let's see how to check if all digits of $$$x$$$ are different. Since there can be only $$$10$$$ different numbers($$$0$$$ to $$$9$$$) in single digit, you can count the occurrences of $$$10$$$ numbers by looking all digits of $$$x$$$. You can count all digits by using modulo $$$10$$$ or changing whole number to string.

For example, if $$$x = 1217$$$, then occurrence of each number will be $$$[0, 2, 1, 0, 0, 0, 0, 1, 0, 0]$$$, because there are two $$$1$$$s, single $$$2$$$ and single $$$7$$$ in $$$x$$$. So $$$1217$$$ is invalid number.

Now do the same thing for all $$$x$$$ where $$$l \le x \le r$$$. If you find any valid number then print it. Otherwise print $$$-1$$$.

Time complexity is $$$O((r-l) \log r)$$$.

# Return if given number's digits are distinct.
def is_distinct(x):
    return len(set(str(x))) == len(str(x))

L, R = map(int, input().split())

found = False
for i in range(L, R+1):
    if is_distinct(i):
        found = True
        print(i)
        break
    
if not found:
    print(-1)

Sort the array in ascending order.

To solve this problem efficiently, we can use a sorting and greedy approach. Here's the step-by-step process:

1. Sort the list of programming skills in ascending order.
2. Initialize two pointers, $$$start$$$ and $$$end$$$, both pointing to the beginning of the sorted list.
3. Iterate over the list using pointer $$$start$$$, and for each student skill $$$(skills[start])$$$, move pointer $$$(end)$$$ forward until the difference between the current skill `$$$(skills[end])$$$ and $$$(skills[start])$$$ exceeds 5.
4. At each iteration, update the maximum number of students in a balanced team $$$(maxNum)$$$ by taking the maximum between the current value of $$$maxNum$$$ and the difference between $$$end$$$ and $$$start$$$.
5. Finally, output the maximum number of students in a balanced team $$$(maxNum)$$$.

Time Complexity: Sorting the list takes O(n log n) time. The iteration over the sorted list takes O(n) time. Thus, the overall time complexity is O(n log n).

Space Complexity: Sorting requires O(1)

    n = int(input())
    skills = sorted(map(int, input().split()))

    maxNum = 0
    end = 0

    for start in range(n):

        while end < n and skills[end] - skills[start] <= 5:
            end += 1
        maxNum = max(maxNum, end - start)

    print(maxNum)

Lets look at the optimal answer. It will contain several segment of increasing beauty and between them there will be drops in the beautifulness.to determine number of such segments. From the way we construct answer it is easy to see that the number of segments always equal to the maximal number of copies of one value. Obviously we can't get less segments than that and our algorithm gives us exactly this number. Total complexity: $$$O(n)$$$

from collections import Counter
n = int(input())
nums = list(map(int, input().split()))
count = Counter(nums)
ans = 0
while len(count) > 0:
    ans += (len(count) - 1)
    keys = list(count.keys())
    for key in keys:
        count[key] -= 1
        if count[key] == 0:
            del count[key]
print(ans)

On the constraints, the size of the array cannot be larger than 2000.

We can use two pointers (non-linearly). One starts from the zero, and stores the numbers in a set (left set) to mark them as seen. For every position on the left, as long as the items in the left set are unique, we use a right pointer and move backwards as long as the number on the right pointer satisfies following conditions:

• It is not in the left set.
• The number is not repeated on the right (we can use a right set for every left).

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

min_segment = float('inf')
left_seen = set()
a.append(0) # appended to handle edge cases (to avoid writing if conditions) 

for left in range(n):

    num = a[left]
    right_seen = set()

    for right in range(n, left - 1, -1):
        if a[right] in left_seen or a[right] in right_seen:
            break

        right_seen.add(a[right])
        min_segment = min(min_segment, right - left)
    
    if num in left_seen:
        break

    left_seen.add(num)
    

print(min_segment)

Think about small substrings.

What are the strings that satisfy the given conditions?

If you got Wrong Answer on test $$$2$$$, then you're probably not checking $$$7$$$ length strings.

The following are all the possible minimal substrings (there aren't that many) which satisfy the given conditions: "aa", "aba", "aca", "abca", "acba", "abbacca", "accabba". Any other string that satisfies the condition contains at least one of these as a substring, and hence is not the optimal substring for the answer.

Claim: If a substring exists which satisfies the given conditions, then the length of the shortest such substring is at most $$$7$$$. Otherwise the solution does not exist.

Proof: Let us consider that the solution exists. We will try to prove this by breaking this into the following cases:

Case 1: There exist two such "a" whose distance is less than or equal to $$$2$$$, where distance is the absolute difference of their indices.

• In this case where there are two such "a" whose distance is less than $$$2$$$, then either these two "a" are present consecutive or there is only one single letter between these two "a". All these minimal substrings are "aa", "aba" and "aca" which satisfies all the given conditions. Hence we can say that the shortest length of such substring that satisfies the given conditions is at most $$$3$$$ in this case.

Case 2: There exists no two such "a" whose distance is less than or equal to $$$2$$$.

• In this case all the consecutive occurrences of "a" are present at a distance at least $$$3$$$. Then in order for the number of "a" to be bigger than that of "b" and "c" the string must look like "a??a??a??a??a".
• Let us define "??" as a block. Now if there is any block consisting of different characters $$$i.e$$$ "bc" or "cb" then the substring "a??a" will satisfy all the given conditions and hence the minimal length will be $$$4$$$.
• Notice that there must be at least one block of "bb" and at least one block of "cc", otherwise "a" will not be in a majority. Hence, there must exist 2 consecutive blocks equal to "bb" and "cc" or "cc" and "bb" in the string (otherwise all blocks would be of the same character). Hence we can pick the substring "abbacca" or "accabba" which satisfies the given conditions. The minimal length is, therefore, $$$7$$$ in this case.

Therefore we can say that the shortest length of such substring that satisfies the given conditions is at most $$$7$$$ in this case.

Thus, it suffices to only check all substrings of length up to $$$7$$$ and find the smallest among them that satisfies the given conditions (or report that it does not exist).

Time Complexity: $$$\mathcal{O}(7⋅n)$$$

from sys import stdin


def input(): return stdin.readline()[:-1]


T = int(input())

for _ in range(T):
    N = int(input())
    s = input()

    if "aa" in s:
        print(2)
    elif "aba" in s or "aca" in s:
        print(3)
    elif "abca" in s or "acba" in s:
        print(4)
    elif "abbacca" in s or "accabba" in s:
        print(7)
    else:
        print(-1)

Let's sort the array in nonincreasing order. Now the answer is some of the first flash-drives. Let's iterate over array from left to right until the moment when we will have the sum at least m. The number of elements we took is the answer to the problem. Complexity: $$$O(nlogn)$$$.

n = int(input())
m = int(input())
flash = []
for _ in range(n):
    val = int(input())
    flash.append(val)
flash.sort(reverse=True)
cur = 0
for i in range(n):
    cur += flash[i]
    if cur >= m:
        print(i + 1)
        break

The goal is to find a greater element for each element in our array. So, consider sorting the array to achieve this.

If our array consists of unique elements, the answer will always be $$$N - 1$$$ (where $$$N$$$ is the size of our array).

Preserve the larger numbers to represent their preceding larger numbers.

As mentioned in the hints, If our array consisted of unique elements, the answer would always be N — 1, where N is the size of our array. Here’s why:

• After sorting the array, for every number in our array, the next number can always replace it because it will always be greater than it, except for the last (maximum) number.
• So, we can safely replace all elements except the largest one.

Handling Duplicates:

To handle duplicates, we’ll use two pointers: left and right. Left represents the current smaller number that needs to be replaced. Right represents the current immediate larger element compared to the first number. We’ll greedily choose the next immediate larger element for the smaller number. This ensures that we have a larger number greater than the smaller one to replace it.

N = int(input())
arr = list(map(int, input().split()))
arr.sort()
left = 0

for right in range(N):
    if arr[right] > arr[left]:
        left += 1
       
print(left)

Suppose we have an array $$$a$$$ that we want to construct, with elements $$$a_{1},a_{2},…,a_{n}$$$. To simplify the process, let's assume that the elements of a are sorted in non-decreasing order, meaning $$$a_{1}≤a_{2}≤⋯≤a_{n}$$$.

Let's start with $$$a_{1}$$$. Since the elements of $$$a$$$ are sorted, the pairs $$$(a_{1},a_{2}),(a_{1},a_{3}),…,(a_{1},a_{n})$$$ will have $$$a_{1}$$$ as the smallest element in each pair. Therefore, the number of occurrences of $$$a_{1}$$$ in array b will be $$$n−1$$$.

Moving on to $$$a_{2}$$$, we already know that $$$a_{1}$$$ appears $$$n−1$$$ times in $$$b$$$. Since the elements of $$$a$$$ are sorted, all pairs involving $$$a_{2}$$$ will have $$$a_{2}$$$ as the second smallest element. This means $$$a_{2}$$$ will appear $$$n−2$$$ times in array $$$b$$$.

We continue this process for each element $$$a_{i}$$$ in $$$a$$$. The number of occurrences of $$$a_{i}$$$ in array $$$b$$$ will be $$$n−i$$$.

We can't determine the exact value of $$$a_{n}$$$, because it won't be written to array $$$b$$$. Therefore, for an we can choose any number in the range $$$[a_{n−1};10^9]$$$.

In case there are multiple elements $$$b_{i}$$$ in array $$$b$$$ that satisfy the condition for a particular $$$a_{i}$$$, we choose the smallest $$$b_{i}$$$. This greedy approach works, because we are constructing $$$a$$$ in non-decreasing order.

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int,input().split()))
    nums.sort()
    ans = []
    c = n - 1
    i = 0
    while i < len(nums):
     
        ans.append(nums[i])
        i += c
        c -= 1
 
    ans.append(10**9)
    print(*ans)

For every number in a sequence, we can store the sum of the sequence with that number removed in a hashmap.

Storing a sum with a number removed is computed for every number, so the space complexity will be linear. As a value for each difference we will store the index of the sequence and the index of the sum within the sequence. This way if we find the same sum in another sequence, we will have access to the required answer.

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

encountered_sums = {}

for j in range(k):
    sequence = sequences[j]
    seq_tot = sum(sequence)

    for y in range(len(sequence)):
        dif = seq_tot - sequence[y]

        # if the difference exists it shouldn't be in the same sequence
        if dif in encountered_sums and encountered_sums[dif][0] != j:
            # i = the sequence index where we saw this dif before, x the index of the number removed to get this sum in sequence i
            i, x = encountered_sums[dif] 
            print('YES')
            print(i + 1, x + 1)
            print(j + 1, y + 1)
            exit()

        # store the sequence sum with the current number excluded
        encountered_sums[dif] = (j, y)

print('NO')

To determine the order of removals, we start from the end of the string. The last character represents the latest removed character. Moving backward, when encountering a character not seen before, it implies that this character was removed in the next step. Thus, we initiate the process from the last character, and each new character encountered denotes the one removed prior. Once we establish this order, we need to reverse it. Now that we have the removal order, the next step is to verify whether the resulting string could have originated from that order. To check this, we first need to assess whether the character counts are valid. If a character was removed first, its actual occurrence in the original string should match its count in the given string. If removed second, the real occurrence in the original string is the count in the given string divided by 2, and so on. After obtaining the counts for each character in the original string, if the sum yields a non-integer number, the given string is invalid. However, if it results in an integer, we proceed to check if the given string can be derived from the first $$$k$$$ characters of the original string $$$k$$$ representing the sum of the counts. To do this, we perform the same operations on the word containing the first $$$k$$$ characters of the given string. After obtaining the result, we compare it with the given string. If they match, we can confidently print the obtained removal order and the original string (which is the first $$$k$$$ characters of the given string). If not, we print $$$-1$$$ as the given string is not valid.

t = int(input())
for _ in range(t):
   s = input()
  
   arr = []
   got = set()
   count = Counter(s)
   for i in s[::-1]:
       if i not in got:
           arr.append(i)
       got.add(i)
   arr.reverse()
   occur = []
   pos = 1
   for i in range(len(arr)):
       occur.append(count[arr[i]] / (i + 1))
   left = 0
   if math.ceil(sum(occur)) != int(sum(occur)):
       pos = 0
 
   if pos:
       ans = ""
       cur = s[:int(sum(occur))]
       j = 0
  
       while cur:
           ans += cur
           stk = ""
           for i in cur:
               if i != arr[j]:
                   stk += i
           cur = stk
           j += 1
       if ans != s:
           pos = 0
   if pos:
       print(s[:int(sum(occur))],"".join(arr))
   else:
       print(-1)

To solve the problem we need to find the character with the highest alphabetical order in our string, since Abenezer will need at least that alphabet size and won't need more. To do this iterate through the string and find the character with the highest alphabetical order. Output the maximum alphabetical order found. The solution can be done in $$$O(n)$$$.

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    ma = 0
    for ch in s:
        ma = max(ma, ord(ch))
    print(ma - 96)
  

What if we use a fixed size sliding window?

To obtain a segment of $$$k$$$ cells with black color, we must paint all the white cells within that segment black. We then consider all segments of length $$$k$$$ (there are only $$$n - k$$$ such segments) and choose the one with the fewest white cells on it. Implementing this involves using a sliding window of size $$$k$$$. Since we have only two colors, we can simplify our implementation by only using two pointers.

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


    recolored = n
    black_count = 0
    left = 0
   
    for right, color in enumerate(s):
        black_count += (color == 'B')


        if right - left + 1 == k:
            recolored = min(recolored, k - black_count)
            black_count -= (s[left] == 'B')
            left += 1


    print(recolored)

Underline every letter $$$w$$$, so that it can't be mistaken with $$$vv$$$. The string splits into segments of letters $$$v$$$. Out of each pair of consecutive letters $$$v$$$ at least one should be underlined. So for the minimum amount you can underline either all the odd positions of the segment or all the even ones. Thus, if the length of the segment is $$$len$$$ , then $$$⌊len/2⌋$$$ underlined letters is enough.

t = int(input())
for _ in range(t):
    s = input()

    left = 0
    underline = 0

    for right in range(len(s)):
        if s[right] == 'w':
            if s[left] == 'w':
                underline += 1
                
            else:
                underline += 1 + (right - left)//2

            left = right + 1
        
    if left < len(s):
        underline += (len(s) - left)//2
    
    print(underline)

Because the constraints are small, brute forcing it is possible. So, check if every number inside your array can be expressed as a subarray sum.

Use two pointers technique to efficiently find subarrays with sums equal to the current element.

We're given an array of numbers and we're trying to find out how many special numbers are there in the array. A special number is one that can be expressed as the sum of two or more consecutive numbers in the array. To solve this, we'll go through each number in the array one by one and check if it satisfies the condition of being special. We'll do this by considering it as a potential sum of consecutive numbers starting from the beginning of the array. We'll keep track of the sum of these consecutive numbers as we move through the array.

Here's how it works: Imagine we're at a certain number in the array. We start considering it as the sum of consecutive numbers starting from the first number in the array. As we move forward, we add each number to our running sum. If at any point our running sum equals the current number, and we've considered at least two numbers in the subarray (because a single number by itself doesn't count as a sum of consecutive numbers), then we've found a special number. We'll count this and move on to the next number in the array.

By repeating this process for each number in the array, we'll be able to count all the special numbers. This approach allows us to efficiently find special numbers without needing to store all the possible consecutive sums separately. It's a straightforward method that checks each number individually to determine if it's special.

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


    count = 0
    for num in a:
        left = 0
        run_sum = 0
        for right in range(n):
            run_sum += a[right]
            while run_sum > num:
                run_sum -= a[left]
                left += 1           
            if run_sum == num and left < right:
                count += 1
                break
   
    print(count)

Consider sorting the array.

A sliding window where the right most number minus the left most number is $$$<= 2$$$ could tell us a lot of information.

For a window size $$$m$$$, where $$$m >= 3$$$, if the right most number minus the left most number is $$$<= 2$$$, how many triples can we form if we take the current right element as the maximum value? Lets label the numbers in the window as $$$w_{1}, w_{2}, w_{3}, ..., w_{m - 2}, w_{m - 1}, w_{m}$$$. Now if we fix the maximum value to be $$$w_{m}$$$:

• For $$$w_{m - 1}$$$ as the middle value, we can take the remaining $$$m - 2$$$ numbers, $$$w_{1}, w_{2}, w_{3}, ..., w_{m - 2}$$$, to be the minimum number.
• For $$$w_{m - 2}$$$ as the middle value, we can take the remaining $$$m - 3$$$ numbers, $$$w_{1}, w_{2}, w_{3}, ..., w_{m - 3}$$$, to be the minimum number.

.
.
.
• For $$$w_{2}$$$ as the middle value, we can take the remaining number $$$w_{1}$$$ to be the minimum number.

From the above possible middle values, in total, we can form $$$(m - 2) + (m - 3) + ... + 1$$$ triples.

Hence, with the current right value we can form $$$(m - 2)*(m - 1)/2$$$ triples.

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

    left = 0
    triples = 0

    for right in range(n):
        num = a[right]
        while num - a[left] > 2:
            left += 1

        win_size = right - left + 1            
        if win_size >= 3:
            triples += (win_size - 2)*(win_size - 1)//2

    print(triples)

Let's see how to check if all digits of $$$x$$$ are different. Since there can be only $$$10$$$ different numbers($$$0$$$ to $$$9$$$) in single digit, you can count the occurrences of $$$10$$$ numbers by looking all digits of $$$x$$$. You can count all digits by using modulo $$$10$$$ or changing whole number to string.

For example, if $$$x = 1217$$$, then occurrence of each number will be $$$[0, 2, 1, 0, 0, 0, 0, 1, 0, 0]$$$, because there are two $$$1$$$s, single $$$2$$$ and single $$$7$$$ in $$$x$$$. So $$$1217$$$ is invalid number.

Now do the same thing for all $$$x$$$ where $$$l \le x \le r$$$. If you find any valid number then print it. Otherwise print $$$-1$$$.

Time complexity is $$$O((r-l) \log r)$$$.

# Return if given number's digits are distinct.
def is_distinct(x):
    return len(set(str(x))) == len(str(x))

L, R = map(int, input().split())

found = False
for i in range(L, R+1):
    if is_distinct(i):
        found = True
        print(i)
        break
    
if not found:
    print(-1)

If s is palindromic initially, we can operate on the interval [1,n], the answer is $$$Yes$$$.

Let's consider the other case. In a palindrome s, for each $$$i$$$ in $$$[1,⌊n/2⌋]$$$, $$$s_i=s_{n−i+1}$$$ must hold. For those $$$i$$$, we may check whether $$$s_i=s_{n−i+1}$$$ is true in the initial string. For all the illegal positions $$$i$$$, the operation must contain either $$$i$$$ or $$$n+1−i$$$, but not both. For the legal positions, the operation must contain neither of $$$i$$$ nor $$$n+1−i$$$, or both of them.

If the illegal positions is continuous (which means that they are $$$l,l+1,…,r−1,r$$$ for some $$$l$$$ and $$$r$$$), we may operate on the interval $$$[l,r]$$$ (or $$$[n+1−r,n+1−l]$$$), making the string palindromic. The answer is $$$Yes$$$.

Otherwise, there must be some legal positions that lie between the illegal ones. Suppose the illegal positions range between $$$[l,r]$$$ (but not continuous). This interval covers all the legal positions that lie between the illegal ones but does not cover their symmetrical positions. Thus, such kind of operation will produce new illegal positions. In other words, there are no valid operations in this situation. The answer is $$$No$$$.

Total complexity: $$$O(n)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    found = False
    last = None
    ans = "Yes"
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            if not found:
                found = True
            else:
                if i - 1 != last:
                    ans = "No"
                    break
            last = i
            
    print(ans)

Lets look at the optimal answer. It will contain several segment of increasing beauty and between them there will be drops in the beautifulness.to determine number of such segments. From the way we construct answer it is easy to see that the number of segments always equal to the maximal number of copies of one value. Obviously we can't get less segments than that and our algorithm gives us exactly this number. Total complexity: $$$O(n)$$$

from collections import Counter
n = int(input())
nums = list(map(int, input().split()))
count = Counter(nums)
ans = 0
while len(count) > 0:
    ans += (len(count) - 1)
    keys = list(count.keys())
    for key in keys:
        count[key] -= 1
        if count[key] == 0:
            del count[key]
print(ans)

On the constraints, the size of the array cannot be larger than 2000.

We can use two pointers (non-linearly). One starts from the zero, and stores the numbers in a set (left set) to mark them as seen. For every position on the left, as long as the items in the left set are unique, we use a right pointer and move backwards as long as the number on the right pointer satisfies following conditions:

• It is not in the left set.
• The number is not repeated on the right (we can use a right set for every left).

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

min_segment = float('inf')
left_seen = set()
a.append(0) # appended to handle edge cases (to avoid writing if conditions) 

for left in range(n):

    num = a[left]
    right_seen = set()

    for right in range(n, left - 1, -1):
        if a[right] in left_seen or a[right] in right_seen:
            break

        right_seen.add(a[right])
        min_segment = min(min_segment, right - left)
    
    if num in left_seen:
        break

    left_seen.add(num)
    

print(min_segment)

What can we say about the position of the maximum elements relative to $$$[l,r]$$$?

Iterate over the middle maximum element and choose $$$[l,r]$$$ greedily.

First we need to notice, that two of the maximums are at the ends of $$$[l,r]$$$, otherwise we can move one of the boundaries closer to the other and improve the answer.

Using this observation we can reduce the problem to the following: choose three indices $$$l<m<r$$$, such that $$$b_l+b_m+b_r−(r−l)$$$ is maximum.

Now, let's iterate over the middle index $$$m$$$ and rewrite the function as $$$b_m+(b_l+l)+(b_r−r)$$$. We can see, that values in the braces are pretty much independent — on of them depends only on the index $$$l$$$ and the second one depends only on the index $$$r$$$ . So, for a given $$$m$$$ we can choose the numbers $$$l$$$ and $$$r$$$ greedily! To make it fast enough we can pre calculate the prefix maximum for the array $$$b_l+l$$$ and the suffix maximum for array $$$b_r−r$$$.

Total complexity: $$$O(n)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    prefix = []
    suffix = []
    for i in range(n):
        prefix.append(nums[i] + i)
        suffix.append(nums[i] - i)
    for i in range(1, n):
        prefix[i] = max(prefix[i], prefix[i - 1])
        suffix[n - i - 1] = max(suffix[n - i - 1], suffix[n - i])
    ans = float("-inf")
    for i in range(1, n - 1):
        ans  = max(ans, prefix[i - 1] + nums[i] + suffix[i + 1])
    print(ans)

Let's sort the array in nonincreasing order. Now the answer is some of the first containers. Let's iterate over array from left to right until the moment when we will have the sum at least m. The number of elements we took is the answer to the problem.

Complexity: $$$\mathcal{O}(nlogn)$$$.

n = int(input())
m = int(input())
flash = []
for _ in range(n):
    val = int(input())
    flash.append(val)
flash.sort(reverse=True)
cur = 0
for i in range(n):
    cur += flash[i]
    if cur >= m:
        print(i + 1)
        break

Note that for each question, the resulting array is

So, the sum of the elements of the new array after each question is

We can compute $$$a_1+⋯+a_{l−1}$$$ and $$$a_{r+1}+⋯+a_n$$$ in $$$\mathcal{O}(1)$$$ time by precomputing the sum of all prefixes and suffixes, or alternatively by using the prefix sums technique. So we can find the sum each time in $$$\mathcal{O}(1)$$$ per question, and just check if it's odd or not. The time complexity is $$$\mathcal{O}(n+q)$$$.

from itertools import accumulate
from sys import stdin


# Fast input for python. Note that it gives you the input with the newline character, '\n'
# This may cause a problem on string problems. In that case, use stdin.readline()[:-1] to strip the last character('\n')
def input(): return stdin.readline()


T = int(input())
for _ in range(T):
    N, Q = map(int, input().split())
    a = list(map(int, input().split()))

    pref_sum = list(accumulate(a, initial=0))

    for __ in range(Q):
        l, r, k = map(int, input().split())
        left_sum = pref_sum[l - 1]
        right_sum = pref_sum[-1] - pref_sum[r]
        middle_sum = k*(r - l + 1)
        total_sum = left_sum + middle_sum + right_sum

        if total_sum%2 == 1:
            print("YES")
        else:
            print("NO")  

The key observation is that to choose an element $$$b_i$$$, we need to consider all elements $$$b_j$$$ where $$$j < i$$$. The objective is to select consecutive elements starting from the first element to maximize the cumulative sum. This principle applies to both the $$$r$$$ and $$$b$$$ sequences.

we can compute the prefix sum for both $$$r$$$ and $$$b$$$. To determine the optimal reconstruction of the original sequence $$$a$$$, we add the maximum prefix sum values from both the $$$r$$$ and $$$b$$$ sequences.

import itertools

t = int(input())

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

    r = list(itertools.accumulate(r))
    b = list(itertools.accumulate(b))

    result = max(0, max(r)) + max(0, max(b))
    print(result)

In this problem the sensible thing to do is to count the amount of times we are going to add some index of this sequence; then the maximal number gets assigned to the index that is added the most, and so on. In order to count the amount of times we referenced each index, we can use normal line sweep to store cumulative sums. Finally sort both arrays (the prefix sum array and the main array) and sum the product of the elements on the same index from both arrays.

Time complexity: $$$\mathcal{O}(nlogn)$$$.

Memory complexity: $$$\mathcal{O}(n)$$$.

from itertools import accumulate
from sys import stdin


def input(): return stdin.readline()


N, Q = map(int, input().split())
nums = sorted(map(int, input().split()))

line = [0]*(N + 1)
for _ in range(Q):
    l, r = map(int, input().split())
    line[l - 1] += 1
    line[r] -= 1

counts = sorted(accumulate(line[:-1]))

ans = 0
for i in range(N):
    ans += counts[i]*nums[i]

print(ans)

To determine the order of removals, we start from the end of the string. The last character represents the latest removed character. Moving backward, when encountering a character not seen before, it implies that this character was removed in the next step. Thus, we initiate the process from the last character, and each new character encountered denotes the one removed prior. Once we establish this order, we need to reverse it.

Now that we have the removal order, the next step is to verify whether the resulting string could have originated from that order. To check this, we first need to assess whether the character counts are valid. If a character was removed first, its actual occurrence in the original string should match its count in the given string. If removed second, the real occurrence in the original string is the count in the given string divided by 2, and so on. After obtaining the counts for each character in the original string, if the sum yields a non-integer number, the given string is invalid. However, if it results in an integer, we proceed to check if the given string can be derived from the first $$$k$$$ characters of the original string $$$k$$$ representing the sum of the counts.

To do this, we perform the same operations on the word containing the first $$$k$$$ characters of the given string. After obtaining the result, we compare it with the given string. If they match, we can confidently print the obtained removal order and the original string (which is the first $$$k$$$ characters of the given string). If not, we print $$$-1$$$ as the given string is not valid.

t = int(input())
for _ in range(t):
   s = input()
  
   arr = []
   got = set()
   count = Counter(s)
   for i in s[::-1]:
       if i not in got:
           arr.append(i)
       got.add(i)
   arr.reverse()
   occur = []
   pos = 1
   for i in range(len(arr)):
       occur.append(count[arr[i]] / (i + 1))
   left = 0
   if math.ceil(sum(occur)) != int(sum(occur)):
       pos = 0
 
   if pos:
       ans = ""
       cur = s[:int(sum(occur))]
       j = 0
  
       while cur:
           ans += cur
           stk = ""
           for i in cur:
               if i != arr[j]:
                   stk += i
           cur = stk
           j += 1
       if ans != s:
           pos = 0
   if pos:
       print(s[:int(sum(occur))],"".join(arr))
   else:
       print(-1)

To solve the problem we need to find the character with the highest alphabetical order in our string, since Abenezer will need at least that alphabet size and won't need more. To do this iterate through the string and find the character with the highest alphabetical order. Output the maximum alphabetical order found. The solution can be done in $$$O(n)$$$.

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    ma = 0
    for ch in s:
        ma = max(ma, ord(ch))
    print(ma - 96)
  

We are interested in the sum of a interval of a given sequence. This can be done by calculating the prefix sum of the sequence beforehand. That is,$$$sv_i = \sum_{j=1}^{i} (v_j)$$$ let . The sum of numbers in the interval $$$[l, r]$$$ would then be $$$sv_r - sv_{l - 1}$$$. we can sort sequence $$$v$$$ to obtain sequence $$$u$$$. We can deal with sequence $$$u$$$ likewise.

Preprocessing takes $$$O(n)$$$ time, and answering a query is only $$$O(1)$$$. The total complexity would be $$$O(nlogn + q)$$$.

n = int(input()) 
nums = list(map(int, input().split()))
q = int(input()) 

def calc_prefix(arr):
    res = [arr[0]]
    for i in range(1, len(arr)):
        res.append(res[-1] + arr[i])
    return res
sorted_nums = sorted(nums)
arr1 = calc_prefix(nums)
arr2 = calc_prefix(sorted(nums))
for _ in range(q):
    a, l, r = map(int, input().split())
    if a == 1:
        print(arr1[r - 1] - arr1[l - 1] + nums[l - 1])
    else:
        print(arr2[r - 1] - arr2[l - 1] + sorted_nums[l - 1])
  

First, we need to determine how many times each operation will be performed. For instance, if our query is $$$1, 3$$$, and $$$2, 5$$$ then $$$2$$$ and $$$3$$$ will be done twice since they fall within two ranges, while the rest will be done once. To calculate this, we can use a prefix sum with range updates.

Next, for each operation $$$l, r, d, and$$$ $$$v$$$ (where $$$v$$$ represents the number of times it will be performed), we'll increment all elements from $$$l$$$ to $$$r$$$ inclusive by $$$d*v$$$. This can also be efficiently computed using a prefix sum with range updates.

prefix sum with range updates: Let's think about a somewhat easier problem first. What if we were asked to add a constant value to the suffix of the array starting at index l, for multiple queries? Instead of updating the whole suffix for each query, we can only increment the first index of the suffix for each query, $$$i.e a[l]+=k$$$. Then after all queries, we take the prefix sum of the whole array. This will "propagate" our increments till the end of the array and thus our task of updating the whole suffix is accomplished at the end, after taking prefix sums. Now, what about updating the range $$$[l…r]$$$? Can you decompose this range update as $2 suffix updates? It can be decomposed as such:

if you need to increment the range $$$[l…r]$$$ by $$$k$$$, you can increment the suffix starting at index $$$l$$$ by $$$k$$$ and decrement the suffix starting at index $$$r+1$$$ by $$$k$$$, i.e perform the operations $$$a[l]+=k$$$ and $$$a[r+1]−=k$$$ for each query and then take the prefix sum of the array as before.

A visual summary:

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
 
op = []
for _ in range(m):
    op.append(list(map(int, input().split())))
    
q = [0]*(m+1)
for _ in range(k):
    l, r = (map(int, input().split()))
    q[l-1] += 1
    q[r] -= 1
    
for i in range(m-1):
    q[i+1] += q[i]
 
update = [0]*(n+1)
for query in range(m):
    l,r,d = op[query]
    update[l - 1] += d*q[query]
    update[r] -= d*q[query]
for i in range(n-1):
    update[i+1] += update[i]
for i in range(n):
    a[i] += update[i]
print(*a)	

There is always one sheep that shouldn't move.

Let's denote by k the number of sheep in the string, and by $$$x_1,x_2,…,x_k$$$ $$$(1≤x_1<x_2<…<x_k≤n)$$$ their positions in the string. Note that in the optimal solution the sheep with the number $$$m=⌈n/2⌉$$$ will not make moves. This can be proved by considering the optimal solution in which the sheep with the number m makes at least one move. if it moves to the right all sheep that are to the left of $$$x_m$$$( $$$x_1,x_2,…,x_{m-1}$$$) will move by one to the right but not all the sheep that are on the left side of $$$x_m$$$( $$$x_{m+1},x{m+2},…,x_k$$$) will decrease their movement by one and same thing if the $$$m-th$$$ sheep move to the left. So we can conclude that this solution is not optimal. Consider sheep with numbers from i=1 to n

Then the final position of the $$$i-th$$$ sheep will be $$$x_m−m+i$$$, and the answer will be $$$\sum\limits_{k = 0}^n |xi−(xm−m+i)|$$$, since all the sheep have to move from $$$x_i$$$ to $$$x_m-m+i$$$.

testcases = int(input())
for _ in range(testcases)
    n = int(input())
    s = input().strip()
    cnt = s.count('*') # total count of sheeps
    pos = -1 # hold the position of the mth sheep
    cur = -1 
    for i in range(n):
        if s[i] == '*':
            cur += 1
            if cur == cnt // 2:
                pos = i

    ans = 0
    # pos -> xm cnt//2-> and i =-> 0
    cur = pos - cnt // 2
    for i in range(n):
        if s[i] == '*':
            ans += abs(cur - i)
            cur += 1

    print(ans)

Let the sum of elements from the beginning be $$$p_i$$$. $$$[l,r]$$$ is bad if the sum of all the elements between that range equals $$$r - l + 1$$$. so $$$[l,r]$$$ is bad if $$$pr−pl + 1 = r−l + 1$$$.

Rewrite the formula $$$pr−pl + 1 = r−l + 1$$$.

Let's precalculate the array $$$p$$$, where $$$pi=\sum\limits_{j = 0}^{i - 1} a_j$$$(so $$$p_x$$$ is the sum of the first $$$x$$$ elements of $$$a$$$). Then subarray $$$[l,r]$$$ is bad if $$$pr−pl + 1 = r−l + 1$$$, so $$$pr−r=pl−l$$$.

Thus, we have to group all prefixes by value $$$pi−i$$$ for $$$i$$$ from $$$0$$$ to $$$n$$$. And if x indexes have a prefix with the same value of $$$pi−i$$$ then we have to add $$$x(x−1)/2$$$ to the answer.

from collections import defaultdict
testcases = int(input())
for _ in range(testcases):
    n = int(input())
    a = input()
    d = defaultdict(int)
    d[0] = 1
    res, s = 0, 0
    
    for i in range(n):
        s += int(a[i])
        x = s - i - 1
        d[x] += 1
        
        res += d[x] - 1
        
    print(res)

Here are two solutions.

Solution 1. Iterate through the string character by character. If $$$s_i=R$$$, then $$$t_i=R;$$$ otherwise, if $$$s_i=G$$$ or $$$B$$$, then $$$t_i=G$$$ or $$$B$$$. If the statement is false for any $$$i$$$, the answer is $$$NO$$$. Otherwise it is $$$YES$$$.

Solution 2. Replace all $$$B$$$ with $$$G$$$, since they are the same anyway. Then just check if the two strings are equal. In either case the complexity is $$$O(n)$$$ per testcase.

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    t = input()
    flag = True
    for i in range(n):
        if (s[i] == "R" and t[i] != "R") or (s[i] != "R" and t[i] == "R"):
            flag = False
            break
    if flag:
        print("YES")
    else:
        print("NO")
  

We can delete all zeros from the array, and it won't affect on answer. Maximum sum is $$$\sum_{i=1}^{n} (a_i)$$$. Minimum number of operations we should do is the number of subarrays with negative values of elements.

Total complexity: $$$O(n)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    
    total_sum = 0
    count = 0
    neg_found = False
    for num in nums:
        total_sum += abs(num)
        if num < 0 and not neg_found:
            neg_found = True
            count += 1
        if num > 0:
            neg_found = False
 
    print(total_sum, count)
  

In a valid substring, all characters must be the same. The objective is to change every character in the substring to the one that appears most frequently, using at most K changes. If the required changes exceed K, the substring isn't valid. Utilizing a dynamic sliding window approach, we begin with two pointers: a right pointer that increments while staying within K changes and a left pointer that moves right when the substring becomes invalid. During this process, we change the character with the minimum frequency to the character with the maximum frequency with an operation that equals the minimum frequency. We keep track of the largest valid substring size encountered.

n,k = list(map(int,input().split()))
s  = input()
count = {"a":0,"b":0}
ans = 0
left = 0

for right in range(n):

   count[s[right]]+=1
   while min(count.values()) > k:
       count[s[left]]-=1
       left+=1
   ans = max(ans,right - left + 1)

print(ans)

Let's consider three offsets of string "RGB": "RGB", "GBR" and "BRG".

Let's compare our string $$$s$$$ with infinite concatenation of each offsets of "RGB". However, we don't need an infinite string to compare. $$$n$$$-sized string could be enough. We don't either need to create $$$n$$$-sized string. We can observe that in the concatenated string the first character of the offset will always be on an index which is a multiple of 3 (whose modulo 3 is 0), the second character will be on an index whose modulo 3 is 1, the third character will be on an index whose modulo 3 is 2.

We can use fixed sliding window and compare the character in that window. While comparing we will count the matches and keep track of the maximum matches in $$$k$$$-sized window. We can then find the minimum number of changes we need to make by subtracting the number of maximum matches from $$$k$$$.

T = int(input())

for _ in range(T):
    N, K = map(int, input().split())
    s = input()

    offsets = ["RGB", "GBR", "BRG"]
    ans = float('inf')

    for offset in offsets:
        matches = 0
        for right in range(K): # Calculate the matches for first K elements
            if offset[right%3] == s[right]:
                matches += 1
        
        max_matches = matches
        for right in range(K, N):
            left = right - K
            if offset[right%3] == s[right]:
                matches += 1
            if offset[left%3] == s[left]:
                matches -= 1
            
            max_matches = max(matches, max_matches)
        
        ans = min(ans, K - max_matches)
    
    print(ans)

Calculate the total number of participants that can join the contest for hour 1.

Use the sliding window algorithm to calculate the rest.

For hour 1 at the first timezone, it will be hour 2 for the second, and so forth. participants from timezone $$$s$$$ to timezone $$$f - 1$$$ are eligible to join the contest. For the second hour, it becomes $$$s - 1 - f - 2$$$, and so forth. If we have the count of contestants participating in the first hour, we can use a sliding window technique to compute the rest. Our answer is updated only when we discover a larger sum.

$$$Note$$$ Since the array is circular and our pointer might be out of bound we have to use mod to correct it

n = int(input())
arr = list(map(int , input().split()))
s , f = map(int , input().split())
 
ans = 1
# The window when time = 1 at first timezone
cur_total = sum(arr[s - 1:f - 1])


left = s - 1 # the leftmost element in our window
right = f - 2 # the rightmost element in our window


max_value = cur_total


for i in range(2 , n + 2):
   
   cur_total -= arr[right]
   right -= 1
   left -= 1  
   # When left and right < 0 that means they start iterating from the back    
   cur_total += arr[left]


   if cur_total > max_value:
       ans = i
       max_value = cur_total
print(ans if ans else n)	

In the context of maximizing earnings by adding at most $$$(m)$$$ negative elements, the optimal solution involves sorting the array in non-decreasing order and summing up the first at most $$$m$$$ (possibly zero) negative numbers.

Time complexity: O($$$(nlogn)$$$) where $$$n$$$ is the number of TV Sets we have Space complexity: O(1)

n, m = map(int, input().split())
tvSets = list(map(int, input().split()))    
tvSets.sort()
ans = 0
# iterate over tv sets m time
for i in range(m):
    # sum up negative numbers only
    if tvSets[i] < 0:
        ans += tvSets[i]
    else:
        break
print(-ans)

We can delete all zeros from the array, and it won't affect the answer.

The maximum sum is Σ (from i=1 to n) |ai|. The minimum number of operations we should do is the number of continuous subsequences with negative values of elements.

Total complexity: O(n) Space complexity: O(1)

T = int(input())

for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    
    total_sum = 0
    negative_subsequences = 0
    is_negative_subsequence = False
    
    for element in a:
        total_sum += abs(element)
        
        if element < 0 and not is_negative_subsequence:
            is_negative_subsequence = True
            negative_subsequences += 1
        
        if element > 0:
            is_negative_subsequence = False
 
    print(total_sum, negative_subsequences)

Let’s calculate the maximum number of problems we can take, and the answer will be n subtracted by that count.

An arrangement that always minimizes the absolute difference between adjacent pairs is the array in sorted order. What we notice, is that if the array is sorted, we will always take a subarray (all taken elements will be consecutive).

So, the problem converts to finding the largest element subarray for which ai — ai — 1 <= k. It’s easy to see that all the subarrays are totally different (don’t share any intersection of elements), thus, we can maintain a count variable of the current number of elements in the current subarray, and iterate through array elements from left to right. If we currently are at i and ai — ai — 1 > k then we just set the count to 1 since we know a new subarray starts, otherwise, we just increase our count by 1. The answer will be n subtracted by the largest value that our count has achieved.

Time complexity: O(nlogn) Space complexity: O(1)

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    a.sort()
    
    cnt = 1
    ans = 1
    
    for i in range(1, n):
        if a[i] - a[i - 1] > k:
            cnt = 1
        else:
            cnt += 1
        ans = max(ans, cnt)
    
    print(n - ans)

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

Iterates through the array, starting from the second index, comparing each element to its leftmost minimum and right neighbor. If at any point the current element is greater than both its leftmost minimum elements and right neighbors, the answer is 'NO', indicating the absence of a valid valley. Otherwise, the answer remains 'YES' and we will update the leftmost minimum element.

Time complexity: O(n), n is length of the array Space complexity: O(1)

# iterating over the test cases
 for _ in range(int(input())):
    n = int(input())
    nums = list(map(int, input().split()))
    indx = 1
    ans = 'YES'
    leftMin = nums[0]
    # iterate over the array starting from the second index
    while indx <= n - 2:
        # compare current element with leftmost minimum elements and right neighbors
        if leftMin < nums[indx] > nums[indx + 1]:
            ans = 'NO'
            break
        leftMin = min(leftMin, nums[indx])
        indx += 1
    print(ans)

The problem can be efficiently solved using the two-pointer technique. Let's denote the first pointer as left (l) and the second pointer as right (r). For each position of left, we move the right end right until, on the substring s[l, l+1, ..., r], it is possible to make no more than k swaps to transform this substring into a beautiful one. We then update the answer with the length of this substring and move left to the right.

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

n, k = map(int, input().split())
s = input()

left = 0
b = 0
max_length = 1

# Handling 'b' characters
for right in range(n):
    if s[right] == 'b':
        b += 1

    # Move the left pointer until it's possible to make no more than k swaps
    while b > k:
        if s[left] == 'b':
            b -= 1
        left += 1

    max_length = max(max_length, right - left + 1)

# Reset pointers and handle 'a' characters
left = 0
a = 0

for right in range(n):
    if s[right] == 'a':
        a += 1

    # Move the left pointer until it's possible to make no more than k swaps
    while a > k:
        if s[left] == 'a':
            a -= 1
        left += 1

    max_length = max(max_length, right - left + 1)

print(max_length)

One way to solve the problem is by iterating through the grid and, when a letter is found, continuing downwards until the entire word is obtained.

However, there is a faster coding approach: simply input each character and output it if it is not a dot. This method works because the characters are inputted in the same top-to-bottom order. The time complexity remains constant, denoted as O(1), regardless of the approach used.

tc = int(input())
 
for _ in range(tc):
    result = []
    for i in range(8):
        result += [char for char in input() if char.isalpha()] 

    print("".join(result))

It is apparent that we can perform a z-sort on any given array, denoted as $$$(nums)$$$ Let's define $$$(k)$$$ as the count of even positions within $$$(nums)$$$ We can assign the maximum $$$(k)$$$ elements to those even positions, and distribute the remaining $$$(n-k)$$$ elements to the odd positions. It's clear that the resulting array will be z-sorted.

n = int(input())
nums = list(map(int,input().split()))

result = [0]*n

nums.sort()

k = n-1
for i in range(1, n, 2):
    result[i] = nums[k]
    k-= 1

for i in range(0, n, 2):
    result[i] = nums[k]
    k-= 1

print(*result)

We will do the following steps inorder to solve it Sort the given sequence in non-decreasing order. The first $$$(k)$$$ elements of the sorted sequence will be the smallest $$$(k)$$$ elements. Any number smaller than or equal to $$$(a[k-1])$$$' will have exactly $$$(k)$$$ elements less than or equal to it. If is $$$(k)$$$ is 0 , the smallest possible value is 1.

n, k = list(map(int, input().split()))
 
nums = list(map(int, input().split()))
 
nums.sort()

if n==k:
	print(nums[k-1])
elif n > k and nums[k] > nums[k-1]:
	print(nums[k-1])
elif k == 0 and nums[0] > 1:
	print(1)
else:
	print(-1)

For each element $$$a_{ij}$$$ , if it lies on the main diagonal $$$(i - j = 0)$$$, secondary diagonal $$$(i + j = n - 1)$$$, middle row $$$(i = n/2)$$$, or middle column $$$(j = n/2)$$$, it is added to the total sum; otherwise, it is skipped.

Consider a line represented by the string "LRRLL". If the ith person turns around, the value of the line will change by specific amounts for each person. For example, if the second person turns around, they will see 3 people before and 1 person after, so the value of the line changes by -2.

Now, to solve this problem efficiently, we can follow these steps:

1. Calculate the change in value for each person in the line if they were to turn around. This will create an array or list of values representing the change in value for each person.
2. Sort this array or list of values in decreasing order. This will help us determine which person turning around will yield the maximum increase in the overall value.
3. Calculate the total values of each person in the line as they were in their original position.
4. Create a result array
5. Traverse through the sorted list of values I. assign the sum of total values and each values in the sorted array to the total sum II. append this result to the result array

This approach, based on sorting the value changes and then greedily selecting the individuals whose turning around increases the overall value, ensures a time complexity of O(n log n) per test case, where 'n' represents the number of people in the line.

for _ in range(int(input())):
    n = int(input())
    lines = input()
    values = []
    totCount = 0
    # getting the total counts of each person in current line
    # and getting the maximized count of each persons by swapping the persons view direction
    for i, line in enumerate(lines):
        if line == 'L':
            totCount += i
            values.append(max(i, n - i - 1) - i)
        else:
            totCount += (n - i - 1)
            values.append(max(i, n - i - 1) - (n - i - 1))
    
    # sort values in decreasing order to maximize the counts
    values.sort(reverse=True)
    for i in range(len(values)):
        totCount += values[i]
        values[i] = totCount
    
    print(*values)

For each element $$$a_{ij}$$$ , if it lies on the main diagonal $$$(i - j = 0)$$$, secondary diagonal $$$(i + j = n - 1)$$$, middle row $$$(i = n/2)$$$, or middle column $$$(j = n/2)$$$, it is added to the total sum; otherwise, it is skipped.

Create a separate matrix with the same dimension and size and Initially, set all all values of this newly created matrix to $(1).

If any corresponding cell in the given matrix is $$$(0) make all the rows and columns of that corresponding cell in the newly created matrix to $$$(0).

Examine this newly created matrix if it can generate the given matrix. If it cannot produce the given matrix, the answer is clearly “NO”.

    n, m = map(int, input().split())
    matrix = []
    for _ in range(n):
        matrix.append(list(map(int, input().split())))
    
    # reconstructing the original matrix
    original = [[1 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 0:
                for k in range(n):
                    original[k][j] = 0
                for t in range(m):
                    original[i][t] = 0
    # perform the OR operation on the original matrix
    newMatrix = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            newMatrix[i][j] |= int(any(original[i] + [original[k][j] for k in range(n)]))
    
    # compare the new matrix with the given matrix
    if newMatrix == matrix:
        print('YES')
        for i in range(n):
            print(*original[i])
    else:
        print('NO')

For this problem you just need to implement what it asks you. To be able to implement it you need to know about the "if" statement.

t  = int(input())
for _ in range(t):
    rating = int(input())
    if rating >= 1900:
        print("Division 1")
    elif 1600 <= rating <= 1899:
        print("Division 2")
    elif 1400 <= rating <= 1599:
        print("Division 3")
    else:
        print("Division 4")

Note that during encryption, only characters different from $$$c$$$ are added after the character $$$c$$$. However, when the character $$$c$$$ is encrypted with different characters, another $$$c$$$ character is added to the string.

This means that for decryption, we only need to read the characters of the string after $$$c$$$ until we find the first character equal to $$$c$$$. It signals the end of the block of characters that will be converted to the character $$$c$$$ during decryption.

To decrypt the entire string, we decrypt the first character $$$s1$$$. Let the next occurrence of the character $$$s1$$$ be at position $$$pos1$$$. Then the next character of the original string is $$$s_{pos1+1}$$$. We apply the same algorithm to find the next paired character and so on.

T = int(input())
for _ in range(T):
    n = int(input())
    s = input()
    new_string = []
    l = 0
    r = 0
    while r < len(s):
        if s[l] == s[r] and l != r:
            new_string.append(s[l])
            r += 1
            l = r
        else:
            r += 1
    ans = "".join(new_string)
    print(ans)	

Let's sort AASTUs and AAiTs by skill. If AASTU with lowest skill can be matched, it is good idea to match him. It can't reduce answer size. Use AAiT with lowest skill to match.

N = int(input())
aastu = sorted(map(int, input().split()))

M = int(input())
aait = sorted(map(int, input().split()))

pairs = 0
p1 = 0 # pointer of aastu array
p2 = 0 # pointer of aait array

while p1 < N and p2 < M:
    if abs(aastu[p1] - aait[p2]) <= 1:
        pairs += 1
        p1 += 1
        p2 += 1
    elif aastu[p1] < aait[p2]:
        p1 += 1
    else:
        p2 += 1
        
print(pairs)

Note that if the second operation were free, we would need $$$\lceil \frac{\text{sum}}{2} \rceil$$$ operations to get rid of all the aliens. Indeed, when we kill one alien, we can kill a second alien for free with a second operation. But the second operation is not free. So we need to use the second operation as little as possible.

To do this, we need to apply ultimates (second attack) on the current largest horde by number of aliens, when the combo counter reaches the size of the largest horde. And we apply the first attack on the smallest hordes. This is so because the combo counter allows us to defeat $$$\lceil \frac{\text{sum}}{2} \rceil$$$ aliens. But since we can't apply this operation on several hordes at once, we need to keep the number of hordes on which we apply these attacks of the second type as small as possible. Then we can use the greedy algorithm described above. Formally, we need to keep a sorted array and store two pointers: pointer $$$i$$$ — to the smallest horde, $$$j$$$— to the largest horde. Until $$$i$$$ is equal to $$$j$$$: if after destroying all horde $$$i$$$ we can't kill horde $$$j$$$ with ultimates, we destroy horde $$$i$$$, increase pointer $$$i$$$ by $$$1$$$ and increase combo counter $$$x$$$ by $$$a[i]$$$. Otherwise, hit the horde $$$i$$$ so many times that the combo counter $$$x$$$ becomes $$$a[j]$$$. Then apply a second attack on horde $$$j$$$, reduce horde $$$j$$$'s counter by $$$1$$$, reduce $$$a[i]$$$, and nullify the combo counter. When $$$i$$$ becomes equal to $$$j$$$, you just need to apply the first attack the right number of times to finish with ultimates (or not if $$$a[i] =1$$$).

Total complexity $$$O(nlogn)$$$.

from math import ceil
t = int(input())
for _ in range(t):
    n = int(input())
    nums = sorted(map(int, input().split()))
    ans = 0
    cur = 0
    left = 0
    right = n - 1
    while left < right:
        cur += nums[left]
        if cur >= nums[right]:
            ans += nums[right] + 1
            cur -= nums[right]
            right -= 1
        left += 1
    if left == right:
        cur += nums[right]
    ans += (ceil(cur / 2) + 1) if cur > 1 else cur
    print(ans)

Calculate the minimum segment size so that a number can be found in all such segments. Do this for every number.

For two segment sizes $$$a$$$ and $$$b$$$ where $$$a < b$$$. If $$$u$$$ is the minimum number found in all segments with size $$$a$$$, and $$$v$$$ is the minimum number found in all segments with size $$$b$$$, then $$$v <= u$$$.

Let's fix some arbitrary number $$$x$$$ and calculate the minimum value of $$$k$$$ such that $$$x$$$ occurs in all segments of length $$$k$$$. Let $$$p_{1}<p_{2}<⋯<p_{m}$$$ be the indices of entries of $$$x$$$ in the array. Then, for each $$$1≤i<m$$$ it is clear that $$$k$$$ should be at least the value of $$$p_{i+1}−p_{i}$$$. Also, $$$k≥p_{1}$$$ and $$$k≥n−p_{m}+1$$$. The maximum of these values is the minimum segment size $$$k$$$ where $$$x$$$ can possibly be the minimum value in. We do this for every number, and then take the minimum of those numbers for a segment size.

Finally for a segment size $$$a > 1$$$, we take the minimum of the value already there or the minimum value we had for the previous size $$$a - 1$$$.

from collections import defaultdict


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


    last_indx = defaultdict(lambda :-1) # stores the last occurence of a given number
    max_dist = defaultdict(int) # stores maximum distance between instances of a given number
    ans = [float('inf')]*n

    # calculate the minimum size segment so that a number can be found in all such segments
    # and take the minimum of those numbers for the segment size
    for indx, num in enumerate(a):
        prev = last_indx[num]
        max_dist[num] = max(max_dist[num], indx - prev)
        
        min_segment_covered = max(max_dist[num], n - indx) - 1
        ans[min_segment_covered] = min(ans[min_segment_covered], num)
        last_indx[num] = indx
    
    # minimum number propagation to larger segment sizes
    for indx in range(1, n):
        ans[indx] = min(ans[indx], ans[indx - 1])
    
    # replace the inf's by -1
    for indx in range(n):
        if ans[indx] == float('inf'):
            ans[indx] = -1
    
    print(*ans)
        

To identify the unique element, this solution counts the occurrences of each number in the array. Then, it locates its index in the array.

from collections import Counter

t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    count = Counter(nums)
    for key in count:
        if count[key] == 1:
            mynum = key
    for i in range(len(nums)):
        if nums[i] == mynum:
            print(i + 1)
            break

To solve the problem quickly, we can maintain two stacks: one for uppercase letters and one for lowercase letters. When deleting, we need to mark that the character at a specific position should be skipped. Alternatively, we can reverse the original string and skip characters instead of deleting them.

tc = int(input())
 
for _ in range(tc):
    word = input()
    res = []
    cap_pos = []
    sm_pos = []
    for i in word:
        if i == "B":
            if cap_pos:
                res[cap_pos.pop()] = ""
        elif i == 'b':
            if sm_pos:
                res[sm_pos.pop()] = ""
        else:
            if i.islower():
                sm_pos.append(len(res))
            else:
                cap_pos.append(len(res))
            res.append(i)
    print("".join(res[:-1]))

Initialize $$$(rows)$$$ and $$$(cols)$$$ dictionaries to track the frequency of each element in the matrix rowwise and columnwise.

For each element $$$a_{ij}$$$, update the counts of these elements in the corresponding $$$(rows)$$$ and $$$(cols)$$$ dictionaries for that row and column.

Check if the count of the current element in both the $$$(rows)$$$ dictionary of its row and the $$$(cols)$$$ dictionaries of its column is equal to $$$(1)$$$. If so, the element is considered unique and updates the $$$(result)$$$ list.

from collections import defaultdict
n, m = map(int, input().split())

grid = []
for _ in range(n):
    grid.append(list(input()))

rows = [defaultdict(int) for i in range(n)]
cols = [defaultdict(int) for i in range(m)]
for i in range(n):
    for j in range(m):
        rows[i][grid[i][j]] += 1
        cols[j][grid[i][j]] += 1

result = []
for i in range(n):
    for j in range(m):
        if rows[i][grid[i][j]] == 1 and cols[j][grid[i][j]] == 1:
            result.append(grid[i][j])

print(''.join(result))

The equation $$$c_i = d \cdot a_i + b_i$$$ is given, and the objective is to maximize the number of zeros in the resulting array $$$c$$$. To achieve this goal, the strategy is to identify values of $$$d$$$ that satisfy the condition $$$0 = d \cdot a_i + b_i$$$, which leads to the expression $$$d = (-b_i) / a_i$$$.

The approach involves iterating through the elements in arrays $$$a_i$$$ and $$$b_i$$$ to track the frequency of occurrences of $$$((-b_i) / a_i)$$$ in a dictionary. To avoid potential inaccuracies stemming from floating-point precision problems when using decimal numbers as dictionary keys, the code represents these fractions in their simplest form. For instance, for values $$$a_i = 6$$$ and $$$b_i = 9$$$, simplification yields $$$(-9/6 => -3/2)$$$, and the simplified fraction $$$(-3, 2)$$$ is used as a key in the dictionary.

from collections import defaultdict
from fractions import Fraction

def main():
    n = int(input()) 
    a = list(map(int, input().split()))
    b = list(map(int, input().split())) 
    c = defaultdict(int) 
    d = 0   
    for i in range(n):
        if b[i] == 0 and a[i] == 0:
            d += 1
        elif a[i]:
            fraction = Fraction(-b[i], a[i])
            c[fraction] += 1
    
    d += max(c.values()) if c else 0
    print(d)

if __name__ == '__main__':
    main()

This problem can be solved using a dictionary to track the count of each number in the array. By iterating through the array and incrementing the count of each number in the dictionary, we calculate the current count (current_count) for each number. Additionally, we utilize another dictionary (appearance_dict) to monitor the total size of the numbers for each frequency count (calculated as frequency_count * frequency = the total size). This calculation allows us to understand the array's total size if the frequency is set as C.

After traversing through the array, we determine the maximum value in the appearance_dict dictionary. This value signifies the maximum size capable of accommodating numbers. The key retrieved from the dictionary indicates the maximum frequency for each unique number, necessary to make the array beautiful. Our goal is to ensure each number appears either zero or C times. Hence, we must eliminate all elements except those appearing C times. Consequently, the number of elements to remove equals the total number of elements minus the maximum value found in the appearance_dict dictionary.

from collections import defaultdict

test_cases = int(input())
for _ in range(test_cases):
    array_length = int(input())
    array = list(map(int, input().split()))

    count_dict = defaultdict(int)
    appearance_dict = defaultdict(int)

    for element in array:
        count_dict[element] += 1
        current_count = count_dict[element]
        appearance_dict[current_count] += current_count

    max_appearance = max(appearance_dict.values())

    print(array_length - max_appearance)