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))