I hope I'm not late T_T

You're asked to find a multiple of $$$C$$$ in $$$[A,B]$$$ , Naive approach is to brute force $$$(A,B)$$$ and print the first number you encounter that's $$$i \mod C=0$$$ , Complexity is $$$O(\min(c,b-a))$$$.

Now Let's go to $$$O(1)$$$ Solution.

from math import *
a,b,c=map(int,input().split())
l,r=a//c,b//c
if(l!=r):
    print(ceil((l+r)/2)*c)
if(l==r):
    v=l*c
    if(a<=v and l*c<=v):
        print(l*c)
    else:
        print(-1)

Naively , you'll try all possible array elements when performing the operation in $$$O(n^2)$$$ ,however there's a better approach in $$$O(n)$$$.

from math import *
for _ in range(int(input())):
  n=int(input())
  a=list(map(int,input().split()))
  a[a.index(min(a))]+=1
  print(prod(a))

The intended solution is $$$O(n^2)$$$ that's by iterating through numbers from $$$1$$$ to $$$n$$$ two times and $$$z=n-x-y$$$ and check the conditions.

Well , We can even reach $$$O(1)$$$ , yes here's how

We've each number is either leaves a remainder of $$$1$$$ or $$$2$$$ $$$\text{mod}$$$ 3 and all of them are distinct.

$$$\infty$$$ denotes No solution.

that said means any $$$n \le 6$$$ is $$$\infty$$$ since we'll either repeat numbers and/or use $$$3$$$.

That's intended to avoid edge cases .

Now we can generalize this .

Now since we handled the edge cases (of repetition)

The First case satisfies $$$1 \neq 4 \neq n-5$$$ and $$$(n-5) \mod 3 \in { 1,2 }$$$

The Second case satisfies $$$2 \neq 5 \neq n-7$$$ and $$$(n-7) \mod 3 = 1$$$

Now the solution is complete and Total complexity is $$$O(1)$$$

for _ in range(int(input())):
    n=int(input())
    if(n<7):
        print('NO')
    elif(n==9):
        print('NO')
    elif(n==7):
        print('YES')
        print(1,2,4)
    elif(n==8):
        print('YES')
        print(1,2,5)
    elif(n==12):
        print('YES')
        print(4,7,1)
    elif(n%3 == 0 or n%3==1):
        print('YES')
        print(1,4,n-5)
    elif(n%3 ==2):
        print('YES')
        print(2,5,n-7)

I couldn't see a naive approach , so I'll go right to case work xD

def solve():
  x,y,k=map(int,input().split())
  if(k==1):
    print(x,y)
    return
  else:
    if(k%2==0):
      for i in range(k//2,k):
        print(x+i,y+i)
        print(x-i,y-i)
   else:
     for i in range(-(k//2),k//2+1):
     print(x+i,y+i)

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

we can split the solution using the sum of array $$$\sum b$$$ and the number of elements $$$k$$$,if we do comparison then we have 3 cases ($$$o$$$ is the number of operations):-

Total Complexity is $$$\mathcal{O}(n)$$$.

to minimize the number of gold , we want to select the first $$$\lceil \frac{n}{2} \rceil$$$ minimum numbers , It's easy to show that $$$n=1,2$$$ are always $$$-1$$$.\ since the average is measured as

it's enough add $$$a_{\lfloor \frac{n}{2} \rfloor}$$$ to the sum (in numerator) , this should be translated in form of numerator , thus must have at least $$$a_{\lfloor \frac{n}{2} \rfloor}+1$$$ to make this happen , and there's already $$$\sum a$$$ thus the answer is

and we've to check

Complexity is $$$\mathcal{O}(n\log n)$$$ due to sorting.

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    s=sum(a)
    a.sort()
    if(n<=2):
        print(-1)
    else:
        ans=(a[n//2]*2*n)-s+1
        if(ans>0):
            print(ans)
        else:
            print(0)

Maximum answer will be if all elements are distinct we'll have $$$\displaystyle \left ( \frac{n(n-1)}{2} \right )$$$, set $$$\mathtt{map}$$$ structure for counting the occurrences, for each element $$$i$$$, the answer is

Since each element $$$i$$$ will have $$$(\mathtt{map}[i])(\mathtt{map}[i]-1)/2$$$, this can be shown by simulating the process on small arrays

Complexity is $$$O(nlogn)$$$ due to sorting.

n=int(input())
mp={}
a=list(map(int,input().split()))
for i in range(n):
  try:mp[a[i]]+=1
  except:mp[a[i]]=1
ans=(n*(n-1))//2
for i in mp.keys(): ans-=(mp[i]*(mp[i]-1))//2
print(ans)

Notice that the answer is the absolute difference between the $$$i_{th}$$$ element on the column $$$x$$$ and every column $$$y$$$ such ($$$y>x$$$) .

For example assume a grid of $$$3 \times 3$$$ as following

You see that we're focusing on columns, but there is an organizing issue i.e. calculate the sum for each column naively is $$$O(n^2)$$$ yields $$$O(n^2m)$$$, This is not efficient of course, thus we've to optimize, almost always when you have \textbf{an organizing issue} you've to sort the array, thus you've to sort the columns such $$$c_1 \le c_2 \le c_3 \le ... \le c_n$$$, $$$c$$$ is any column on the grid,Sorting the columns, for single column it takes $$$O(n \log n)$$$ and there are $$$m$$$ columns, thus complexity for sorting the columns $$$O(nm\log n)$$$, now since we ensured that column is sorted thus we can formulate the answer for each column (for example the first one) as follows:

We can formulate how many $$$+a_7,-a_7,a_1,-a_1,a_4,-a_4$$$ are there, you'll observe that for some element $$$a_i$$$, The positives are $$$\text{index}(a_i)$$$ and negatives are $$$n-1-\text{index}(a_i)$$$ (assuming 0-based indexing) thus we'll have a total of

for each one, This will take $$$\displaystyle O(n)$$$ per columns and we've $$$m$$$ columns thus we've $$$O(nm)$$$ calculation, thus total complexity is $$$O(nm \log n)$$$.

for _ in range(int(input())):
  n,m=map(int,input().split())
  g=[]
  for i in range(n):
    a=list(map(int,input().split()))
    g.append(list(a))
  c=[[0]*n]*m
  ans=0
  for i in range(m):
    for j in range(n):
      c[i][j]=g[j][i]
  col=c[i]
  col.sort()
  for i in range(len(col)): 
    ans+=col[i]*(2*i-n+1)
  print(ans)

Notice that the number of possible elements of the array is $$$|[-200,200]|=401$$$,thus we can iterate through array elements and make a $$$\mathtt{map}$$$ data structure that counts the occurrences of each element, thus we can iterate through all possible pairs $$$(i,j)$$$ such $$$(i<j)$$$, and in each iteration we add $$$(j-i)^2 \cdot \text{cnt}_i \cdot \text{cnt}_j$$$

Total complexity is $$$O(N+\frac{401(400)}{2})$$$

$$$C$$$ is constant.

n=int(input())
a=list(map(int,input().split()))
f={}
for i in range(-200,201): f[i]=0
for i in a: f[i]+=1
ans=0
for i in range(-200,201):  
  for j in range(i+1,201):
    ans+=(j-i)*(j-i)*f[i]*f[j]
print(ans)

Let's Formulate the Problem , Let $$$f(n,k)$$$ so that $$$n$$$ is the $$$n_{th}$$$ message , Notice that :

Thus We have $$$f(n,k)$$$ is $$$\mathcal{O}(1)$$$ time , Now notice $$$f(n,k)$$$ is increasing with fixed $$$k$$$ , thus you can binary search with $$$l=0$$$ , $$$r=2k$$$ and obtain an answer , Total complexity is $$$\mathcal{O}(\log k)$$$.

def f(n,k):
    if(n<=k): return (n*(n+1))//2
    else:
        ans=(k*(k+1))//2+(n-k)*k-((n-k)*(n-k+1))//2
        return ans
 
for _ in range(int(input())):
    k,x=map(int,input().split())
    l,r=0,2*k
    ans=0
    if(x>=f(2*k-1,k)):
        print(2*k-1)
        continue
    while(l<=r):
        n=(l+r)//2
        if(f(n,k)==x):
            ans=n
            break
        if(f(n,k)<x<f(n+1,k)):
            ans=n+1
            break
        elif(f(n,k)<x):l=n+1
        else:r=n-1
    print(ans)

The maximum length of array $$$a$$$ is obtained when the difference of two consecutive differences is minimized ; Thus we set the difference of two consecutive differences is only 1 , For example consider $$$l=1,r=10$$$ thus we can consider the following array as the optimal choice

thus the maximum length is $$$4$$$ , Notice we can form an $$$\textbf{Optimal Model}$$$ , $$$a$$$ can be considered as :

since each time we've an element $$$l$$$ + Sum of First $$$n$$$ integers called Triangular Numbers

We want to determine the value of $$$x$$$ above i.e.

$$$\textbf{First approach }$$$ : Simulate the process with brute force in $$$O(\sqrt{r-l})$$$.

for _ in range(int(input())):
  l,r=map(int,input().split())
  x=1
  m=1
  while(l<=r):
    l+=x
    x+=1
    m+=1
  if(l==r):
    print(m)
  else:
    print(m-1)

$$$\textbf{Second approach}$$$ : $$$T(n)$$$ is increasing , thus we can use binary search in $$$O(\log(r-l))$$$

for _ in range(int(input())):
  a,b=map(int,input().split())
  l,r=0,b-a
  while(l<=r):
    m=(l+r)//2
    v=(m*(m+1))//2
    if(v>x): r=m-1
    else: l=m+1
  print(r+1)