Try what can you achieve with the given operation.

Given a sequence of numbers, the minimum value that can be obtained by applying the given bitwise AND operation is a1 & a2 & a3 & ... & an, since ANDing can't turn on any off bits but can only turn off on bits. By repeatedly applying the operation on suitable intervals, Mocha can make each number in the sequence a1 & a2 & a3 & ... & a4 . This can be achieved by performing the operation on each l, r possible pairs.

[submission:203874032]

Try graph/tree traversal.

To solve this problem, we represent the repost chain as a directed acyclic graph (DAG), where each node represents a user and a directed edge from node A to node B represents a repost event where user A reposted from user B. We use a recursive DFS algorithm to traverse the DAG and find the longest path. We start by adding the initial post by Polycarp as the root node of the DAG and then iterate through the repost events in the input, adding each user to the DAG with a directed edge from the reposting user to the original poster. We then use a recursive DFS function to traverse the DAG and find the length of the longest path from the root node to any other node. Finally, we return the maximum length of any path in the DAG, which corresponds to the length of the longest repost chain.

BFS Solution [submission:204222640] DFS Solution [submission:204117650]

This problem can be solved using a graph traversal algorithm such as Breadth-First Search (BFS). We can create an undirected graph where each stamp represents an edge between two cities. Then we can start BFS from any city and traverse the graph until we find one of the end cites, then

Since there are only two possible routes, we can stop BFS once we find a path that connects the two endpoints. We can then output the indexes of the cities along this path.

Overall, the time complexity of this solution is O(n), where n is the number of stamps in the envelope.

[submission:204338953]

Run BFS to find the a path between start cell and the lower rightmost cell.

[submission:203876708]

Try to solve without graph traversal.

Start from the end position of the mouse's move and return all cells that are p distance away from it.

[submission:203836678]

To check if the king can reach the target, we need to ensure that both the king and the target lie in the same quadrant relative to the black queen. We can determine this by comparing the signs of the x and y coordinates of the king and the target with respect to the queen. If they have the same signs for both coordinates, then they are in the same quadrant and the king can reach the target.

dimension = int(input())
ax, ay = map(int, input().split())
bx, by = map(int, input().split())
cx, cy = map(int, input().split())

# Check if king and target are in the same quadrant
if (bx-ax) * (cx-ax) > 0 and (by-ay) * (cy-ay) > 0:
    print("YES")
else:
    print("NO")

The problem involves a graph of employees and their managers, with one employee called "root" not having a manager. We can label each employee with a number indicating their distance from the root. The solution to the problem is the highest number assigned to any employee.

Why is this? It's because if two employees have the same label, they cannot be in the same group because one cannot be the superior of the other. Therefore, we can form groups of employees by putting those with the same label together, and these groups will not overlap.

import sys
from collections import defaultdict

# Increase recursion limit to avoid stack overflow during DFS
sys.setrecursionlimit(2500)

def main():
    # Read in number of employees
    n = int(input())
    # Initialize empty adjacency list and list of "root" employees
    adjlist = defaultdict(list)
    roots = []
    
    # Loop through each employee and their manager
    for i in range(1, n + 1):
        emp = int(input())
        
        # If employee has no manager, add them to list of "root" employees
        if emp == -1:
            roots.append(i)
        # Otherwise, add this employee to their manager's list of direct reports
        else:
            adjlist[emp].append(i)
    
    # Initialize variable to store maximum depth found during DFS
    max_level = 0
    # Loop through each root employee and perform DFS to find maximum depth
    for root in roots:
        level = dfs(root, adjlist)
        max_level = max(level, max_level)
    
    # Output the maximum depth found
    print(max_level)

# Recursive DFS function to find depth of each employee in the tree
def dfs(cur, adjlist):
    # Initialize current depth to 0
    level = 0
    # Loop through each direct report of this employee and perform DFS to find maximum depth
    for nxt in adjlist[cur]:
        level = max(dfs(nxt, adjlist), level)
    # Add 1 to the maximum depth found for this employee
    return level + 1

# Call the main function to run the program
main()

To solve this problem, we can work backwards from the target number A to the given number B. If the last digit of B is 1, then the last operation must have been appending a 1 to the right of the current number. So, we can delete the last digit of B to get the new number and continue.

If the last digit of B is even, then the last operation must have been multiplying the current number by 2. So, we can divide B by 2 to get the new number and continue.

If the last digit of B is an odd digit except for 1, then it is not possible to obtain A by performing the given operations on B.

We repeat this algorithm until we either reach A or we obtain a number less than A, in which case it is not possible to transform B to A.

def can_transform_to_target(start_num, target_num, transformation):
    # Keep applying operations until target_num <= start_num
    while target_num > start_num:
        # If target_num is even, divide it by 2
        if target_num % 2 == 0:
            target_num //= 2
            transformation.append(target_num)
        # If target_num ends in 1, remove that digit
        elif target_num % 10 == 1:
            target_num //= 10
            transformation.append(target_num)
        # If target_num is odd and doesn't end in 1, it can't be transformed to A
        else:
            return "NO"
    
    # If target_num ended up equal to A, it can be transformed to A
    return "YES" if target_num == start_num else "NO"


start, target = map(int, input().split())
transformation = [target]
is_possible = can_transform_to_target(start, target, transformation)
print(is_possible)

if is_possible == "YES":
    print(len(transformation))
    print(*transformation[::-1])

We can start traversing the tree from the root node and keep track of the number of consecutive vertices with cats using a parameter k. If k exceeds the maximum number of consecutive vertices with cats allowed, m, then we can stop traversing that path since it's not a valid path for the cat to travel. Otherwise, we can continue traversing the tree.

The answer we're looking for is the total number of leaves (endpoints of the tree) that we're able to reach within the constraints set by m.

num_vertices, max_cats = map(int, input().split())
cat_count = list(map(int, input().split()))

adj_list = [[] for _ in range(num_vertices)]

for _ in range(num_vertices - 1):
    vertex_a, vertex_b = map(int, input().split())
    adj_list[vertex_a - 1].append(vertex_b - 1)
    adj_list[vertex_b - 1].append(vertex_a - 1)


def dfs(start_vertex, parent_vertex, start_cats):
    stack = [(start_vertex, parent_vertex, start_cats)]
    leaf_count = 0
    while stack:
        current_vertex, parent_vertex, current_cats = stack.pop()
        if current_cats > max_cats:
            continue
        is_leaf = True
        for neighbor in adj_list[current_vertex]:
            if neighbor != parent_vertex:
                is_leaf = False
                stack.append((neighbor, current_vertex, current_cats * cat_count[neighbor] + cat_count[neighbor]))
        leaf_count += is_leaf
    return leaf_count


num_leafs = dfs(0, -1, cat_count[0])

print(num_leafs)

The problem involves determining if there is a rectangular region in a grid that is filled with only ones. We can break down the problem by finding the divisors of a given number k and checking if there are subsegments of length p in one grid and subsegments of length q in another grid that consist of only ones.

To solve this, we can precalculate the number of subsegments of each length that consist of only ones in both grids. We can then iterate through the divisors of k, calculate the corresponding lengths p and q, and check if there are enough subsegments of length p in one grid and length q in the other grid to form a rectangular region of only ones.

To find all subsegments of ones in a grid of length l, we can consider all maximal subsegments and add the length of each segment to the count of subsegments of the corresponding length.

def count_ones(segments, cnt):
    i = 0
    n = len(segments)

    while i < n:
        j = i
        while j < n and segments[j] == 1:
            j += 1

        len_ones = (j - i)
        count = 1
        while len_ones > 0:
            cnt[len_ones] += count
            len_ones -= 1
            count += 1

        i = j + 1


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

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

a_cnt = [0] * (n + 1)
b_cnt = [0] * (m + 1)

count_ones(a, a_cnt)
count_ones(b, b_cnt)

cnt = 0
for i in range(1, n + 1):
    idx = k // i
    mod = k % i

    if idx <= m and mod == 0:
        cnt += (a_cnt[i] * b_cnt[idx])

print(cnt)
'

One way to verify a function is by checking if there exists an "i" for which the output of the function, when applied three times consecutively (i.e., f(f(f(i)))), is equal to "i". In other words, the condition to check is whether f(f(f(i))) equals "i"

length = int(input())

planes = list(map(lambda x: int(x) - 1, input().split()))

flag = False
for i in range(length):
    if planes[planes[planes[i]]] == i:
        flag = True

print("YES" if flag else "NO")

To maximize the sum of an array, we can first divide all numbers in the array by 2 as many times as possible and count the number of successful divisions as "k". Then, we should identify the largest number remaining in the array after these divisions. To obtain the maximum sum, we need to multiply this largest remaining number by 2 raised to the power of "k".

numOfTests = int(input())

for _ in range(numOfTests):
    length = int(input())
    arr = list(map(int, input().split()))

    twos = 0
    for i in range(length):
        while arr[i] % 2 == 0:
            twos += 1
            arr[i] //= 2

    arr.sort()
    total = sum(arr[:-1]) + (arr[-1] * (1 << twos))
    print(total)

We have a bunch of jewelry pieces with different prices. We want to color them in a way that if the price of any piece is a multiple of a prime number, then it should have a different color than the other pieces whose prices are also multiples of that prime number.

To solve this, we need to first find all the prime numbers up to a certain range (in this case, up to number of jewelries + 1) using the Sieve of Eratosthenes method. Then, we can color all the jewelry pieces whose prices are prime numbers with one color, and color the rest of the pieces with a different color. This ensures that if a piece's price is a multiple of a prime number, it will have a different color than the other pieces whose prices are also multiples of that prime number.

def build_sieve(num_jewelries):
    sieve = [1 for i in range(num_jewelries)]
    sieve[1] = 1
    
    i = 2
    while i * i <= num_jewelries:
        if sieve[i] == 1:
            for j in range(i * i, num_jewelries, i):
                sieve[j] = 2
        i += 1
    
    return sieve
    
def main():
    num_jewelries = int(input())
    sieve = build_sieve(num_jewelries + 2)
    
    if num_jewelries > 2:
        print(2)
    else:
        print(1)
    
    for i in range(2, num_jewelries + 2):
        print(sieve[i], end = " ")
    
main()

Given a number num, we want to find two positive integers a and b such that their LCM is equal to num and the maximum of a and b is minimized. To do so, we can start by finding the prime factors of num. We can then divide the prime factors into two sets a and b such that their product is num.

To minimize the maximum of a and b, we want to divide the prime factors as evenly as possible between a and b. This means that we want to split the prime factors into two sets of approximately equal size. To do so, we can start by initializing a to 1 and b to num, and then iterate over all the possible factors of num starting from 2.

For each factor i, we check if it is a divisor of num and whether the LCM of i and num // i is equal to num. If both conditions are satisfied, we update a and b accordingly. By doing so, we are effectively finding a pair of positive integers a and b such that their product is num and their greatest common divisor (GCD) is 1, i.e., they are coprime.

import math

num = int(input())

a = 1
b = num

for i in range(2, int(math.sqrt(num)) + 1):
    if num % i == 0 and math.lcm(i, num // i) == num:
        a = i
        b = num // i

print(a, b)

To solve this problem, we need to find the greatest common divisor (GCD) of the given integers a and b that lies in a range specified by the query. We can use the fact that any divisor of a and b must also be a divisor of their GCD.

After computing the GCD of a and b, we can obtain all its factors by iterating from 1 to the square root of GCD, and checking if it divides the GCD without a remainder. Once we have the factors of the GCD, we can check if they fall within the range of the current query.

If there are factors within the range, we can pick the maximum factor that satisfies the conditions. Otherwise, we output -1 for the current query, indicating that there is no common divisor within the range.

def gcd(num1, num2):
    while num2:
        num1 %= num2
        num1, num2 = num2, num1
    
    return num1

def find_factors(num):
    factors = []
    d = 1

    while d * d <= num:
        if num % d == 0:
            factors.append(d)
            factors.append(num // d)
            
        d += 1
    
    if num > 1:
        factors.append(num)
    
    return sorted(factors)
    

def main():
    num1, num2 = map(int, input().split())
    num_queries = int(input())
    cur_gcd = gcd(num1, num2)
    factors = find_factors(cur_gcd)

    for query in range(num_queries):
        low, high = map(int, input().split())

        modified_gcd = -1
        for factor in factors:
            if low <= factor <= high:
                modified_gcd = factor


        print(modified_gcd)

main()

We need to count the number of pairs of integers ai and aj such that there exists an integer x where ai * aj = x^k.

For each number ai, we can find its prime factorization. Let's say it is ai = p1^x1 * p2^x2 * ... * pn^xn.

To make ai * aj = x^k, we need to choose aj such that its prime factorization only includes the same prime factors as ai, but with exponents that are multiples of k.

For each prime factor pi in ai, let's calculate the remainder of xi when divided by k. If the remainder is 0, then we don't need to change the exponent of pi. But if the remainder is r > 0, then we need to change the exponent of pi to (k — r).

Let's call the resulting product of adjusted prime factors for ai, the "multiplier" of ai.

Now, we can keep track of the number of times we've seen each multiplier by using a dictionary (in Python, we can use a defaultdict). For each ai, we can multiply its prime factors with adjusted exponents to get its multiplier, and add to the answer the number of times we've seen the same multiplier before.

Finally, we can update the dictionary by incrementing the count of the multiplier we've seen for this ai.

At the end, the answer will be the number of pairs that we have counted.

from collections import defaultdict


def prime_factorization(num):
    factors = defaultdict(int)
    d = 2

    while d * d <= num:
        while (num % d == 0):
            factors[d] += 1
            num //= d 

        d += 1

    if num > 1:
        factors[num] += 1

    return factors 

def main():
    length, power = map(int, input().split())
    nums = list(map(int, input().split()))
    multiplicand = defaultdict(int)
    ans = 0

    for num in nums:
        prime_factors = prime_factorization(num)
        multiplier = 1

        for factor in prime_factors:
            exponent = prime_factors[factor]
            modulo = exponent % power

            if modulo != 0:
                multiplier *= (factor ** (power - modulo))
            
        
        ans += multiplicand[multiplier]
        cur_multiplicand = 1
        
        for factor in prime_factors:
            exponent = prime_factors[factor]
            modulo = exponent % power
            cur_multiplicand *= (factor ** modulo)
            
        multiplicand[cur_multiplicand] += 1
    
    print(ans)

main()

Time Complexity: O(n.sqrt(n))

from collections import defaultdict

def build_sieve(num):
    sieve = [0 for i in range(num + 1)]
    
    for i in range(num + 1):
        sieve[i] = i
    
    i = 2
    
    while i * i <= num:
        if sieve[i] == i:
            for j in range(i * i, num + 1, i):
                if (sieve[j] == j):
                    sieve[j] = i
        i += 1

    return sieve

def prime_factorization(num, sieve):
    factors = defaultdict(int)
    d = 2

    while num > 1:
        sf = sieve[num]
        factors[sf] += 1
        num //= sf

    return factors 

def main():
    length, power = map(int, input().split())
    nums = list(map(int, input().split()))
    multiplicand = defaultdict(int)
    sieve = build_sieve(100_000)
    ans = 0

    for num in nums:
        prime_factors = prime_factorization(num, sieve)
        multiplier = 1

        for factor in prime_factors:
            exponent = prime_factors[factor]
            modulo = exponent % power

            if modulo != 0:
                multiplier *= (factor ** (power - modulo))
            
        
        ans += multiplicand[multiplier]
        cur_multiplicand = 1
        
        for factor in prime_factors:
            exponent = prime_factors[factor]
            modulo = exponent % power
            cur_multiplicand *= (factor ** modulo)
            
        multiplicand[cur_multiplicand] += 1
    
    print(ans)

main()

Time Complexity: O(n*log(n))

Any element of the array works. Why?

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

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

main()

To determine the minimum number of bacteria needed to achieve exactly x bacteria in the box at some point, we can represent x in binary form. We will then iterate through each bit in the binary representation of x, starting from the least significant bit to the most significant bit.

For each bit that is equal to 1, we will add one bacterium into the box on the corresponding day. Specifically, if the bit is 1at position i, we will add the bacterium on the morning of the (n+1-i)th day, where n is the total number of bits in the binary representation of x.

After iterating through all the bits, the box will contain exactly x bacteria at the noon of the nth day. Therefore, the minimum number of bacteria needed is equal to the number of 1s in the binary representation of x.

x = int(input())
ans = 0

for i in range(32):
    if x & (1 << i):
        ans += 1

print(ans)

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

MOD = 1000000007
noOfTests = int(input())

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

    ans = 0
    mult = 1

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

    print(ans)

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

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

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

main()

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

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

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

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

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


solve()

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

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

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

main()

Consider the strategy of forming teams based on the power of the players. How can this strategy be optimized to maximize the number of wins?

How can sorting help you come up with a strategy?

To maximize the number of wins, we can sort the candidate players in decreasing order of power and form teams by picking a player with the highest power and pairing them with the player with the lowest power. This strategy ensures that we use the highest power available while minimizing the number of players needed to form a team with a particular power.

We can then leverage Pak Chanek's ability to change the power of players in a team by increasing their power to the maximum available power in the team. This increases the chances of winning a match by ensuring that the team's total power is as high as possible.

To determine the maximum number of wins, we can iterate through the formed teams and count the number of teams that can defeat an enemy team with a specified power. This can be done by comparing the total power of the team with the power of the enemy team and checking if it is strictly greater.

n, d = map(int, input().split())
players = sorted(list(map(int, input().split())), reverse=True)

num_wins = 0
right = n - 1

for left in range(n):
    if left > right:
        break

    curr = players[left]

    while right > left and curr <= d:
        curr += players[left]
        right -= 1

    num_wins += int(curr > d)

print(num_wins)

Simulate the program.

Simulate the program by simulating the recursion stack. Since we only have "add" operations and a for loop we can use simply multiply nest loop results.

Time Complexity — O(N) Space Complexity — O(N)

from sys import stdin

n = int(stdin.readline().strip())
stack = [[1, 0]]

for _ in range(n):
    command = stdin.readline().strip()

    if command == "add":
        stack[-1][1] += 1
    elif command == "end":
        iterations, add = stack.pop()
        stack[-1][1] += iterations * add
    else:
        _, iterations = command.split()
        stack.append([int(iterations), 0])

if stack[-1][1] > (2**32 — 1):
    print("OVERFLOW!!!")
else:
    print(stack[-1][1])

Try sorting.

After sorting we can observe that the target rectangle area should be $$$a_{i} \cdot a_{4n}$$$. Then we just need to check for each $$${i}$$$ from 1 to n that $$$a_{2i-1}=a_{2i}$$$ and $$$a_{4n-2i+1}=a_{4n-2i+2}$$$ and $$$a_{2i-1}\cdot a_{4n-2i+2}=area$$$. If all conditions are satisfied for all i then the answer is "YES". Otherwise, the answer is "NO".

from sys import stdin, stdout

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

for _ in range(t):
    n = int(stdin.readline().strip())
    arr = list(map(int, stdin.readline().split()))
    arr.sort()

    i, j = 0, len(arr) - 1

    ok = True

    area = arr[i] * arr[j]

    while i < j:
        if arr[i] == arr[i + 1] and arr[j] == arr[j - 1] and arr[i] * arr[j] == area:
            i += 2
            j -= 2
        else:
            ok = False
            break
    
    print("YES" if ok else "NO")

Look for an optimal way to arrange the emotes.

The optimal way to arrange the emotes is to choose a chunk of k of the most potent emote separated by a single emote of the second most potent emote. Eg: Let's say "a" is the most potent emote and "b" is the second most potent. The best way to arrange the emotes is like: $$${"a_1, a_2, a_3 .... a_k, b, a_1, .... a_k, b , a_1..."}$$$

from sys import stdin, stdout

n, m, k = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))
arr.sort(reverse=True)

chunk_len = k + 1

full = (arr[0] * k + arr[1]) * (m // chunk_len)
rem = m % chunk_len

part = arr[0] * min(rem, k)
rem -= min(rem, k)

part += arr[1] * rem

print(full + part)

What happens as we increase or decrease "k" in regard to the damage done to the dragon?

Use binary search to look for the minimum k that deals at least h damage to the dragon.

from sys import stdin

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

for _ in range(t):
    n, h = map(int, stdin.readline().split())

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

    left = 1
    best = right = h

    while left <= right:
        mid = (left + right) // 2

        curr_max = -1
        damage = 0

        for time in arr:
            damage += mid - max(curr_max - time, 0)
            curr_max = time + mid

        if damage >= h:
            best = mid
            right = mid - 1
        else:
            left = mid + 1

    print(best)

Try Binary Search.

Use binary search to find the position of the smallest name larger than the given name.

from sys import stdin
 
n = int(stdin.readline().strip())
queue = list(stdin.readline().strip().split())
q = int(stdin.readline().strip())
 
 
for _ in range(q):
    left, right = 0, n - 1
    val = stdin.readline().strip()
    best = len(queue)
 
    while left <= right:
        mid = (left + right) // 2
 
        if queue[mid] < val:
            left = mid + 1
        else:
            best = mid
            right = mid - 1
 
    print(best)

from sys import stdin
import
 
n = int(stdin.readline().strip())
queue = list(stdin.readline().strip().split())
q = int(stdin.readline().strip())
 
 
for _ in range(q):
    left, right = 0, n - 1
    val = stdin.readline().strip()
    print(bisect_right(queue, val))

Given a choice of dividers which one would give you the most outlets and how much.

Given a choice of dividers the one with the maximum value of outlets would have the most outlets, if we say the chosen divider has ai outlets and we initially have s outlets after using the divider we would have s + ai — 1 since we have to use one of the existing outlets. Until we have enough outlets repeat this.

testcases = int(input())
for i in range(testcases):
    students, m = map(int, input().split())
    dividers = list(map(int, input().split()))

    dividers.sort(reverse=True)

    outlets = 2
    dividers_used = 0

    while dividers_used < m and outlets < students:
        outlets += dividers[dividers_used] - 1
        dividers_used += 1

    if outlets < students:
        print(-1)
    else:
        print(dividers_used)

Try to see the different kinds of ways of using the elevator and stairs.

There are 2^4 ways of arranging elevators and stair moves. Out of these arrangements, there are only some that make sense.

These are a different kind of arrangements: e, e, s, s; e, s, s, s; s, e, e, e...

Out of these configurations we can see that once we start using the elevator it doesn't make sense to go back to the stairs since if the elevator is less efficient than the stairs you shouldn't take the elevator but if not you should continue using the elevator since going back to the stairs wouldn't give you any better time. So the configurations you have to check are: use stairs only, walk to the elevator then use it, and use the elevator only.

t = int(input())
 
for i in range(t):
    wt, et, ef = list(map(int, input().split()))
    #         stairs, walk then elevator,        use elevator only
    print(min(wt * 4, wt * (ef) + et * (4 - ef), et * (ef + 4)))

Find a way to count subarrays with a sum less than some value x.

To find subarrays with a sum less than some value x we will use a sliding window, we expand our window until adding the next element would make its sum exceed x then we can be sure there are len(sliding window) subarrays with sum less than x since all the numbers are positive. To find subarrays with a sum between l and r, find the number of subarrays with a sum less than r + 1 and l then the answer would be the difference.

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


def sub_arrays_with_sum_less_than(target):
    runningSum = answer = left = 0

    for right in range(len(nums)):
        runningSum += nums[right]

        while runningSum >= target:
            runningSum -= nums[left]
            left += 1

        answer += right - left + 1

    return answer


print(sub_arrays_with_sum_less_than(end + 1) - sub_arrays_with_sum_less_than(start))

Think of merge sort.

We can notice that single-elimination bracket and merge sort have a similar process. We can leverage our knowledge in implementing the simulation for the game. But we have other rules, namely, we say a player has a possibility of moving forward if either there is a player with a lower rating or with absolute diff less than k. So if we can plug the check for winning possibility we can successfully simulate the game and find our possible winners.

from sys import stdin, stdout

# Reading input values from standard input
n, k = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))

# Function to recursively solve the problem
def solve(i, count, k):
    # Base case, when only one element is left in a sub-array
    if count == 1:
        return [i]

    # Divide the sub-array into two halves and solve each recursively
    left = solve(i, count // 2, k)
    right = solve(i + (count // 2), count // 2, k)

    # Merge the two sorted halves while checking the difference between elements
    merged = []
    l_ptr = r_ptr = 0
    left_min, right_min = arr[left[0]], arr[right[0]]

    while l_ptr < len(left) and r_ptr < len(right):
        if arr[left[l_ptr]] <= arr[right[r_ptr]]:
            if right_min - arr[left[l_ptr]] <= k:
                merged.append(left[l_ptr])
            l_ptr += 1
        else:
            if left_min - arr[right[r_ptr]] <= k:
                merged.append(right[r_ptr])
            r_ptr += 1

    # Add any remaining elements from left or right halves while checking the difference between elements
    while l_ptr < len(left) and right_min - arr[left[l_ptr]] <= k:
        merged.append(left[l_ptr])
        l_ptr += 1

    while r_ptr < len(right) and left_min - arr[right[r_ptr]] <= k:
        merged.append(right[r_ptr])
        r_ptr += 1

    # Return the merged and sorted sub-array
    return merged


# Print the sorted and transformed sub-array obtained by calling the solve() function
print(*sorted(map(lambda x: x + 1, solve(0, 2**n, k))))

Try to see how to check if an index can be a start for a new bus.

Any multiple of 6 greater than 6 can be described as a linear combination of 12 and 18.

Find the sum of a subarray with size 12 that started at 0 or 6 * b + 1, b being a positive integer.

from sys import stdin

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

for _ in range(t):
    n = int(stdin.readline().strip())
    nums = list(map(int, stdin.readline().split()))

    prefix_sums = []
    running_sum = 0

    for num in nums:
        running_sum += num
        prefix_sums.append(running_sum)

    # To avoid having to check if i - 1 is out of bounds
    prefix_sums.append(0)

    # The best we can do is to take the first 12
    best = prefix_sums[min(n - 1, 11)]

    for i in range(12, n, 6):
        # Check if the next 12 is better than the current best
        best = min(best, prefix_sums[min(i + 11, n - 1)] - prefix_sums[i - 1])

    print(best)

Try to see what kinda pairing creates optimal time.

The optimal matching starts by considering the smallest 2 ^ n — 1 as a base and changing the elements to be paired, then moving the window by 2 ^ n — 2, 2 ^ n — 3... and so on. The element determining the session time will be the largest among the elements in the current window and we can run the 2 ^ n — 1 then 2 ^ n — 2 then 2 ^ n -3... session for each window respectively.

n, k = list(map(int, input().split()))
 
nums = sorted(list(map(int, input().split())), reverse=True)
 
curr = 1 << n
total = 0
while k > 0:
    curr //= 2
    total += min(k, curr) * nums[curr]
    k -= min(k, curr)
print(total)

Try Binary Search.

Use binary search to find the position of the smallest name larger than the given name.

from sys import stdin
 
n = int(stdin.readline().strip())
queue = list(stdin.readline().strip().split())
q = int(stdin.readline().strip())
 
 
for _ in range(q):
    left, right = 0, n — 1
    val = stdin.readline().strip()
    best = len(queue)
 
    while left <= right:
        mid = (left + right) // 2
 
        if queue[mid] < val:
            left = mid + 1
        else:
            best = mid
            right = mid - 1
 
    print(best)

from sys import stdin
import
 
n = int(stdin.readline().strip())
queue = list(stdin.readline().strip().split())
q = int(stdin.readline().strip())
 
 
for _ in range(q):
    left, right = 0, n — 1
    val = stdin.readline().strip()
    print(bisect_right(queue, val))

Given a choice of dividers which one would give you the most outlets and how much.

Given a choice of dividers the one with the maximum value of outlets would have the most outlets, if we say the chosen divider has ai outlets and we initially have s outlets after using the divider we would have s + ai — 1 since we have to use one of the existing outlets. Until we have enough outlets repeat this.

testcases = int(input())
for i in range(testcases):
    students, m = map(int, input().split())
    dividers = list(map(int, input().split()))

    dividers.sort(reverse=True)

    outlets = 2
    dividers_used = 0

    while dividers_used < m and outlets < students:
        outlets += dividers[dividers_used] - 1
        dividers_used += 1

    if outlets < students:
        print(-1)
    else:
        print(dividers_used)

Try to see the different kinds of ways of using the elevator and stairs.

There are 2^4 ways of arranging elevators and stair moves. Out of these arrangements, there are only some that make sense.

These are a different kind of arrangements: e, e, s, s; e, s, s, s; s, e, e, e...

Out of these configurations we can see that once we start using the elevator it doesn't make sense to go back to the stairs since if the elevator is less efficient than the stairs you shouldn't take the elevator but if not you should continue using the elevator since going back to the stairs wouldn't give you any better time. So the configurations you have to check are: use stairs only, walk to the elevator then use it, and use the elevator only.

t = int(input())

for i in range(t): wt, et, ef = list(map(int, input().split())) # stairs, walk then elevator, use elevator only print(min(wt * 4, wt * (ef) + et * (4 — ef), et * (ef + 4)))

Find a way to count subarrays with a sum less than some value x.

To find subarrays with a sum less than some value x we will use a sliding window, we expand our window until adding the next element would make its sum exceed x then we can be sure there are len(sliding window) subarrays with sum less than x since all the numbers are positive. To find subarrays with a sum between l and r, find the number of subarrays with a sum less than r + 1 and l then the answer would be the difference.

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


def sub_arrays_with_sum_less_than(target):
    runningSum = answer = left = 0

    for right in range(len(nums)):
        runningSum += nums[right]

        while runningSum >= target:
            runningSum -= nums[left]
            left += 1

        answer += right - left + 1

    return answer


print(sub_arrays_with_sum_less_than(end + 1) - sub_arrays_with_sum_less_than(start))

Think of merge sort.

We can notice that single-elimination bracket and merge sort have a similar process. We can leverage our knowledge in implementing the simulation for the game. But we have other rules, namely, we say a player has a possibility of moving forward if either there is a player with a lower rating or with absolute diff less than k. So if we can plug the check for winning possibility we can successfully simulate the game and find our possible winners.

from sys import stdin, stdout

# Reading input values from standard input
n, k = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))

# Function to recursively solve the problem
def solve(i, count, k):
    # Base case, when only one element is left in a sub-array
    if count == 1:
        return [i]

    # Divide the sub-array into two halves and solve each recursively
    left = solve(i, count // 2, k)
    right = solve(i + (count // 2), count // 2, k)

    # Merge the two sorted halves while checking the difference between elements
    merged = []
    l_ptr = r_ptr = 0
    left_min, right_min = arr[left[0]], arr[right[0]]

    while l_ptr < len(left) and r_ptr < len(right):
        if arr[left[l_ptr]] <= arr[right[r_ptr]]:
            if right_min - arr[left[l_ptr]] <= k:
                merged.append(left[l_ptr])
            l_ptr += 1
        else:
            if left_min - arr[right[r_ptr]] <= k:
                merged.append(right[r_ptr])
            r_ptr += 1

    # Add any remaining elements from left or right halves while checking the difference between elements
    while l_ptr < len(left) and right_min - arr[left[l_ptr]] <= k:
        merged.append(left[l_ptr])
        l_ptr += 1

    while r_ptr < len(right) and left_min - arr[right[r_ptr]] <= k:
        merged.append(right[r_ptr])
        r_ptr += 1

    # Return the merged and sorted sub-array
    return merged


# Print the sorted and transformed sub-array obtained by calling the solve() function
print(*sorted(map(lambda x: x + 1, solve(0, 2**n, k))))

Try to see how to check if x persons can be transported using buses of sizes 18 and 12.

Any multiple of 6 greater than 6 can be described as a linear combination of 12 and 18.

Find the sum of a subarray with size 12 that started at 0 or 6 * b + 1, b being a positive integer.

from sys import stdin

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

for _ in range(t):
    n = int(stdin.readline().strip())
    nums = list(map(int, stdin.readline().split()))

    prefix_sums = []
    running_sum = 0

    for num in nums:
        running_sum += num
        prefix_sums.append(running_sum)

    # To avoid having to check if i - 1 is out of bounds
    prefix_sums.append(0)

    # The best we can do is to take the first 12
    best = prefix_sums[min(n - 1, 11)]

    for i in range(12, n, 6):
        # Check if the next 12 is better than the current best
        best = min(best, prefix_sums[min(i + 11, n - 1)] - prefix_sums[i - 1])

    print(best)

Try to see what kinda paring creates optimal time.

The optimal matching starts by considering the smallest 2 ^ n — 1 as a base and changing the elements to be paired, then moving the window by 2 ^ n — 2, 2 ^ n — 3... and so on. The element determining the session time will be the largest among the elements in the current window and we can run the 2 ^ n — 1 then 2 ^ n — 2 then 2 ^ n -3... session for each window respectively.

n, k = list(map(int, input().split()))
 
nums = sorted(list(map(int, input().split())), reverse=True)
 
curr = 1 << n
total = 0
while k > 0:
    curr //= 2
    total += min(k, curr) * nums[curr]
    k -= min(k, curr)
print(total)

Left as an Exercise.

Left as an Exercise.

Implementation: The product of several integers is equal to 1 if and only if each of these numbers is 1 or −1, and there must be an even number of −1 (else the product would give us a negative number).

Let's be greedy to minimize our cost. Would it be good/optimal to change a positive number to -1? No, because 1 is closer to all positive numbers. By the same logic, it is good to shift all negative numbers to -1. Therefore, We will have to reduce every positive a[i] at least to one, and we have to spend at least a[i] - 1 coin on this (decrement a[i] until it reaches 1). Similarly, we will have to increase every negative a[i] at least to −1, for this we will spend at least −1−a[i] coins. Note that we haven't touched the zeros yet.

Let's move to the second criteria (having even -1s). If we, currently, have odd -1s, we have two options, either to change one -1 to 1 (which would cost us 1 - (-1) = 2 or change one zero to -1 (which would cost us 0 -(-1) = 1). The later option is optimal. Therefore, whenever we have zeros in our list, change one of them to -1 and the others to 1. However, if there are no zeros, we would be left with only the first option with a cost of 2.

TIME: O(N)

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

coins = pos = neg = zero = 0

for x in a:
    if x == 0:
        zero += 1
        coins += 1
    elif x > 0:
        coins += x - 1
        pos += 1
    else:
        coins += -1 - x 
        neg += 1

if neg % 2 == 1 and zero == 0:
    coins += 2

print(coins)

Sorting: All you need is to swap the current minimum with the ith element each time (Selection Sort). Implement selection sort while keeping track of the swaps you make. For each index, you will be doing at max 1 swap. Therefore, the number of swaps never exceeds n.

Time: O(N^2)

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

swaps = []

for i in range(n):
    mn_index = i
    for j in range(i + 1, n):
        if a[j] < a[mn_index]:
            mn_index = j 
    swaps.append((i, mn_index))
    a[mn_index], a[i] = a[i], a[mn_index]

print(len(swaps))
for swap in swaps:
    print(*swap)

Two Pointers: The constraint -seats has to be on the same row or column- simplifies the problem. Let's brute force and find the number of possible ways for each row and column. We can find out how many consecutive empty positions in every row and column separately and add them together to form the final answer. We can use two pointers to keep track of the left most open and right most open positions.

If the length of consecutive empty positions is larger than k, then we can add length−k+1 to the final answer.

But, be careful. When k=1, the algorithm shown above gives twice the correct value. Can you see why?

TIME: O(NM)

n, m, k= map(int,input().split())
matrix = [input() for _ in range(n)]

ways = 0

# count adjacent horizontal seats
for i in range(n):
    count = 0
    for j in range(m):
        if matrix[i][j] == '*':
            ways += max(0, count - (k - 1))
            count = 0
        else:
            count += 1
    ways += max(0, count - (k - 1))
        
# count adjacent vertical seats
for j in range(m):
    count = 0
    for i in range(n):
        if matrix[i][j] == '*':
            ways += max(0, count - (k - 1))
            count = 0
        else:
            count += 1
    ways += max(0, count - (k - 1))
        
if k == 1:
    ways //= 2
    
print(ways)

n, m, k= map(int,input().split())
matrix = [input() for _ in range(n)]

ways = 0

# count adjacent horizontal seats
for row in range(n):
    left = 0
    for right in range(m):
        if matrix[row][right] == '*':
            left = right + 1
        elif right - left + 1 >= k:
            ways += 1 
        
# count adjacent vertical seats
for col in range(m):
    left = 0
    for right in range(n):
        if matrix[right][col] == '*':
            left = right + 1
        elif right - left + 1 >= k:
            ways += 1
        
if k == 1:
    ways //= 2
    
print(ways)

Two pointers: Let's perform the process in reverse: we will remove the first and last character of the string, if these two characters are different. We should do this as long as possible, since we need to find the shortest initial string.

So the algorithm is straightforward: keep track of the left and right characters, and if they are different, remove both. Otherwise, output the length of the current string.

Time: O(N)

for _ in range(int(input())):
    n, s = int(input()), input()
    l, r = 0, n - 1
    while l < r:
        if s[l] == s[r]:
            break 
        l += 1
        r -= 1
    print(r - l + 1)

Sorting & Two pointers: There are different ways to solve this problem. But let's stick with the simplest one for now. Let's simplify the question by restating it as how many boys can be paired with girls at maximum. The first thing that might come to your mind is process the boys one by one and try to pair them with one girl if there is a match. That looks good. Let's try it.

Eg. Let a = [2, 3] and b = [2, 1]. Now let's pair the first boy 2 with the first girl 2. Next when we try to pair the second boy 3 with the second girl 1, we notice that abs(3 - 1) > 1 and we return [(2, 2)] as our end result. There is one problem though. We could pair them as [(2, 1), (3, 2)] and could've gotten more pairs. Hmm... Is our approach wrong? Yes. But with slight improvement (__Sorting__), we can make it right. What is the problem in our previous approach? Matching in a non-optimal way. So to fix this issue, sort the boys and pick a pair for the boys (if there is a match) one by one. One constraint would be to pick the smallest value from the perfectly matched girls, leaving more options for later boys. Intuition: Boys with large values need girls with large values and boys with small values need girls with small values.

Time: O(NlogN + MlogM)

n, a = int(input()), sorted(map(int, input().split()))
m, b = int(input()), sorted(map(int, input().split()))

pairs = i = j = 0
while i < n and j < m:
    if abs(a[i] - b[j]) < 2:
        pairs += 1
        i += 1
        j += 1
    elif a[i] < b[j]:
        i += 1
    else:
        j += 1

print(pairs)

Time: O(NlogN + M)

from collections import Counter

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

a.sort()

count = Counter(b)

pairs = 0
for x in a:
    if count[x - 1]:
        count[x - 1] -= 1
        pairs += 1
    elif count[x]:
        count[x] -= 1
        pairs += 1
    elif count[x + 1]:
        count[x + 1] -= 1
        pairs += 1

print(pairs)

Sorting & Two pointers: Straightforward implementation would be enough. Sort the input so that you can make close elements adjacent to each other. For each index increase the index as long as the difference between the next index's value and the current index's value is not more than one.

Time: O(NlogN)

pages = sorted(list(map(int, input().split(','))))

n = len(pages)

i, res = 0, []

while i < n:

    j = i + 1
    while j < n and pages[j - 1] + 1 >= pages[j]:
        j += 1

    if pages[i] == pages[j - 1]:
        res.append(f"{pages[i]}")
    else:
        res.append(f"{pages[i]}-{pages[j - 1]}")

    i = j 

print(','.join(res))

Sorting: We are ordered to buy n items in total and at least k items now (with the current week's market price). Our goal is to maximize profit. Therefore, we try to buy items that gives us high profit. Which ones? Let's see with an example.

Eg. Let k = 1, a = [2, 2] and b = [4, 10]. We have three options.
1. Buy the first item this week and the second item next week. Total price = 2 + 10 = 12
2. Buy the second item this week and the first item next week. Total price = 4 + 2 = 6
3. Buy both items this week. Total price = 2 + 2 = 4

Q:
- Why is the second option better than the first one? Because we bought an item whose price has increased by much during the next week. The first option buys the item whose price didn't increase by much and puts the other for next week. But the second option wisely chooses the item whose value increased by much (because it would've cost more if it would've been put for next week) and puts the ones that didn't change by much for next week. Conclusion: Always prefer the item whose price increased by much over the ones that changed by smaller value.

- Why is the third option better than the second one? Because the third option buys extra items even after all k items bought. Conclusion: If there are still some items left that are not bought but could give profit buy them.

To solve this problem we need at first to sort all items in increasing order of values a[i] - b[i]. Then let's iterate through sorted array. If for the current item x we did not buy k items now and if after discounts it will cost not more than now, we need to buy it now and pay a[x], in the other case we need to buy item x after discounts and pay b[x].

Time: O(NlogN)

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

c = sorted(range(n), key=lambda i: a[i] - b[i])

res = 0
for i in range(n + 1):
    if i >= k and (i == n or a[c[i]] - b[c[i]] > 0):
        break 
    res += a[c[i]]

for j in range(i, n):
    res += b[c[j]]

print(res)

This one is implementation problem. Let's break down the algorithm and implement it step by step.

Step 1: Move elements from array A to array B. In this step, have a left_arr and right_arr, and then insert elements of A one by one, alternating between the two sub-arrays. You don't have to worry when the total length is even. After this step, we have moved all elements from array A to array left_arr and right_arr. Array A is now empty, and array B(left_arr + right_arr) has n elements.

Step 2: Move elements from array B(which is left_arr + right_arr) to array C. In this step, we merge the two sub-arrays left_arr and right_arr to form the final array C . The merging is done by taking the the smaller element from the top of the left_arr vs right_arr if they have equal size if not we take element from the array with larger size

Finally check if the final c is sorted by c == list(sorted(x)).

Where should be the minimum and the maximum element of the array in order for the matrix to be beautiful.

If a matrix is beautiful, then its minimum is in the upper left corner, and its maximum is in the lower right corner (and vice versa). If you rotate it, the element from the upper left corner goes to the upper right corner, and the element from the lower right corner goes to the lower left corner — so these elements are still in the opposite corners. No matter how many times we rotate a beautiful matrix, its minimum and maximum elements will be in the opposite corners — and the opposite is true as well; if you have a 2×2 matrix with minimum and maximum elements in opposite corners, it can be rotated in such a way that it becomes beautiful.

So, all we need to check is that the minimum and the maximum elements are in the opposite corners.

def solve():
    ROWS, COLS = 2, 2
    matrix = []
    
    for i in range(ROWS):
        matrix.append(list(map(int,input().split())))
    
    x1, y1 = 0, 0
    x2, y2 = 0, 0
    
    for i in range(ROWS):
        for j in range(COLS):
            if matrix[i][j] < matrix[x1][y1]:
                x1, y1 = i, j
            
            if matrix[i][j] > matrix[x2][y2]:
                x2, y2 = i, j
    
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)
    
    if dx + dy > 1:
        print("YES")
    else:
        print("NO")

def main():
    num_tests = int(input())
    
    for test in range(num_tests):
        solve()

main()

Note, that if the array has two intersecting continuous non-decreasing subsequence, they can be combined into one. Therefore, you can just pass the array from left to right. If the current subsequence can be continued using the i-th element, then we do it, otherwise we start a new one. The answer is the maximum subsequence of all the found ones.

def main():
    size = int(input())
    nums = list(map(int, input().split()))
    
    max_subsegment = 0
    cur_segment = 1
    for i in range(1, size):
        if nums[i] >= nums[i-1]:
            cur_segment += 1
        else:
            max_subsegment = max(max_subsegment, cur_segment)
            cur_segment = 1
    
    max_subsegment = max(max_subsegment, cur_segment)
    print(max_subsegment)

main()

Try brute force.

For each string s, brute force all strings x and y such that s=x+y. There are at most 7 such strings, because s has length at most 8. Then check if both x and y appear in the array using some data structure.

def solve():
    num_strings = int(input())
    strings = []
    
    for i in range(num_strings):
        string = input()
        strings.append(string)
    
    indices = set(strings)
    ans = ['0' for i in range(num_strings)]
    for i in range(num_strings):
        for j in range(1, len(strings[i])):
            prefix = strings[i][: j]
            suffix = strings[i][j :]
            
            if prefix in indices and suffix in indices:
                ans[i] = '1'
    
    return ''.join(ans)

def main():
    num_tests = int(input())
    
    for test in range(num_tests):
        print(solve())

main()

May be sorting might help.

In order to create a team with the maximum number of students, it is important to ensure that all members of the team have similar levels of programming skill. A way to do this is by taking the list of students and sorting them in increasing order according to their programming skills. After this, a sliding window technique can then be employed to find the maximum size team window that satisfies the given constraint; i.e. that there is no more than 5 unit difference in skill level between each pair of members. The resulting window size will indicate how many students can be placed together in a team without breaking their specified constraint.

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

nums.sort()
ans = 0
left = 0
for right in range(length):
    while (nums[right] - nums[left]) > 5:
        left += 1
    
    ans = max(ans, right - left + 1)
    
print(ans)

Let's sort the difference array(ai — bi)

Let's rewrite the inequality

Let's find pair of topics which fulfills the rewritten inequality

The given problem requires finding the number of pairs of elements (i,j) in two arrays a and b, such that the sum of the differences between corresponding elements in the two arrays (Di = ai — bi and Dj = aj — bj) is positive. To simplify this problem, we can create a new array D where Di is the difference between ai and bi, and sort this array.

Rewriting the inequality gives us:

(ai + aj) > (bi + bj)

    (ai - bi) + (aj - bj) > 0

    Di + Dj > 0

Then, we can iterate through the elements of D from left to right and count the number of pairs (i,j) such that Di and Dj sum to positive and i < j.

length = int(input())

arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
diff = [0] * length

for i in range(length):
    diff[i] = arr1[i] - arr2[i]

diff.sort()

total = 0
beg = 0
end = length - 1

# find pairs which gives Di + Dj > 0
while end >= beg:
    while beg < end and diff[beg] + diff[end] <= 0:
        beg += 1

    total += max(end - beg, 0)
    end -= 1

print(total)

When is it impossible to reorder the elements?

Maybe sorting the elements might help.

If all elements in the array are equal, there's no solution. Otherwise, sort the array. The sum of the second half will indeed be greater than that of the first half.

def main():
    half = int(input())
    
    nums = list(map(int, input().split()))
    nums.sort()
    
    if nums[0] == nums[-1]:
        print(-1)
    else:
        print(*nums)

main()

Greedily take the smallest character in both strings. What's the exception to this?

We can't take the smallest character in both strings when we've already took k elements from the string we chose. Denote A as the number of characters we've took from string str1 in the last few consecutive moves and denote B the same for str2. If A = k, then we have to take the smallest character in string str2 instead of possibly str1. If B = k, then we have to take the smallest character in string str1 instead of possibly str2.

Remember to reset A to 0 when you take a character from b. Similarly, reset B to 0 when you take a character from a.

def solve():
    len_str1, len_str2, k = map(int, input().split())
 
    str1 = list(input())
    str2 = list(input())
    
    str1.sort()
    str2.sort()
    
    output = []
    str1_cnt = 0
    str2_cnt = 0
    i = 0
    j = 0
    
    while i < len_str1 and j < len_str2:
        
        if ((str1[i] < str2[j] and str1_cnt < k) or str2_cnt == k):
            output.append(str1[i])
            str1_cnt += 1
            str2_cnt = 0
            i += 1
            
        else:
            output.append(str2[j])
            str2_cnt += 1
            str1_cnt = 0
            j += 1
    
    print(''.join(output))
    
def main():
    num_tests = int(input())
    
    for i in range(num_tests):
        solve()
 
main()

Lets sort boys and girls by skill. Let’s say

• boys_ptr = represents the index of boys_skill array
• girls_ptr = represents the index of girls_skill array

And let’s assume that the programming skill of a boy at boys_ptr is greater than the programming skill of the girl at girls_ptr index.

If the absolute difference in skill levels between a boy at boys_ptr and a girl at girls_ptr does not exceed 1, we add 1 to our answer and increment both boys_ptr and girls_ptr by 1.

If the absolute programming skill difference between a boy at the boys_ptr index and a girl at the girls_ptr index is found to be greater than one, then it is certain that any boy at an index beyond boys_ptr will also have an absolute skill difference of more than one when paired with the same girl at girls_ptr. Therefore, it is impossible to pair this girl with any of these boys. So we have to increment the girls_ptr and check the same thing.

Vice versa if the skill of a girl is greater than skill of a boy

-Time Complexity: O(n.log n)

def main():
    num_boys = int(input())
    boys_skill = list(map(int, input().split()))
    
    num_girls = int(input())
    girls_skill = list(map(int, input().split()))
    
    boys_skill.sort()
    girls_skill.sort()
    
    boys_ptr = 0
    girls_ptr = 0
    num_pairs = 0
    
    while boys_ptr < num_boys and girls_ptr < num_girls:
        cur_boy_skill = boys_skill[boys_ptr]
        cur_girl_skill = girls_skill[girls_ptr]
        
        if abs(cur_boy_skill - cur_girl_skill) <= 1:
            num_pairs += 1
            boys_ptr += 1
            girls_ptr += 1
            
        elif cur_boy_skill < cur_girl_skill:
            boys_ptr += 1
        
        else:
            girls_ptr += 1
    
    print(num_pairs)

main()

In order to minimize the cost:

• We must assign the lowest price from a list of prices to the toy that appears most often.
• We must assign the second lowest price from the list of prices to the toy that appears the second most number of times.
• We must assign the third lowest price from the list of prices to the toy that appears the third most number of times.
• …

In order to maximize the cost:

• We must assign the highest price from a list of prices to the toy that appears most often.
• We must assign the second highest price from the list of prices to the toy that appears the second most number of times.
• We must assign the third highest price from the list of prices to the toy that appears the third most number of times.
• …

from collections import defaultdict


def main():
    num_prices, num_toys = map(int, input().split())
    prices = list(map(int, input().split()))

    toys = defaultdict(int)
    for i in range(num_toys):
        toy = input()
        toys[toy] += 1

    count = list(toys.values())
    prices.sort()
    count.sort(reverse = True)

    min_price = 0
    max_price = 0
    
    toy = 0
    i = 0
    while toy < num_toys:
        min_price += (prices[i] * count[i])
        max_price += (prices[num_prices - 1 - i] * count[i]) 
        toy += count[i]
        i += 1
        
    print(min_price, max_price)

main()

We can find the number of ways to arrange k consecutive empty seats either in a row or a column by considering each row and column individually. For each row, we need to count the number of ways we can place k empty seats in consecutive order. Similarly, for each column, we need to calculate the number of ways we can place k empty seats in contiguous order. After counting the number of combinations for each row and column, we can simply add the two results together for our final answer.

How do we count the number of k consecutive empty seats in a row or column?

If the length of consecutive empty seats in a row or column is no smaller than k, we can count all the possible combinations of k consecutive empty seats adding up to that length. That is, for any given length len, (len-k+1) additional sets of k consecutive empty seats can be accounted for in our solution.

But, be careful. When k=1, the algorithm shown above is completely wrong. (Why?) So we need to deal with that situation separately.

def main():
    ROWS, COLS, k = map(int, input().split())
    
    seats = []
    for i in range(ROWS):
        seats.append(input())
     
    #find number of ways to arrange seats in each row   
    num_ways = 0
    for row in range(ROWS):
        empty_slots = 0
        
        for col in range(COLS):
            if seats[row][col] == '.':
                empty_slots += 1
            else:
                empty_slots = 0
            
            if empty_slots >= k:
                num_ways += 1
    
    #find number of ways to arrange seats in each column
    for col in range(COLS):
        empty_slots = 0
        
        for row in range(ROWS):
            if seats[row][col] == '.':
                empty_slots += 1
            else:
                empty_slots = 0
            
            if empty_slots >= k:
                num_ways += 1
    
    #handle k = 1 case
    if k == 1:
        num_ways //= 2
    
    print(num_ways)
 
main()

Use two pointers

In this problem, you can implement an algorithm opposite to that given in the condition. Let's maintain two pointers to the left-most and right-most unhandled element. Then, restoring the original array, you:

• put the left-most unhandled item in the first position
• put the right-most unhandled item in the second position
• put the left-most unhandled item in the third position
• put the right-most unhandled item in the fourth position ...

def solve():
    length_of_sequence = int(input())
    sequence = list(map(int, input().split()))
    
    left = 0
    right = length_of_sequence - 1
    write_left = True
    
    while left <= right:
        
        if write_left:
            print(sequence[left], end = ' ')
            left += 1
            
        else:
            print(sequence[right], end = ' ')
            right -= 1
        
        write_left = not write_left
    
    print()

def main():
    num_tests = int(input())
    for i in range(num_tests):
        solve()

main()

The product of multiple integers can only equal 1 if each of the integers are either 1 or -1, with an even number of -1s. To make this happen, we need to spend at least "ai — 1" coins for each positive integer "ai" to reduce it to 1 and spend at least "-1 — ai" coins for each negative integer "ai" to increase it to -1. If there are 0s among the numbers, we will need to spend at least "k" coins to replace each zero with either 1 or -1. If there are no zeros and the product is not equal to 1, it will require an additional 2 coins to change some 1s to -1s or some -1s to 1s.

length = int(input())

neg_cnt = 0
zero_cnt = 0
ans = 0

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

for i in range(length):
    if nums[i] == 0:
        ans += 1
        zero_cnt += 1
    elif nums[i] < 0:
        ans += (-1 - nums[i])
        neg_cnt += 1
    else:
        ans += nums[i] - 1

if neg_cnt % 2 == 1 and zero_cnt == 0:
    ans += 2

print(ans)

Try to think of a sorting algorithm where you can track the swapped elements

Use Selection sort to sort out the elements and when you do the swaps add the indices of both elements.

Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list

• Time-Complexity — O(N^2)
• Space-Complexity — O(N)

n = int(input())
arr = list(map(int, input().split()))
pairs = []


for i in range(len(arr)):
    min_idx = i
    for j in range(i + 1, len(arr)):
        
        if arr[min_idx] > arr[j]:
            min_idx = j
            
            
    if min_idx != i:
        pairs.append((i, min_idx))
        arr[min_idx], arr[i] = arr[i], arr[min_idx]

print(len(pairs))
for res in pairs:
    print(*res)

Use Two pointers approach

We claim that the answer is always 0 or 1. First, note we can't apply any operations if and only if each ')' symbol is left from each '(' symbol, so that the string looks as ')))(((((('.

The basic idea of the solution is to match '(' with ')' on the right side of it. We can use two pointers to do that.

• Time complexity: O(n)
• space Complexity: O(1)

def main():
    brackets = input()
    
    length = len (brackets)
    left = 0
    right = length - 1
    ans = []
    
    
    while (left < right):
        while (left < right and brackets[left] == ')'):
            left += 1
            
        
        while (left < right and brackets[right] == '('):
            right -= 1
            
        
        if (left < right):
            ans.append(left + 1)
            ans.append(right + 1)
        
        left += 1
        right -= 1
    
    
    ans.sort()
    
    if (len(ans) > 0):
        print(1)
        print(len(ans))
        print(*ans)
    else:
        print(0)
    
main()

What shall we do in order to keep the top view same as the original?

What shall we do in order to keep the right side view the same as the original?

• If we assume the stack of blocks as a matrix:
• • rows are represented the height of blocks at each index that is a[i].
• • Columns are represented by the indices

• In order for the top and right side view to be the same two things should be fulfilled

• • • In order to maintain the same top view from the original view, all columns containing blocks should leave at least one block remaining when the rest are removed. This way, the top view will remain unchanged.
• • • To maintain the right side view of the stack of blocks, it is necessary to keep at least one block in each row, starting from Row =1 up to the maximum height of the stack.

• To make the right side views of blocks the same would be to use blocks which have minimum heights in order to cover up rows with minimum values. While doing this we have to make sure there is at least on block that is left in each column.
• Example: a = [2, 3, 1, 4, 4] In order to make the right side view of the blocks identical to the original, all stacks of blocks with a height ranging from 1 to 4 must be present in each row between rows 1 and 4.

• The first block should be placed at index 2, to cover the row of 1. The second block should be placed at index 0 and will cover a row of 2. The third block should be placed at index 1 and will cover a value of 3. Finally, the fourth block can either be placed at index 3. Since we have to make sure that one block should be left at each index we can leave one block at index 4 and remove the rest.

  Time Complexity: O(n.log n)

def main():
    num_stacks, height_of_exhibit = map(int, input().split())
    heights = list(map(int, input().split()))
    
    height_to_build = 1
    max_height = max(heights)
    
    heights.sort()
    ans = 0
    
    for i in range(num_stacks):
        #we leave one block in each column and remove the rest
        ans += (heights[i] - 1)
        
        #if the current height is built move to the next
        if heights[i] >= height_to_build:
            height_to_build += 1
            
    
    #subtract number of unbuilt heights from answer
    ans -= (max_height - height_to_build + 1)
    print(ans)

main()

This problem uses the greedy technique, in which each player desires to take a card with a high score.

1. Let left_pointer and right_pointer represent the beginning and end of the array, respectively.
2. Then compare numbers at left_pointer and right_pointer and select the greatest of both.
3. Add the score of the chosen cards to the corresponding player.
4. The player turn can be identified by variable 'turn'. If turn is an even number, player 1(Wube) takes the turn; otherwise, player 2(Henok) takes the turn.
5. Continue until the left_pointer and right_pointer cross each other.

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

def main():
    #input
    length = int(input())
    numbers = list(map(int, input().split()))
    
    #initialize pointers
    left = 0
    right = length - 1
    turn = 0
    wube_score = 0
    henok_score = 0
    
    while left <= right:
        cur_max = 0
        
        if numbers[left] > numbers[right]:
            cur_max = numbers[left]
            left += 1
        
        else:
            cur_max = numbers[right]
            right -= 1
        
        if turn % 2 == 0:
            wube_score += cur_max
        else:
            henok_score += cur_max
        
        turn += 1
    
    print(wube_score, henok_score)

main()

if the keyboard key is broken we know it cannot type consecutive letters of length odd number.

which technique can we use to check the length of consecutive similar letters.

Since we want to know how many of consecutive similar letters are there, we can use two pointers, one to go through the string and one to count consecutive similar letters.

Then we check if that length is odd or even. If it is odd we can consider it as a working button and since we don't want to have duplicate buttons, we can use set.

Finally we will cast it to list and sort it to get the answer in alphabetical order and print it by joining the elements.

tests = int(input())
for _ in range(tests):
    string = input()
    size = len(string)
    left = 0
    answer = set()
    while left < size:
        right = left + 1
        count = 1
        while right < size and string[right] == string[right - 1]:
            count += 1
            right += 1
            left += 1
        if count % 2 == 1 and string[left] not in answer:
            answer.add(string[left])
        left += 1
    answer = list(answer)
    print("".join(sorted(answer)))

The main idea of my solution is that the answer should look like abb...bbbbbc: one character of type a, a block of characters of type b, and one character of type c. If we find all blocks of consecutive equal characters in our string, each candidate for the answer can be obtained by expanding a block to the left and to the right by exactly one character. So the total length of all candidates is O(n), and we can check them all.

Why does the answer look like abb...bbbbbc? If the first character of the substring appears somewhere else in it, it can be deleted. The same applies for the last character. So, the first and the last characters should be different, and should not appear anywhere else within the string. Since there are only three types of characters, the answer always looks like abb...bbbbbc.

from collections import defaultdict

num_tests = int(input())

for _ in range(num_tests):
    string = input()
    len_str = len(string)
    ans = len_str + 1
    
    freq = []
    for i in range(len_str):
        cur_char = string[i]
        if len(freq) == 0 or freq[-1][0] != cur_char:
            freq.append([cur_char, 1])
        else:
            freq[-1][1] += 1
    
    freq_size = len(freq)
    for i in range(1, freq_size - 1):
        if freq[i - 1][0] != freq[i + 1][0]:
            ans = min(ans, freq[i][1] + 2)
    
    if ans == len_str + 1:
        ans = 0
    
    print(ans)

We can use the sliding window technique to solve this problem. We extend our window until we find all the three characters 1, 2, 3. And we will try to shorten the interval as much as we can but we have to make sure that the three numbers are present in the substring.

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

from collections import defaultdict

num_tests = int(input())

for _ in range(num_tests):
    string = input()
    len_str = len(string)
    occurence = defaultdict(int)
    
    left = 0
    contained = 0
    ans = len_str + 1
    for right in range(len_str):
        char_at_right = string[right]
        occurence[char_at_right] += 1
        
        if occurence[char_at_right] == 1:
            contained += 1
        
        while contained >= 3:
            char_at_left = string[left]
            occurence[char_at_left] -= 1
            
            if occurence[char_at_left] == 0:
                contained -= 1
            
            left += 1
           
        if left > 0:
            ans = min(ans, right - left + 2)
    
    if ans == len_str + 1:
        ans = 0
    
    print(ans)
    
        

Simulate with sample examples

Assume the array given was [A,B,C,D] what would be the pattern when you simulate it?

What pattern can we see if we always remove the element at index 0.

• • let say we are given an array [A,B,C,D] and Let's always remove the element at index 0 and see the resulting pattern
• • first we delete A and subtract from the rest
• • • [B — A, C — A, D — A]
• • Then we delete the next sequence which is B — A
• • • [C — A — (B — A), D — A — (B — A)]
• • • which simplifies to [C — B, D — B]
• • Finally we delete the next sequence which is C — B
• • • [D — B — (C — B)]
• • • which simplifies to [D — C]

- So we can see that we only need two number whose difference is equal to k. so basically we need to find two numbers that meet the condition and print YES and if we can't get print NO

def solve():
    n , k = map(int , input().split())
    nums = list(map(int, input().split()))
    
    i = 0
    j = 1
    found = False
    nums.sort()
    while not found and j < n:
        difference = nums[j] - nums[i]
        if difference == k:
             found = True
        elif difference > k:
              i += 1
        else:
              j += 1
    
    if found:
        print("YES")
    else:
        print("NO")
        
def main():
    t = int(input())
    
    for _ in range(t):
        solve()

main()

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    occured = set()
    ok = False
    i = 0
    
    while not ok and i < n:
        x = a[i] - k
        y = a[i] + k
        
        if x in occured:
            ok = True
        
        if y in occured:
            ok = True
        
        occured.add(a[i])
        i += 1
        
    if ok:
        print("YES")
    else:
        print("NO")
        
    
def main():
    t = int(input())
    for i in range(t):
        solve()
main()

This solution involves solving for each column individually, by starting from the bottom and working towards the top. For each column, the row of the last obstacle seen is kept track of and initially set to n + 1, treating the floor as the (n + 1)th row of obstacles. If a new obstacle is encountered, the last row variable is updated. If a stone is encountered, it is moved to the row above the last obstacle seen and the last row variable is decreased by 1. This solution has a time complexity of O(nm) and is efficient, however slower alternatives that run in O(n^2*m) that simulate each stone falling are also accepted.

cases = int(input())

for _ in range(cases):
    ROWS, COLS = map(int , input().split())
    
    grid = []
    
    for _ in range(ROWS):
        temp = list(input())
        grid.append(temp)
    
    for cur_col in range(COLS):
        cur = ROWS
        for cur_row in range(ROWS - 1, -1, -1):
            
            if grid[cur_row][cur_col] == '*':
                cur -= 1
                
                if cur_row != cur:
                    grid[cur][cur_col] = '*'
                    grid[cur_row][cur_col] = '.'
                    
            elif grid[cur_row][cur_col] == 'o':
                cur = cur_row
                   
    
    for cur_row in range(ROWS):
        for cur_col in range(COLS):
            print(grid[cur_row][cur_col],end='')
        print()
    print()

Try sorting.

Sort the three numbers and return the second number.

Time Complexity — O(1) Space Complexity — O(1)

test_cases = int(input())

for i in range(test_cases):
    numbers = list(map(int, input().split()))
    numbers.sort()
    print(numbers[1])

Try sorting.

Sort the laptops based on their price, and for laptops with the same price sort based on quality. Check if a pair of neighboring laptops have different prices and decreasing quality exist.

Time Complexity — O(N*log(N)) Space Complexity — O(1)

length = int(input())
laptops = []

for i in range(length):
    price, quality = map(int, input().split())
    laptops.append((price, quality))

laptops.sort()

for i in range(length - 1):
    cur_laptop_price, cur_laptop_quality = laptops[i]
    next_laptop_price, next_laptop_quality = laptops[i + 1]

    if (
        cur_laptop_price != next_laptop_price
        and cur_laptop_quality > next_laptop_quality
    ):
        print("Happy Alex")
        exit()

print("Poor Alex")

Find an example that can't be sorted by reversing a subarray of it.

Create a sorted copy of the given array. Find the first and the last position where the two arrays differ, and reverse the segment between these positions. Check if the two arrays are equal.

Time Complexity — O(N log(N)) Space Complexity — O(N)

from math import inf


n = int(input())

array = list(map(int, input().split()))
sorted_array = sorted(array)

start, end = inf, -inf

for idx in range(n):
    if array[idx] != sorted_array[idx]:
        start = min(start, idx)
        end = idx

if start == inf:
    print("yes")
    print(1, 1)
else:
    i, j = start, end

    while i <= end:
        if array[i] != sorted_array[j]:
            print("no")
            exit()

        i += 1
        j -= 1

    print("yes")
    print(start + 1, end + 1)

How does sorting help?

What improvement can we make on the sorted array?

After sorting, if arr[-1] >= arr[-2] + arr[-3], what does this tell us?

To summarize, it involves 1) Sorting the array in non-decreasing order 2) Checking if the last element of the array is greater than or equal to the sum of the second-to-last and third-to-last elements. 3) If it is, print "NO" as there is no solution. 4) If it is not, swap the last and second-to-last elements of the array and print the new array.

Time Complexity — O(N log(N)) Space Complexity — O(1)

length = int(input())
nums = list(map(int, input().split()))
nums.sort()
​
if nums[-1] >= nums[-2] + nums[-3]:
    print("NO")
else:
    print("YES")
    nums[-1], nums[-2] = nums[-2], nums[-1]
    print(*nums)

Try to see the difference between two consecutive elements in the sequence below:

1, 2, 4, 8 ...
2^0, 2^1, 2^2, 2^3 ...

We are required to find the number of windows which could be increasing given the condition below: - If you multiply the first element by 2^0, the second element by 2^1, ..., and the (k+1)-st element by 2k, then this subarray is sorted in a strictly increasing order. Multiplying the first element by 2^0, the second by 2^1 ... and (k + 1)th element by 2^k means multiplying [i + 1]th element by 2 and checking if it's greater than [i]th element. Check if nums[i] < 2 * nums[i + 1] if the above condition is satisfied widen the window and check if the window is greater than k, if the above condition failed to hold, start the search from the index that failed the condition.

Time Complexity — O(N) Space Complexity — O(1)

def inpNum():
    return int(input())
def inpSepNum():
    return map(int, input().split())
def inpNumList():
    return list(map(int, input().split()))
test_cases = inpNum()
for _ in range(test_cases):
    n , k = inpSepNum()
    nums = inpNumList()
    subarrays = 0
    left = 0
    for right in range(1,n):
        # If the required condition failed move the left pointer to right
        if nums[right]*2 <= nums[right-1]:
            left = right
        # When the window size exceeds k increment subarrays
        if right - left >= k:
            subarrays += 1
    print(subarrays)

Try brute force.

We have two orientations for each rectangle, rotated by 90 or 270 degrees or by 0 or 180 degrees. So, we can try each of the four possibilities we can get by matching each orientations of the first rectangle to the two orientations of the second rectangle.

Time Complexity — O(1) Space Complexity — O(1)

testcases = int(input())

for _ in range(testcases):
    w_1, l_1 = map(int, input().split())
    w_2, l_2 = map(int, input().split())
    answer = "No"

    for (a, b) in [(w_1, l_1), (l_1, w_1)]:
        for (c, d) in [(w_2, l_2), (l_2, w_2)]:
            if a + c == b == d:
                answer = "Yes"

    print(answer)

You can always find an answer.

An odd number of negatives will result in a Negative Number

Positive numbers set or a set with positive numbers and an even number of negative numbers will result in a Positive set

Anything multiplied with a zero will be Zero

There is always at least one zero

Implement the following algorithms: Create three arrays: zero_array, positive_array, and negative_array. Put the numbers from the given array into their respective arrays. If there are even elements in negative_array, move an element to zero_array. If there are more than two elements in the negative_array, move two elements to the positive_array.

Time Complexity — O(N) Space Complexity — O(N)

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

zero_array = []
positive_array = []
negative_array = []

for num in array:
    if num < 0:
        negative_array.append(num)
    elif num > 0:
        positive_array.append(num)
    else:
        zero_array.append(num)

if len(negative_array) % 2 == 0:
    zero_array.append(negative_array.pop())

if len(negative_array) > 2:
    positive_array.append(negative_array.pop())
    positive_array.append(negative_array.pop())

print(len(negative_array), *negative_array)
print(len(positive_array), *positive_array)
print(len(zero_array), *zero_array)

Try to see a pattern at the intersection of the diagonals.

For each cell with a hash, check if its diagonally adjacent cells have a hash too.

Time Complexity — O(N^2) Space Complexity — O(1)

def solve(grid):
    directions = [(-1, -1), (1, 1), (-1, 1), (1, -1)]
    n = 8

    for row in range(1, n - 1):
        for col in range(1, n - 1):
            if grid[row][col] != "#":
                continue
            bishop = True
            for di, dj in directions:
                row_n, col_n = row + di, col + dj
                bishop &= grid[row_n][col_n] == "#"
            if bishop:
                return (row + 1, col + 1)

test_cases = int(input())

for _ in range(test_cases):
    input()
    grid = [input() for _ in range(8)]
    print(*solve(grid))

Try to see which cells interchange positions upon rotation.

First, we need some way to find cells that interchange positions; we can achieve this by using four pointers or a formula. After that, from the four cells that interchange positions, we figure out the count of the minority element and add it to our answer.

Time Complexity — O(N^2) Space Complexity — O(1)

from math import ceil

test_case = int(input())


for _ in range(test_case):
    n = int(input())

    grid = []
    for _ in range(n):
        row = [int(num) for num in input()]
        grid.append(row)

    cost = 0
    for row in range(ceil(n / 2)):
        for col in range(n // 2):
            count = sum(
                [
                    grid[row][col],
                    grid[col][-1 - row],
                    grid[-1 - row][-1 - col],
                    grid[-1 - col][row],
                ]
            )

            cost += min(count, 4 - count)
    print(cost)

List down the different types of paths with fewer than three turns.

Since we can only make two turns max, we have a limited kind of paths.

Paths 1 and 2 are just straight lines; paths 3, 4, 5, and 6 are parallel straight lines connected by an orthogonal line.

To check if such a path exists, paint a cross on S and T with "S" and "T", then try to find S+dots+T or T+dots+S row-wise or column-wise.

Time Complexity — O(N * M) Space Complexity — O(1)

from itertools import product


def paint_cross(s_row, s_col, char, grid, n):
    # down
    for i in range(s_row + 1, n):
        if grid[i][s_col] == ".":
            grid[i][s_col] = char
        else:
            break
    # up
    for i in range(s_row - 1, -1, -1):
        if grid[i][s_col] == ".":
            grid[i][s_col] = char
        else:
            break
    # right
    for j in range(s_col + 1, m):
        if grid[s_row][j] == ".":
            grid[s_row][j] = char
        else:
            break
    # left
    for j in range(s_col - 1, -1, -1):
        if grid[s_row][j] == ".":
            grid[s_row][j] = char
        else:
            break


n, m = map(int, input().split())
grid = [list(input()) for _ in range(n)]

h_row, h_col = None, None
r_row, r_col = None, None

for i in range(n):
    for j in range(m):
        if grid[i][j] == "S":
            h_row, h_col = i, j
        elif grid[i][j] == "T":
            r_row, r_col = i, j

        if h_row is not None and r_col is not None:
            break


paint_cross(h_row, h_col, "S", grid, n)
paint_cross(r_row, r_col, "T", grid, n)

# try to find S+dots+T or T+dots+S row-wise
for i in range(n):
    last = "*"
    for j in range(m):
        if (grid[i][j], last) == ("T", "S") or (grid[i][j], last) == ("S", "T"):
            print("YES")
            exit()

        if grid[i][j] != ".":
            last = grid[i][j]

# try to find S+dots+T or T+dots+S column-wise
for j in range(m):
    last = "*"
    for i in range(n):
        if (grid[i][j], last) == ("T", "S") or (grid[i][j], last) == ("S", "T"):
            print("YES")
            exit()

        if grid[i][j] != ".":
            last = grid[i][j]

print("NO")

As the problem states in order not to be noticed by the guard we should not execeed h. We can simply track the width(a variable w) of the road by tracking the number of people that exceeds the h and that don't and incrementing 2 and 1 to w(width of a road) respectively.

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

n, h = map(int, input().split())
heights = list(map(int, input().split()))
total = n

for height in heights:
    total += height > h    
 
print(total)

Let's iterate through the given array from the left to the right and store in the variable cur the length of the current increasing subarray. If the current element is more than the previous we need to increase cur on one. In the other case we need to update the answer with the value of cur and put in cur 0, because new increasing subarray began.

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

n = int(input())
a = list(map(int, input().split()))
 
ans = 1
cur = 1
 
for i in range(1, n):
    if a[i] <= a[i-1]:
        ans = max(ans, cur)
        cur = 0
    cur += 1
 
print(max(cur, ans))

The statement we should focus on is the one that says and I quote, "the box covers stairs with numbers 1, 2, ..., wi." on line 4 of the question. Let us take some examples and explain it a bit more. If there was a box with width 4, then this would cover the first 4 stairs. And box with width 6 would cover the first 6 stairs. What the aforementioned question statement implies is that if another box with width 2 — meaning it will cover the first 2 staircases — was thrown, the only option it has is to sit on top of the 6 width box that was thrown before it. Because the first 4 width box covered the first 4 stairs and then the 6 width box covered the first 6 stairs. And since we are told that the staircases are increasing, it means the more stairs covered means the more higher the box will be at. So, we could just keep track of the maximum height we reached so far, compare that with the height we got for the current box (which we can find by accessing the element on the list of stair height on the index width of the box minus one), we take the higher one and update the maximum height.

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

n = int(input())
 
hieght_of_strairs = list(map(int, input().split(" ")))
 
m = int(input())
best_attainable_height = -1
 
for i in range(m):
    bw, bh = list(map(int, input().split(" ")))
    curr_h = hieght_of_strairs[bw-1]
    best_attainable_height = max(best_attainable_height, curr_h)
    print(best_attainable_height)
    best_attainable_height += bh

What the question basically asks us is to find the lexicographically smallest permutation of [2...n] that is possible to get by moving only from some already visited city to another unvisited city and we are initially located at city 1.

Key Observations: -> We don't care about the length of the path we take, we only care about its lexicographical order. i.e We can go back and forth without being affected. -> We always choose the smallest reachable city, greedily, as our next destination. -> The number of possible candidates for next move is dynamic as our list can grow and shrink when we visit an new city. -> Heap is ideal for dynamic sized sorted arrays.

First, we build the graph so that we can access neighbors of a city efficiently later. Next, We create a heap(min-heap for our purpose) with 1 inside it. Note that at any point in time all the elements in the heap are possible candidates for our immediate next move. So we pop the smallest city from the heap, add it to the end of our path, mark it as visited and insert all the neighbors of this city to our heap (if a neighbor is already visited we ignore it to avoid cycle). Keep doing this until the heap becomes empty.

Q: What if the currently added neighbors are larger than a city we have left unvisited since we had a better choice back then? A: As I mentioned above, we will go back and visit that city before visiting the new cities. The questions doesn't explicity limit the the number of steps we can take to visit all the cities.

• Time: $$$O(m * log(n))$$$
• Space: $$$O(m)$$$

NB: $$$m >= n$$$ (since the graph is connected), so $$$(m + n <= 2m)$$$

from collections import defaultdict
from heapq import *

n, m = map(int, input().split())
graph = defaultdict(list)

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

heap, path, visited = [1], [], {1}

while heap:
    current = heappop(heap)
    path.append(current)

    for neighbor in graph[current]:
        if neighbor not in visited:
            heappush(heap, neighbor)
            visited.add(neighbor)

print(*path)

Our goal is to detect if the situation is dangerous or not. The condition we need to check is 7 players of the same team standing one after the other. so what we can do is count contiguous players of the same team. Iterate through the given string and compare each value at current index with the value of the previous index, if equal increment our count else assign count equal to 1. If count reaches 7 it means the situations is dangerous then print "YES".

s = input()
curr = 1

for i in range(1,len(s)):
    if s[i-1] != s[i]:
        curr = 0
    curr += 1
    if curr >= 7:
        print('YES')
        break
else:
    print('NO')

• Time complexity — $$$O(n)$$$
• Space complexity — $$$O(1)$$$

Lets make some observations, if there were no constraints we could make a total of (a+b)//4 teams. the number of teams we can make is limited by min(a, b) because the smaller number(say mathematicians) will be the limiting factor and some of the larger number(say programmers) will be left without a team. So we can deduce that the possible amount of teams is min((a+b)/4, a, b) for example say a = 10 and b = 2 we can see that its not possible to create more than two teams due to the given constraint so min((2+10)/4, min(2,10)) == 2 lets say a=3 and b=2 here it might look like b=2 is the limiting factor and the answer, but notice that its not logically possible to make 2 teams of 4 from 5 individuals so this time what limits us is actually (a+b)//4. min((2+3)//4, 2, 3) == 1.

for _ in range(int(input())):
    a, b = map(int, input().split())
    print(min((a+b)//4, a, b))

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

Binary search on Answer.

def is_valid(a, b, teams):
    return min(a, b) >= teams and a + b >= 4 * teams
 
def solve(a, b):
    lo, hi = 0, min(a,b)
    best = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if is_valid(a, b, mid):
            best = mid
            lo = mid + 1
        else:
            hi = mid - 1   
    return best           
 
t = int(input())
 
res = []
for _ in range(t):
    a, b = map(int, input().split())
    res.append(solve(a,b))
 
print(*res, sep="\n")

• Time complexity — $$$O(logn)$$$
• Space complexity — $$$O(1)$$$

For better illustration of the problem analysis let's go through this train of thought, first considering the string "usknnruu": We would start from the first left side of the string and write how many versions we would build up from the letters: u — 1 us — 1 usk — 1 uskn — 1 usknn — 2 : NOW we spot two consecutive n's which could have been interpreted by the machine as really "nn" or "m" thus leaving us with two cases (one case is we added to the previous string "uskn" + the other case is we added m to the previous previous string "usk"): LEADING TO VERSIONS "usknn, uskm" usknnr — 2: LEADING TO VERSIONS "usknnr", "uskmr" usknnru — 2: LEADING TO VERSIONS "usknnru", "uskmru" usknnruu — 4 (since we add u to the previous two strings: LEADING TO VERSIONS "usknnruu, uskmru" + we add w to the previous previous strings: LEADING TO VERSIONS "usknnrw", "uskmrw")

so at last we return 4 but the problem with this is we didn't consider the case "uu". If we had done it like earlier: u — 1 uu — 1 (it should have been 2 since we have two cases "uu" and "w" but we don't know how to construct "w")

So, we need to consider an empty string "" — 1 (in-case we have consecutive u's or n's at first it'll hold the w or m) u — 1 uu — 2 (cause we add u to the previous string: LEADING TO VERSION "uu" and we add w to the previous previous string: LEADING TO VERSION "w")

So overall, this is what we were doing: - Maintaining (keeping) the same version number as we added distinct letters - When we got consecutive u's or n's (like when we had processed the letter u previously and the coming letter is again u), we add the version of the previous string + the version of the previous previous string

Look closely, looks like we're building it up (constructing using DP-bottom up approach :D) Implementation detail hint: Use an array sized [0-n+1] and make sure the 0th and 1st index of the array is set to 1 (we saw the empty string proof earlier and a string with size 1 has only a version of 1)

And one last note: if the string includes "m" or "w", we should return 0 at once. Since the machine didn't mess with it if it included m or w in the first place.

def solve(s,m):
    n = len(s)
    for val in s:
        if val == "m" or val == "w":
                return 0                      
    
    array = [1] * (n+1)
    for i in range(2, n+1):
        if s[i-2:i] == "nn" or s[i-2:i] == "uu":
            array[i] = (array[i-1] + array[i-2] ) % m
        else:
            array[i] = array[i-1]
    
    return array[n]
     
s = int(input())
MOD = 10**9 + 7
print(solve(s, MOD))

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

The first thing to notice is that it's always optimal to perform the operation on the character that appears first on the string. Let's say the first character that appears first is E, then the we should repeatedly apply the operation on letter on that position (i.e. E->D->C->B->A). After performing these operations, there's nothing you can do for the first character so you can move to the next character on the string. At this point, if the character you encounter is lexicographically lower than the highest character you have seen so far (in this case E), you can just convert it to A without any cost (because it would have changed to A while you were applying the operations in the past). Furthermore, if you find a letter that's higher, say F, it would cost you 1 operation to get it down to A (Think if you rearranged the operations so that you did F->E before you did the other operations).

One additional point, is that if you don't have enough points to get a character (say Q) all the way to A. In this case, you use all the operations to get it as low as possible (Say G) and then continue to the other characters and if they are below or equal to Q but above G then you can convert it to G, but otherwise continue till the end.

t = int(input())
 
for _ in range(t):
    _, m = list(map(int, input().split()))
    s = input()
    max_changed = 'a'
    top_level = 'a'
    ceil_change = 'a'
    answer = []
    for c in s:
        if c <= max_changed:
            answer.append('a')
            continue
        if ord(c) - ord(max_changed) > m:
            if m > 0:
                ceil_change = chr(ord(c) - m)
                top_level = c
                m = 0
            if c <= top_level:
                answer.append(min(c, ceil_change))
            else:
                answer.append(c)
        else:
            m -= ord(c) - ord(max_changed)
            max_changed = c
            answer.append('a')
        
    print("".join(answer))

• Time complexity: $$$O(n)$$$
• Space complexity: $$$O(1)$$$ additional pace complexity

After having the input as a string we can count the number of the character "1" ether by looping or if you are in python by using list(string).count("1"). Then finally print "yes" if the count is more than 2.

n = int(input())
count = 0
for _ in range(n):
    s = input()
    count += s.count("1") >= 2
print(count)

Time and space Complexity $$$O(n)$$$

from collections import defaultdict
import sys
sys.setrecursionlimit(8000)
 
count = 0
 
def dfs(i, s):
    global count

    res = 1 if s[i - 1] == 'W' else -1 
    for neighbor in graph[i]:
        res += dfs(neighbor, s)
 
    if res == 0:
        count += 1 
    return res 
 
for _ in range(int(input())): 
    count = 0 
    n = int(input())
 
    a = [int(x) for x in input().split()]
    s = input()
 
    graph = defaultdict(list)
 
    for i in range(n-1):
        graph[a[i]].append(i + 2)
 
    dfs(1, s)
    print(count)

First we save original indices of the numbers. Then we sort them. After that we compare old and new indices. In order this question to be true, there must be either not difference between all old and new indices or there must be only one sub array in the new indices and the summation between all the indices in that sub array should be equal.

import java.util.*;

public class Solution{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.nextLine());
        String[] line = sc.nextLine().split(" ");
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < n; i++){
            map.put(Integer.parseInt(line[i]), i);    
        }
        
        Arrays.sort(line, (a, b) -> Integer.parseInt(a) - Integer.parseInt(b));
        
        boolean found = false, continued = false;
        int sum = 0, start = 1, end = 1;
        
        for(int i = 0; i < n; i++){
            int prevIdx = map.get(Integer.parseInt(line[i]));
            if(prevIdx != i){
                if(!found){
                    found = true;
                    continued = true;
                    sum = prevIdx + i;
                    end = prevIdx + 1;
                }else if(continued && prevIdx + i == sum){
                    start = prevIdx + 1;
                }else{
                    System.out.println("no");
                    return;
                }
            }
            
            if(prevIdx + i != sum){
                continued = false;
            }
        }
        System.out.println("yes");
        System.out.println(start + " " + end);
    }
}

Time complexity — $$$O(nlogn)$$$ Space complexity — $$$O(n)$$$

First we need a frequency list for each value. Then in order to delete few elements we need to keep as many as possible. and each kept value need to have the same frequency. Thinking the frequency as a height then we are looking for the largest rectangle.

How about the largest frequency combined with the second largest frequency and so on? Great lets give it a try.

let [3,8,7,5] was our frequency list first the largest frequency. 8 ==> area will 8*1 largest with second largest. 8, 7 ==> area will 7*2(14) and so on 8, 7, 5 ==> 5*3(15) 8, 7, 4, 3 ==> 3*4(12)

here we can see 15 is the largest rectangle possible. lets sort freq_list in reversed way. Then each value will be making possibly the largest rectangle with width as its index +1 and height the value.

// max([val*(i+1) for val in enumerate(sorted(freq_list))]) will give us the largest rectangle possible. This is it. except for returning the appropirate value which is length of the given array minus the largest rectangle possible.

from collections import Counter
from collections import defaultdict
t = int(input())
for _ in range(t):
    n = input()
    arr = list(map(int, input().split()))
    freq = sorted(Counter(arr).values(), reversed=True)
    remaining = max([val*i for i, val in enumerate(freq, 1)])
    print(n - remaining)

Time and Space Complexity — $$$O(N)$$$

Xenia wants to compute the total of integer summands, but she can only do it if the summands are sorted in a non-decreasing manner, therefore we may assist her as follows:

• step 1: remove the “+” character from the given string.
• Step 2: sort the summands in an increasing order.
• Step 3: replace the “+” character between the summands.

input = input().split("+")
input.sort()
li = []
for i in range(len(input)):
   li.append(input[i])
   if i < len(input) - 1:
       li.append("+")
 
string = "".join(li)
print(string)

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

The straight forward solution to this problem is simulating the process. This can be achieved by pooping the elements from the two ends of using Two pointers. And counting the score point gained by the two players.

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

l,r = 0,len(nums)-1
i = 0
sereja = dima = 0
while l<=r:
    if i % 2 == 0:
        if nums[l] > nums[r]:
            sereja += nums[l]
            l += 1
        else:
            sereja += nums[r]
            r -= 1
    else:
        if nums[l] > nums[r]:
            dima += nums[l]
            l += 1
        else:
            dima += nums[r]
            r -= 1
    i += 1
    
print(sereja,dima)

Time Complexity: $$$O(n)$$$ Space Complexity: $$$O(1)$$$ where $$$n$$$ is number of cards

Understanding the problem:

1. There is a frog and it can jump in both directions(left or right) from some index.
2. The frog can jump to Left direction if s[i] = 'L' and it can jump to Right direction if s[i] = 'R', for i [0, n-1] where n is the length of the string.
3. It can only jump upto the boundary of the array. It cannot go past 0 index in the left direction and it cannot go past n-1(where n is length of string). let, d be the distance you decided to use to jump.
4. From the first index (0), you can only go to right, 'R'
5. What is the minimum d you have to use to get from 0 to n-1? d is the maximum jump you have done anywhere in the string. And, you want to minimize d.

Insight:

1. we should ignore 'L' because it will just take us backward.
2. we should only keep track of the maximum distance between two 'R'
3. for example, RLLLRLR, it takes 4 distances to jump from 0 to 4 index. and it takes 2 distances to jump from 4 to 6. And, the maximum distance we have used so far is 4. So, the answer will be 4.

Psuedo code:

set starting index to -1
set max_distance to 0
append 'R' at the end of the string
iterate through the string from i = 0..n
    if string[i] == "R":
       update max distance with max(max_distance, i - starting_index)
       set starting index to i
return max_distance

n = int(input())

while n>0:
    li = list(input())
    li.append("R")
    max_distance = 0
    s = -1
    for i in range(len(li)):
        if li[i] == "R":
            max_distance = max(max_distance, i-s)
            s = i
    n-=1
    print(max_distance)

Complexity analysis

Time complexity is $$$O(n)$$$ because we are iterating over the string once Space complexity is $$$O(1)$$$ because we are not using any auxiliary data structure

The solution is trivial for a single player having maximum score. But it needs more work if we have two or more players with a maximum score. The rule says If two or more players have a maximum score, m at the end of the game we have to look for a player that scored at least m points first in some round, and that player becomes the winner of the game.

let’s say the players are Mike and John, their score in each round is given in the following manner:

Mike 20 John 10 Mike -10

at the end of the game both of the players will have a maximum score, m=10. In order to find the winner we have to look for the player who scored at least m points first. We can see that Mike scored 20 before John scored 10, thus making Mike the winner of the game.

Algorithm

Data Structure we will use:

A dictionary called score to keep track of the scores each player have.

A set called winners to store the candidate winners

A list called history to store the inputs we are given in each round. This comes in handy when we have more than one candidate winners, then we have to play the game again (traversing the history array) to find the player in the winners set who scored at least m points first, m being the maximum score at the end of the game.

The steps are as follows:

1. we update the score of player’s in each round
2. we traverse through the scores of the players to find the maximum score, m.
3. we separate players with score m into winners set
4. we traverse through the history array to find the first person to score at least m points first.
5. Check if the first person to score m point first is in the winners set since players that are not winner candidate may score m points first

score = {}
history = []
winners = set()
 
n = int(input())
 
for i in range(n):
    s = input()
    history.append(s)
    name,val = s.split()
    val = int(val)
    score[name] = score.get(name,0) + val
    
maxScore = max(val for name,val in score.items())
 
for name,val in score.items():
    if val == maxScore:
        winners.add(name)
 
roundScore = {}
for i in range(len(history)):
    name,score = history[i].split()
    score = int(score)
    roundScore[name] = roundScore.get(name,0) + score
    
    if roundScore[name]>=maxScore and name in winners:
        print(name)
        break

Time complexity: $$$O(n)$$$, $$$n$$$ is number of rounds Space Complexity: $$$O(n)$$$, the history array is a size of $$$n$$$

Given the username our task is to identify the gender of the user. if the number of distinct characters in one's user name is odd, then he is a male, otherwise she is a female. To solve this problem we only need to know the number of distinct characters in the username. Then determine whether it is odd or even.

1. To solve this problem without the help of any data structure is by counting number of duplicated characters within the whole string and then take the difference between the length of the whole user name and the number of duplicated characters. Their difference will give us the number of distinct characters.
2. What is the popular data Structure we use to remove duplicates? As you guessed $SET$S.

user_name = input()
n = len(user_name)
count = 0
for i in range(n):
 for j in range(i+1, n):
 if user_name[i] == user_name[j]:
 count += 1
 break
res = n - count
if res % 2 == 0:
 print("CHAT WITH HER!")
else:
 print("IGNORE HIM!")

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

User_name = set(input())
if len(User_name) % 2 == 0:
 print("CHAT WITH HER!")
else:
 print("IGNORE HIM!")

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

For this problem, we can rephrase the question as, for given number of swaps swap any adjacent ("B" then "G")'s to ("G" then "B").

intuition : iterate through the entire array and swap the Boys and Girls that are next to each other. One edge case to consider is to pass the $$$i+1$$$ iteration if $$$i$$$ matches the given pattern because it's already processed because of the swap.

import sys
input = sys.stdin.readline

def invr():
    return(map(int,input().split()))
length, swaps = invr()
string = input()
# prepare character array
char = [ch for ch in string]
 
for _ in range(swaps):
    i = 0
    while i < length-1:
       # check adjacent boys and girls and swap them
        if char[i] == 'B' and char[i+1] =='G':
            char[i], char[i+1] = char[i+1], char[i]
            # pass the next i since its already swapped
            i += 1
        i += 1
        
print(''.join(char))

Time complexity : O(n*m) where n is string length and m is number of swaps Space complexity : O(n) we are using external character array

To solve this question we are going to use the hashmap data structure. We store the name of client as a key and the number of registration for the same name as a value.

If the input name's value in the hashmap equals one the registration went successfully, if greater than one it registers the name + value of that name.

public class RegistrationSystem {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
        // solution starts................................................................
        Map<String, Integer> map = new HashMap<>();
        int n =  Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++){
            String data = br.readLine();
            int freq = map.getOrDefault(data, 0) +1;
            map.put(data, freq);
            if(map.get(data) == 1){
              System.out.println("OK");
            }else{
                System.out.println(data  + (map.get(data) - 1));
            }
        }
       // solution ends....................................................................
       output.flush();
    }
}

Let $$$A$$$ be a list of the interestingness of the topic of length $$$n$$$, where $$$ai$$$ is the interestingness of the $$$i-th$$$ topic for the teacher. Let $$$B$$$ be a list of the interestingness of the topic of length $$$n$$$, where $$$bi$$$ is the interestingness of the $$$i-th$$$ topic for the student.

Good pair of topics = pair($$$i, j$$$), where $$$i < j$$$ and $$$ai + aj > bi + bj$$$

$$$Approach 1$$$: Bruteforce (Time Limit Exceeded)

The brute force solution would be iterating over an array A and finding topic $$$bj$$$, where $$$j < i$$$ and $$$ai - bi > bj - aj$$$ for each $$$ai$$$. This requires two-layer looping and time complexity is $$$O(n^2)$$$, which is unacceptable for this problem.

$$$Approach 2$$$: Binary Search

Let’s rewrite the equation:

$$$ai - bi > bj - aj$$$ ==> $$$ai - bi > - (aj - bj)$$$ ==> $$$(ai-bi) + (aj - bj) > 0$$$

$$$ai - bi$$$ is the difference between the interestingness of the $$$i-th$$$ topic for the teacher and the student. We can now build an array $$$c$$$, where $$$ci = ai - bi$$$ The problem is now simplified to finding pairs of indices $$$i$$$ and $$$j$$$, where $$$ci + cj > 0$$$ Now, the solution would be, to sort the array $$$c$$$ and find the leftmost index $$$j$$$ at which $$$ci + cj > 0$$$ for each $$$ci$$$, where $$$ci <= 0$$$. Leftmost index $$$j$$$, can be found with binary search. Add $$$n - j$$$ to the answer, because topics after indices $$$j$$$ including $$$j$$$ are all good pairs, with topic $$$ci$$$. For $$$ci$$$, where $$$ci > 0$$$, add $$$(n - i + 1)$$$ to the answer, this makes sure the same pairs of topics won’t be added to the answer multiple times.

def binary_search(diff, low, high):
 
    i = low - 1
    best = False
 
    while low <= high:
        mid = low + (high - low)//2
 
        if diff[mid] + diff[i] > 0:
            best = mid
            high = mid-1
        else:
            low = mid + 1
    
    return best
    
def solve(a, b):
    count = 0
    diff  = []
 
    for i in range(t):
        diff.append(a[i] - b[i])
    
    diff.sort()
    n = len(diff)
 
    for i in range(n):
        if diff[i] > 0: count += (n - (i + 1))
        else:
            idx = binary_search(diff, i + 1, n -1)
            if idx:
                count += (n - idx)
 
    return count
 
if __name__ == '__main__':
 
    t = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
 
    print(solve(a, b))

Time Complexity: $$$O(nlogn)$$$, $$$n$$$ for iterating through the array and $$$logn$$$ for finding the leftmost index $$$j$$$ where $$$ci + cj > 0$$$ \n Space Complexity: $$$O(1)$$$, if one of the two arrays is reused to build an array $$$c$$$

Lexicographically compare two given strings and print '-1' if if the first string is less than the second one, print 1 if the second string is less than the first one or print 0 if they are equal. (The letters' case doesn't matter)

first = input().lower()
second = input().lower()
 
if first < second:
    print(-1)
elif second < first:
    print(1)
else:
    print(0)

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

From observing the condition that is given:

n & (n - 1) & (n - 2) & (n - 3) & …. (k) = 0

We can see that we are subtracting one from n every time we use the logical AND between pairs.

Say if n = 5, => n & (n & n — 1) => 5 & (5 & 5 — 1) => 5 & (4) = 4

This can go on until the number becomes zero. If we take a look under the hood and see how the number’s binary representation behaves, we can see that this process is just flipping ones to zero from right to left until the left most bit ,also know as the Most Significant Bit (MSB), is flipped to a zero.

For n = 5

From the above demonstration we can see that the number we have to AND with to flip the MSB is 3 which is conveniently a number we would gate subtracting one from the representation of the MSB. And this representation is just the biggest power of two less that or equal to n. This is also the same with 2 ^ bit_count, where bit count represents the number of bits till upto the MSB (ignoring all leading zeros).

We can achieve this with wide variety of ways. Here are some approaches that you may use, though there might be more ways of doing it.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t, num;
    cin >> t;
    while (t--) {
        cin >> num;
        int nextPowerOfTwo = 1;

        while (nextPowerOfTwo * 2 <= num) {
            nextPowerOfTwo *= 2;
        }

        cout << nextPowerOfTwo - 1 << endl;
    }
}

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

t = int(input())

for i in range(t):
    num = int(input())
    while num & (num - 1) :
        num &= num - 1
    print(num - 1)

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

We have people named 1,2,3 .... n. We do also have groups or unions formed based on pairs of nodes given in the input.

So simply the problem is picking one person from each group. Which person in a group? The guy with smallest gold demand.

How do we form the groups from the input? We can use union find algorithm can't we? Or DFS or BFS. I'm going with union-find for no special reason. Well if you have affiliation with BFS or DFS then that also possible.

So after implementing the find(..) and union(..) functions and grouping every node pairs in the input. All we have to do is then picking a person from each group.

If you don't have idea of how to pick, here is how. After unionising the nodes we will know for every node to which group they belong. Usually by the #find(node) function. Then by iterating for each node. We can register the smallest gold for each group. Then print the sum of them

def find(node, parents):
    if parents[node] == node:
        return node
    parents[node] = find(parents[node], parents)
    return parents[node]
 
def union(a, b, parents, rank):
    root_a = find(a, parents)
    root_b = find(b, parents)
 
    if rank[root_a] < rank[root_b]:
        root_a, root_b = root_b, root_a
 
    parents[root_b] = root_a
    rank[root_a] += rank[root_b]
 
 
 
n, m = map(int, input().split())
gold = map(int, input().split())
 
parents = {i:i for i in range(1,n+1)}
rank = {i:1 for i in range(1,n+1)}
 
for _ in range(m):
    a, b = map(int, input().split())
    union(a, b, parents,rank)
 
costs = {} 
for node, cost in enumerate(gold, 1):
    root = find(node, parents)
 
    if root in costs:
        costs[root] = min(costs[root], cost)
    else:
        costs[root] = cost
 
print(sum(costs.values()))

let N : (number of nodes), M : (number of node pairs) Time Complexity: $$$O(M*log(N) + N)$$$, Space Complexity: $$$O(N)$$$

import collections

n, m = map(int, input().split())
visited = set()
golds = list(map(int, input().split()))
graph = [[] for _ in range(n)]
 
for _ in range(m):
  x,y = map(int, input().split())
  graph[x-1].append(y-1)
  graph[y-1].append(x-1)
 
def bfs(x):
  _min = float('inf')
  while queue:
    node = queue.popleft()
    _min = min(_min, golds[node])
 
    for v in graph[node]:
      if v not in visited:
        visited.add(v)
        queue.append(v)
  return _min
 
queue = collections.deque()
 
total = 0
for i in range(n):
  if i not in visited:
    queue.append(i)
    visited.add(i)
    total += bfs(i)
 
print(total)

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

In this problem we are asked to find the longest three equal substrings called prefix, suffix and obelisk (neither prefix nor suffix). To find the prefix and suffix, let $$$i$$$ (initially $$$i=0$$$) point to the end of the prefix (prefix becomes $$$s[:i+1]$$$) and let $$$j$$$ (initially $$$j=n-1$$$) point to the start of the suffix (suffix becomes $$$s[j:]$$$). But what about obelisk? the time complexity would be too slow if we were to find obelisk after finding prefix and suffix. We can use another pointer $$$k$$$ (initially $$$k=n-2$$$) that points to the start of the obelisk (obelisk becomes $$$s[k:k+i+1]$$$, $$$i+1$$$ is our current string size). The suffix and obelisk's strings should be equal. We can't guarantee that prefix is the same as suffix on every iterations, but obelisk should always be the same as suffix. To solve this problem a sliding window technique can be applied and whenever obelisk is different from suffix slide the window which is $$$(k:k+i+1)$$$ by $$$1$$$ to the left. We do this for every i in 0...n-2 while k > 0. Finally, from all acceptable password variants we choose the longest one.

The above algorithm runs in o(n^2) time complexity. And the expensive operation was checking if two string are equal. There are two string matching algorithms (Robin Karp and KMP algorithms). In solution 1 rolling hash (Robin Karp algorithm) is used to reduce the time complexity to a linear runtime. In solution 2 kmp (Knuth–Morris–Pratt) is used.

Resources to learn about rolling hash Youtube and blog. KMP Youtube and blog

Use three different hash values for suffix, prefix and obelisk. Try to maintain an equal hash value for obelisk and suffix. If the three values are equal, one acceptable password variant is found.

def get_hash(c):
    return 1+ord(c)-ord("a")

def solve(s):
    n = len(s)
    a, curr_a = 31, 1
    mod = 10**9 + 7
    password_idx = -1
    p_hash = s_hash = o_hash = 0 # prefix, suffix and obelisk hash values respectively
    k = n-2 # pointer for obelisk
    for i in range(n-1): # i is pointer for prefix
        j = -i-1 # pointer for suffix
        p_hash = (p_hash + get_hash(s[i])*curr_a) % mod
        s_hash *= a
        s_hash = (s_hash + get_hash(s[j])) % mod
        o_hash *= a
        o_hash = (o_hash + get_hash(s[k])) % mod
        while s_hash != o_hash and k > 0:
            o_hash -= get_hash(s[k+i])*curr_a
            k -= 1
            o_hash *= a
            o_hash = (o_hash + get_hash(s[k])) % mod
        if k == 0: break # since obelisk can't be a prefix
        if p_hash == s_hash:
            password_idx = i
        k -= 1
        curr_a *= a
        curr_a %= mod

    if password_idx != -1:
        return s[:password_idx+1]
    return "Just a legend"

if __name__ == '__main__':
    s = input()
    print(solve(s))

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

Author: nCydready

# This is a kmp solution and a tutorial will be added later
s = input()
 
pattern = [0] * (len(s) + 1)
left, right = 0, 1
 
while right < len(s): # longest proper prefix that also a suffix
    if s[left] == s[right]:
        left += 1
        right += 1
        pattern[right] = left
    elif left > 0:
    	left = pattern[left] 
    else: 
    	right += 1
 
n = pattern.pop()
if n > 0 and n in pattern:
    print(s[:n])
elif pattern[n] > 0:
    print(s[:pattern[n]])
else:
    print('Just a legend')

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