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)