How many vowels are there?

odd*odd+even*odd=?

odd*odd+even*even=?

If n>5, we don't have enough vowels to give one to each row. Hence answer would be "NO"

If k is odd, odd number of rows each have an odd number of characters in them. Remaining rows have even number of characters. So, total number of distinct characters should be odd for the answer to be "YES". but we know that 26 is not odd. Hence, answer will be "NO"

If both the conditions "n>5" and "k is odd" are False, then it is guaranteed that n<=5 and k is even

We can first give one vowel to each of the row (remaining 26-n alphabets left)

Then, we can add one more character to n-k rows (remaining 26-n-(n-k)=26-2n+k alphabets left)

Now, we have n-k rows with 2 characters each and k rows with 1 character each. All of them have atleast one vowel in them. 26-2n+k is an even number. So, we can just add the remaining 26-2n+k characters to one of the rows and it's parity would remain the same

Finally, we are left with exactly n-k rows with even number of characters in them and exactly k rows with odd number of characters in them.

hence, if n<=5 and k is even, the answer is "YES"

for _ in range(int(input())):
    n,k=map(int,input().split())
    if n>5 or k%2==1:print("NO")
    else:print("YES")

The problem name is "Earth's Inhalation Exhalation principle"

Does it sound familiar?

Use inclusion exclusion principle

Include all multiples of 4 from x to y (inclusive of x and y)

Exclude all multiples of 100 from x to y (inclusive of x and y)

Include all multiples of 400 from x to y (inclusive of x and y)

def count(start,stop,n):
    start+=(-start)%n
    stop-=stop%n
    return (stop-start)//n +1
x,y=map(int,input().split())
print(
    count(x,y,4)
    -count(x,y,100)
    +count(x,y,400)
)

consider n's binary representation and check for k=0,1,2,...

for _ in range(int(input())):
    n,k=map(int,input().split())
    if k>=2:
        print(0)
        continue
    if k==1:
        while n&1:n>>=1
        print(n)
        continue
    print(n)

Greedy

sort Alice's ranks at each timestamp and greedily make his fan observe him for as much as required from top ranks to bottom ranks

for each bob, sort his ranks at each timestamp and greedily make his fan observe him for as much as required from bottom ranks to top ranks

Record how much each fan's happiness reduces. If reduction in Alice's fan's happiness is strictly lower than each Bob's fan's reduction in happiness, then the answer will be "YES". If not, then the answer will be "NO"

n=int(input())
q=int(input())
t=[int(x) for x in input().split()]+[float('inf')]
 
 
mat=[[int(x) for x in input().split()] for _ in range(q)]
mat=[*zip(*mat)]
 
 
mat2=[]
for r in (mat):
   r2=[]
   for i,x in enumerate(r):
       r2.append((x,t[i+1]-t[i]))
   r2.sort()
   mat2.append(r2)
 
 
L=[int(x) for x in input().split()]
 
 
a_neg=0
a_obv=L[0]
for r,dt in mat2[0]:
   tr=min(a_obv,dt)
   a_obv-=tr
   a_neg+=tr*(r-1)
 
 
for i,bob in enumerate(mat2[1:]):
   b_neg=0
   b_obv=L[i+1]
   for r,dt in reversed(bob):
       tr=min(b_obv,dt)
       b_obv-=tr
       b_neg+=tr*(r-1)
   if b_neg<=a_neg:
       print("NO")
       break
else:print("YES")

$$$(()())()$$$

number of distinct happy paths = $$$T - L - U$$$

where,

T = total number of ways

L = total number of ways in which only lower triangle of the matrix (including diagonal) is visited

U = total number of ways in which only upper triangle of the matrix (including diagonal) is visited

let m = n-1

T = $$${2*m}\choose {m}$$$

Symmetrically, L = U

The condition required for visiting only lower triangular matrix is row number >= column number (where rows are numbered 0 to n-1 from top to bottom; columns are numbered 0 to n-1 from left to right)

This is the same as counting number of possible bracket sequences. So, L = U = C(m) (where C(m) denotes the m — th catalan number)

Hence, the final answer will be $$$T-L-U={{2*m}\choose {m}}-2*C(m)$$$

p=10**9+7
fact=[1]
for i in range(1,2001):
    fact.append((fact[-1]*i)%p)
finv=[1]
for i in range(1,2001):
    finv.append((finv[-1]*pow(i,-1,p))%p)
def C(n):
    ans= pow(n+1,-1,p)* fact[2*n]*finv[n]**2
    return ans%p
for _ in range(int(input())):
    n=int(input())-1
    ans=fact[2*n]*finv[n]**2-2*C(n)
    ans%=p
    print(ans)

First, we solve the problem "find the total number of ways to go from (0,0) to (n-1,n-1) where only right and down movements are permitted"

$$$dp[i][j]=dp[i+1][j]+dp[i][j+1]$$$

with the base cases

$$$dp[i][-1]=1$$$ ($$$0 \le i \le n-1$$$)

$$$dp[-1][j]=1$$$ ($$$0 \le j \le n-1$$$)

Now, let's assume the first step taken is down (i.e Bob's house). We have to make sure that there is no way of reaching (n-1,n-1) without going into Alice's house. We can do so by blocking the square (n-1,n-2)

To block (n-1,n-2), we'll fill up the last row with 0 and second last row with 1. Then, we can recalculate the dp for lower triangle (except last 2 rows)

Now, the square right below start has the answer for the problem, with an additional constraint that the first visited house should be Bob's house. Let's call this x. Symmetrically, the answer will be $$$2*x$$$

p=10**9+7
n=1000
dp=[[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dp[-1][i]=1
    dp[i][-1]=1
for i in reversed(range(n-1)):
    for j in reversed(range(n-1)):
        dp[i][j]=dp[i+1][j]+dp[i][j+1]
        dp[i][j]%=p
for i in range(n):
    dp[-2][i]=1
    dp[-1][i]=0
for i in reversed(range(n-2)):
    for j in reversed(range(n-1)):
        if i<j:continue
        dp[i][j]=dp[i+1][j]+dp[i][j+1]
        dp[i][j]%=p
for _ in range(int(input())):
    n=int(input())
    print((2*dp[-n+1][-n])%p)

How can you determine at which point they both will meet each other again for the first time

look at image in problem for reference

They can meet again in start point only if each of them traveled even distance (as circumference is 2KM)

They can meet again in opposite point only if each of them traveled odd distance (as circumference is 2KM)

The ratio of their distance traveled is equal to the ratio of their speeds. Since we want the first time they meet, we'll get the simplest form by dividing numerator and denominator by their gcd. Let this simplest form of fraction be $$$\frac{x}{y}$$$

If both x and y are odd, they'll meet at the opposite point. So, $$$s_a=x$$$ and $$$s_b=y$$$

If exactly one of them is even, $$$s_a=2*x$$$ and $$$s_b=2*y$$$ and they'll meet at start point

It is not possible for both of them to be even since they're already in their simplest form (i.e their gcd is guaranteed to be 1)

from math import gcd
for _ in range(int(input())):
    a,b=map(int,input().split())
    g=gcd(a,b)
    a//=g
    b//=g
    if a%2==0 or b%2==0:
        a*=2
        b*=2
    print(a,b)

$$$L_i$$$ has to be minimized. Since $$$L_i$$$ decreases when standing duration increases and vice versa, the i — th student will try to stand for as long as possible

So, $$$L_i=q-P_i+1$$$

but this could lead to $$$L_i$$$ becoming less than 0, which is not permitted (a student cannot solve negative number of questions)

So, $$$L_i=max(0,q-P_i+1)$$$

for _ in range(int(input())):
    n,q=map(int,input().split())
    P=[int(x) for x in input().split()]
    print(*[max(0,q-t+1) for t in P])

What if n = 2?

XOR is addition without carry

$$$L_1+L_2+...+L_n \ge L_1 \oplus L_2 \oplus ... \oplus L_n$$$

Write down all numbers in the array L in their binary representation

"$$$L_1+L_2+...+L_n \ne L_1 \oplus L_2 \oplus ... \oplus L_n$$$" iff "there exists a position where at least two numbers have their bit in that position set to 1"

The above stated is true because if less than two numbers have their bit in that position set to 1, XOR and addition both operations would behave the same and hence $$$L_1+L_2+...+L_n = L_1 \oplus L_2 \oplus ... \oplus L_n$$$

In order to make L satisfy this property, all operations shall be applied only to one index of the array (otherwise number of operations won't be minimised).

Given the constraints, doing the operation at an index at most 19 times should be sufficient (worst case input is $$$L=[1,2^{19}]$$$

We can solve this in O(n) by computing sum of L and XOR of L in advance and when iterating over L, we can get sum of remaining elements and XOR of remaining elements in O(1)

for _ in range(int(input())):
    n=int(input())
    L=[int(x) for x in input().split()]
    S=sum(L)
    X=0
    for x in L:X^=x
    req=10**9
    for x in L:
        rs=S-x
        rx=X^x
        for i in range(20):
            if rs+(x<<i)!=rx^(x<<i):
                req=min(req,i)
    print(req)

Manually calculate for smaller values of n

Read solution of H before this

If an element occurs more than once in the array, then it occurs at least twice in the array. Let's call these $$$L_j$$$ and $$$L_k$$$. $$$j \ne k$$$; $$$L_j=L_k$$$

$$$L_j \oplus L_k = 0$$$ but $$$L_j + L_k \gt 0$$$. The remaining elements XOR is less than or equal to the remaining elements sum

Hence, if a number occurs more than once in L, the minimum operations required would be 0. We now need to find n! * (minimum operations required for L=[1,2,...,n])

If $$$n \ge 3$$$,

$$$1 \oplus 2 \oplus ... \oplus n \le n+1$$$

$$$n + 1 \lt n(n+1)/2$$$

From the above 2 statements, $$$1 \oplus 2 \oplus ... \oplus n \lt 1 + 2 +... + n$$$

Hence for $$$n \ge 3$$$, minimum operations required for the array L=[1,2,...,n] will be 0

The only edge case will be n=2, where we can manually figure out the answer to be 2

for _ in range(int(input())):
    n=int(input())
    print(2 if n==2 else 0)

"lesser the age gap between two people, higher the interaction between them" so we need to find the first neighbour pair with the lowest age gap

n=int(input())
A=[int(x) for x in input().split()]
 
from itertools import pairwise
req=min(abs(x-y) for x,y in pairwise(A))
 
for i in range(n-1):
    if abs(A[i]-A[i+1])==req:
        print(i+1)
        break

he gets the verdict "Wrong answer on test k"

So, he knows the correct answer for the first k-1 test cases and also he knows the wrong answer for the test case k. The opposite of his current answer for test case k will be the correct answer. Hence, he now knows the correct answer for the first k test cases

There are m-k test cases remaining. In the worst case scenario, all of his initial guesses would be incorrect. Hence he will get m-k more WAs

He initially got a WA. So, in total he got m-k+1 WA

m,k=map(int,input().split())
print(m-k+1)

TLDR: the edge case is 2028

• If x%4=1, that year's batch will be assigned hostel A

• If x%4=2, that year's batch will be assigned hostel B

• If x%4=3, that year's batch will be assigned hostel C

• If x%4=0, that year's batch will be assigned hostel D

Since there are 50 students per floor,

• In 2025 ground floor and 1st floor occupied (2 floors in total)

• In 2026 ground floor to 2nd floor occupied (3 floors in total)

• In 2027 ground floor to 3rd floor occupied (4 floors in total)

• In year x, ground floor to (x-2024)th floor occupied (x-2023 floors in total)

If x%4=1, first floor is guaranteed to be occupied. So answer will be 1/(x-2023)

If x%4=2, ground floor is guaranteed to be occupied. So answer will be 1/(x-2023)

If x%4=3, ground and first floor are both guaranteed to be occupied. So answer will be 2/(x-2023)

If x%4=0 and x>2028, first, third and fifth floors are guaranteed to be occupied. So answer will be 3/(x-2023)

If x%4=0 and x=2028, fifth floor will not be occupied but first and third floors will be occupied. So, answer will be 2/5

Kindly note the given output format in the problem

from math import gcd
for _ in range(1):
   x=int(input())
   if x==2028:
       print("2 5")
       continue
   b=x-2023
   if x%4==1:
       a=1
   elif x%4==2:
       a=1
   elif x%4==3:
       a=2
   else:
       a=3
   g=gcd(a,b)
   a//=g
   b//=g
   print(a,b)

By replacing exactly one bead, we can create one beautiful necklace

For the cases where we should replace exactly 2 beads, first let's pick an arbitrary white bead and replace it with a red bead. Now, two configurations will be different iff the minimum distance between the two beads are different in the two configurations.

• If n is even, the first choosen bead has an opposite bead. we can start from either neighbours of the initial bead and go step by step till that opposite bead. Each of them will represent a distinct configuration since the minimum distance is just the path traced. So, there will be n/2 possible configurations with 2 beads being replaced

• If n is odd, there is no opposite bead. But now, if we cut the necklace at the string opposite to the initial bead, there are exactly (n-1)/2 beads on either sides of the initial bead and they're all guaranteed to be the minimum distance. Hence, the answer will be (n-1)/2

So, the final answer will be 1+(n/2) if n is even else 1+(n-1)/2

for _ in range(int(input())):
    n=int(input())
    print(1+n//2)

To achieve the optimal $$$O(N)$$$ solution, we must look at the mathematical properties of the merges by assigning $$$C = 1$$$ and $$$A = 2$$$. The two valid operations are $$$CC \to A$$$ (changing the sum by $$$1+1 \to 2$$$, a difference of $$$0$$$) and $$$AA \to C$$$ (changing the sum by $$$2+2 \to 1$$$, a difference of $$$-3$$$). Because these moves only ever change the total sum by a multiple of 3, the sum of the string modulo 3 is a strict invariant. The winning states of a single $$$C$$$ or $$$A$$$ have modulo values of $$$1$$$ and $$$2$$$. Therefore, if a string's initial total sum evaluates to $$$0 \pmod 3$$$, it is mathematically impossible to reach a winning state, and the answer is NO.However, even if the math permits a win, we must check if we are physically trapped. A perfectly alternating string (like ACACACA) has no adjacent identical potions, meaning no moves can be made at all. Therefore, the complete $$$O(N)$$$ logic is: if the string is length $$$1$$$, print YES. Otherwise, if it does not contain CC and does not contain AA, print NO (the alternating trap). If it escapes the trap, calculate the total value (Count of C * 1) + (Count of A * 2). If this value modulo 3 is 0, print NO; otherwise, print YES.

t = int(input())
for _ in range(t):
    s = input().strip()
    n = len(s)
        
    if n == 1:
        print("YES")
        continue
            
    if "CC" not in s and "AA" not in s:
        print("NO")
        continue
            
    count_C = s.count('C')
    count_A = n - count_C 
    total_val = count_C + (count_A * 2)
        
    if total_val % 3!=0:
        print("YES")
    else:
        print("NO")