Thanks bashkort and peltorator for Month of Blogs Challenge
I hope I'm not late T_T
800
—1300
Requirements : Math , Observation , Sorting , Binary Search .
While Solving problems it's almost always needed you to analyze some cases in order to get with some useful information , In this blog , we'll be discussing some problems that smashes the guessing and bring the proof.
The Blog is intended for those who are unfamiliar with analysis .
abc220a. Find Multiple
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.
There's also a better approach, by counting the multiples of $$$C$$$ on $$$[A,B]$$$, this can be performed by defining $$$(l,r)=(\left \lfloor \frac{A}{C} \right \rfloor, \left \lfloor \frac{B}{C} \right \rfloor)$$$, thus we've two cases $$$l<r$$$ in this case an optimal answer is $$$\left \lceil \frac{l+r}{2} \right \rceil \cdot c$$$, and $$$l=r$$$ in this case we've to check if the only possible value in the range i.e. $$$a \le l\cdot c \le b$$$, if yes print $$$l \cdot c$$$ otherwise print $$$-1$$$, Total complexity of this solution is $$$\mathcal{O}(1)$$$.
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)
B. Good Kid
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)$$$.
Let's calculate the product of array in $$$O(n)$$$ that's
Now each time you can maintain a variable $$$v$$$ and in each iteration update it to $$$p \times \left ( \frac{a_i+1}{a_i} \right )$$$.
Since $$$p$$$ is constant , let's ignore it , we can just focus on $$$\left ( \frac{a_i+1}{a_i} \right )$$$ , notice that as much as $$$a_i$$$ is increasing as much as $$$\left ( \frac{a_i+1}{a_i} \right )$$$ is decreasing.
\lim_{x \rightarrow 0} \left ( \frac{x+1}{x} \right )= \infty \\
\end{cases} $$$
so now it's optimal to select the minimum number among them .
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))
A. Sum of Three
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$$$.
for $$$7$$$ : $$$(1,2,4)$$$
for $$$8$$$ : $$$(1,2,5)$$$
for $$$9$$$ : $$$\infty$$$ (why?) because you'll either use a multiple of three or repeat a number.
for $$$10$$$ : $$$(1,4,5)$$$
For $$$11$$$ : $$$(2,4,5)$$$
For $$$12$$$ : $$$(1,4,7)$$$
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)
A. Find K Distinct Points with Fixed Center
I couldn't see a naive approach , so I'll go right to case work xD
Let the points you want to output is
the center is
which means that
So we have : -
Complexity is $$$\mathcal{O}(k)$$$.
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()
A. Arithmetic Array
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):-
\sum b > k \rightarrow \textbf{add } n \textbf{ zeros} \rightarrow min(o)=n=\sum b-k \\ \end{cases}$$$
Total Complexity is $$$\mathcal{O}(n)$$$.
C. Robin Hood in Town
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)
C. Swappable
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)
B. Playing in a Casino
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)
C — Squared Error
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)
C. Chat Ban
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)
C. Longest Good Array
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)
If you've suggestions/problems please share them in comments !