Thank you for Participating !
A.Hasan and Binary Function
We can obtain $$$n$$$ from the binary representation as following
We know that the fact
Let’s consider the last active bit i.e. $$$\mathtt{1}$$$ is $$$i$$$ then $$$n$$$ as integer is
thus the answer is the index of last occurrence of $$$\mathtt{1}$$$ , Complexity $$$O(n)$$$.
for _ in range(int(input())):
n=int(input())
s=input()
ans=0
for i in range(n):
if(s[i]=='1'):
ans=n-i-1
break
print(ans)
B.Hasan and Beautiful !
Maintain two arrays $$$b$$$ and $$$c$$$ such that
Now , maintain a function $$$f$$$ that process the maximum subarray sum in $$$O(n)$$$ for both of arrays $$$b$$$ and $$$c$$$ (Kadane's Algorithm for example), be careful of initialization that it’s non-empty , and the answer is $$$\max(f(b),f(c))$$$ , Complexity $$$O(n)$$$.
def f(a):
best = a[0]
sum = a[0]
for i in range(1, len(a)):
sum = max(a[i], sum + a[i])
best = max(best, sum)
return best
for _ in range(int(input())):
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = a.copy()
c = a.copy()
for i in range(n):
b[i] //= k
c[i] *= k
print(max(f(b), f(c)))
C.Hasan and Special Remove
One way to solve the problem is to make a fixed-size sub-array and iterate through the array and test all the subarrays with length $$$k$$$ i.e Sliding window of length $$$k$$$ , so we can make a sliding window with length $$$k$$$ and iterate the array which yields $$$n- k + 1$$$ and you delete $$$k − 1$$$ elements in total then the total complexity for each case can reach $$$O(n^2)$$$ ,Unfortunately it’s not efficient enough so we should optimize!. We can optimize the solution by making a frequency map ; we use a greedy approach by removing the first $$$k$$$ elements from Map (dict) structure , and then doing a sliding window minimum and finally obtain the minimum final number of distinct numbers , total complexity is $$$O(n \log n)$$$ due to using maps.
def solve():
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [str(arr[i]) for i in range(n)]
dic = {}
for num in a:
if num not in dic: dic[num] = 0
dic[num] += 1
for i in range(k):
dic[a[i]] -= 1
if dic[a[i]]==0: del dic[a[i]]
ans = len(dic)
for i in range(k,n):
if a[i-k] not in dic: dic[a[i-k]] = 0
dic[a[i-k]] += 1
dic[a[i]] -= 1
if dic[a[i]]==0: del dic[a[i]]
ans = min(ans, len(dic))
print(ans)
for _ in range(int(input())):
solve()
D.Hasan and Permutations
Let's see for each index $$$i$$$ among the permutation $$$p_n$$$ , what's the count of possible cases for it , we can use $$$(n-i)$$$ integers , thus for each index $$$i$$$ the count is $$$2^{n-i}$$$ , thus the answer will be the sum of count overall indices
due to exclusion of last index , complexity is $$$O(\log n)$$$ (Binary Exponentiation).
m=10**9+7
def p(a,b,m):
a%=m
r=1
while(b>0):
if(b&1):
r=r*a%m
a=a*a%m
b>>=1
return r
def ff(n):
return (p(2,n,m)-n-1)%m
for _ in range(int(input())):
n=int(input())
print(ff(n))
E.Square Triangle
F.Behruzbek and XOR Queries
G.Hasan and Fair Split
notice that the set of prime factors common between numerator and denumerator are the same and in the numerator for each power of common it’s at least has the same power as den and We’re aiming to minimize the product thus we need to make a divisible by b (for each prime separately) so whenever we had an even power for some prime the best thing is split it into equal parts.
Calculate sieve for all numbers upto $$$2 \cdot 10^5$$$ this can be achieved in $$$O(n \log(\log(n)))$$$ which is fast , Find the prime factorization of $$$n!$$$ this can be found with the prime factorization form of $$$n!$$$
For each prime factor $$$p_i$$$ the power $$$\alpha_i$$$ can be calculated with the following formula
it can be show that this sum converges in $$$a$$$ , $$$O(\log(n))$$$ it’ll take no more than $$$20$$$ runs , thus the final prime factorization will take $$$O(20p)$$$.
Now we want to have $$$a \bmod b = 0$$$ (assuming fraction $$$\frac{a}{b}$$$) , so a productive greedy is to have for each $$$p_i$$$ with power $$$\alpha_i$$$ the following : for $$$a$$$ the power is $$$\displaystyle \left \lceil \frac{\alpha_i}{2} \right \rceil$$$ and for $$$b$$$ the power is $$$\displaystyle \left \lfloor \frac{\alpha_i}{2} \right \rfloor$$$.
Therefore we only need to look at $$$\alpha_i \bmod 2 = 1$$$ i.e. odd powers , and calculate The following
For each test case , we calculate for each prime upto $$$n$$$ it’s power , the count of prime upto $$$n$$$ are approximately $$$O \left ( \frac{n}{\log(n)} \right )$$$ and we check the power in $$$O(\log(n))$$$ and even better in practice , this yields prime factorization of $$$n!$$$ takes at most $$$O(n)$$$ time , we can with each prime factorized if the final power is odd then multiply it by the answer and take the modulus by $$$10^9 + 7$$$ , thus the total complexity for multiple test cases is $$$O(8 \cdot 10^5)$$$ for precalculation of sieve (primes) , and $$$O(\sum n)$$$ for answering test cases.
def solve():
x = int(input())
ip= [1] * (x + 1)
ip[0] = ip[1] = 0
for i in range(2, int(x**0.5) + 1):
if ip[i]:
for j in range(i * i, x + 1, i):
ip[j] = 0
p = [0] * (x + 1)
for i in range(2, x + 1):
if ip[i]:
cnt = 0
j = i
while j <= x:
cnt += x // j
if j > x // i: break
j *= i
p[i] = cnt
ans = 1
MOD = 10**9 + 7
for i in range(2, x + 1):
if p[i] % 2:
ans = (ans * i) % MOD
print(ans)
for _ in range(int(input())):
solve()