Contest Link : Project Her 1.0
Problem: Special 7
Problem setter: jay_munjapara
DIFFICULTY:
Easy
Logic (Explanation)
This can be solved by taking the input as a string and then linearly searching for ‘7’ (as a character instead of a number) in the string.
You can use in-build functions too. Refer this article for better understanding
Solution in Python
T=int(input())
for _ in range(T):
print('7' in input())
Problem: Digitone
Problem setter: @jeemitsha
DIFFICULTY:
Easy
Logic (Explanation)
This question can be solved with brute force. We follow the steps in question.
It can be noted that successive sum of digits of a number until it becomes a single digit is that number modulo 9. Where 0 becomes 9. For example, for
1234567 becomes 1+2+3+4+5+6+8 = 29 => 2+9 = 11 => 1+1 => 2
1234568%9 = 2.
Hence we this for the last step of the problem
Solution in Python
for _ in range(int(input())):
n = int(input())
a,b = map(int,input().split())
l = list((str(n)))
o,e = 0,0
s=0
for i in range(len(l)):
if i&1:
o+=int(l[i])*b
else:
e+=int(l[i])*a
s=o+e
s%=9
if s==0:s=9
print(s)
Problem: Wierd Fibonacci
Problem setter: @jeemitsha
DIFFICULTY:
Easy-Medium
Logic (Explanation)
There are two optimisation in this solution. There first one is to precompile the normal Fibonacci series before taking the T i.e the test case number.
The second optimisation is use modulo at each step while compiling the Fibonacci series. The number becomes too be big to add them. Then for each query we use the existing Fibonacci series to make the weird series.
Solution in Python
mod = 10 ** 9 + 7
fibo=[0,1]
a=0
b=1
c=1
for i in range(2,10**6):
c=a+b
a=b
b=c
a%=mod
b%=mod
c%=mod
fibo.append(c)
#print("done")
for _ in range(int(input())):
n,m=map(int,input().split())
#l-=1
#r-=1
#print(*fibo[:10])
i=0
j=n-1
count=0
ans=[]
while count<m:
print(fibo[i],end=" ")
count+=1
i+=1
if count>=m:
break
print(fibo[j],end=" ")
count+=1
j-=1
print()
Problem: The Birthday Fiesta
Problem setter: @utkarsha1910
DIFFICULTY:
Easy-Medium
Logic (Explanation)
For this problem, we are to first identify unique characters in the string. Then, we are to print all the permutation in lexicographical order. We may use inbuilt functions such as permutation from itertools in python or using next_permutation in cpp. You can refer this to print all permutations
Solution in Python
from itertools import permutations
t=int(input())
text='abcdefghijklmnopqrstuvwxyz'
for _ in range(t):
n=int(input())
s=input()
st=""
for letter in text:
if letter in s:
st+=letter
ans=list(permutations(st))
print(len(ans))
Ans=[]
for i in ans:
Ans.append(''.join(i))
print(*Ans)
Problem: Un-ek
Problem setter: @hardee_ck
DIFFICULTY:
Easy-Medium
Logic (Explanation)
This is a Dynamic programming problem. You may use memorisation to solve this.
While traversing, we check if the current element forms and chain with elements that we have already traversed. We do this by using a dictionary where we store the coordinates of element ( if it is 1) along with the length of chain it forms (horizontal, vertical, two diagonals)
The time complexity of this solution is O(N).
Solution in Python
def solve(mat,k):
d={}
for i in range(len(mat)):
for j in range(len(mat[0])):
if mat[i][j]==1:
#horizontal
if (i,j-1,'H') in d.keys():
d[(i,j,'H')]=d[(i,j-1,'H')]+1
else:
d[(i,j,'H')]=1
#vertical
if (i-1,j,'U') in d.keys():
d[(i,j,'U')]=d[(i-1,j,'U')]+1
else:
d[(i,j,'U')]=1
# diagonal /
if (i-1,j+1,'/') in d.keys():
d[(i,j,'/')]=d[(i-1,j+1,'/')]+1
else:
d[(i,j,'/')]=1
# diagonal \
if (i-1,j-1,'\\') in d.keys():
d[(i,j,'\\')]=d[(i-1,j-1,'\\')]+1
else:
d[(i,j,'\\')]=1
counter=0
for key,value in d.items():
if value>=k:
#print(key)
counter+=1
return counter
import time
st=time.time()
n,m,k=map(int,input().split())
mat=[]
for i in range(n):
mat.append(list(map(int,input().split())))
#print("done")
print(solve(mat,k))
Problem: City
Problem setter: @jenil_kanani
DIFFICULTY:
Medium
We get the following things as input:
Logic (Explanation)
- T: Number of cities.
- n: Number of stations in the city.
- b: Base price for the real estate in the city.
- x, y: The x and y coordinates of the station.
Among the points given, connect the outermost points by using the fastest way, graham’s scan algorithm which is a O(nlogn) solution to find the convex hull. After that remove the points that make up the convex hull and apply the graham’s scan again to the remaining points until you are left with less than three points(because it’s not possible to make a polygon with less than 3 points).
After finding the total number of convex hulls possible, we need to find the average price.
So for example number of hulls is 4 and the base price is 5,
Average real estate = ((15) + (15) + (25) + (35)) / 4
Average real estate = ((1 + 1 + 2 +3) * 5 ) / 4
Here we need to find the sum of the first n fibonacci series, for this we use Sum of first n fibonacci numbers = (n+2th fibonacci number) - 1. And to find the nth fibonacci number we use a fast doubling algorithm which is an O(logn) solution.
Eg.-
sum of first 4 fibb nos. = (4 + 2 th fibb number) - 1
6th fibb number is 8 so minus 1 is 7
1 + 1 + 2 + 3 = 7
Solution in Python
from functools import reduce
MOD = 1000000007
res = [0]*2
# function to find convex hull using graham's scan(nlogn)
def convex_hull_graham(points):
TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0)
def cmp(a, b):
return (a > b) - (a < b)
def turn(p, q, r):
return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)
def _keep_left(hull, r):
while len(hull) > 1 and turn(hull[-2], hull[-1], r) ==-1:
hull.pop()
if not len(hull) or hull[-1] != r:
hull.append(r)
return hull
points = sorted(points)
l = reduce(_keep_left, points, [])
u = reduce(_keep_left, reversed(points), [])
return l.extend(u[i] for i in range(1, len(u) - 1)) or l
# function to find difference of two lists
def Diff(li1, li2):
return list(list(set(li1)-set(li2)) + list(set(li2)-set(li1)))
# Function calculate the N-th fibanacci number using fast doubling method
def FastDoubling(n, res):
if (n == 0):
res[0] = 0
res[1] = 1
return
FastDoubling((n // 2), res)
a = res[0]
b = res[1]
c = 2 * b - a
if (c < 0):
c += MOD
c = (a * c) % MOD
d = (a * a + b * b) % MOD
if (n % 2 == 0):
res[0] = c
res[1] = d
else :
res[0] = d
res[1] = c + d
import time
st=time.time()
T=int(input())
for _ in range(T):
# input for number of points and the base price for the city
n, base_price = map(int, input().strip().split(" "))
pnts = []
for i in range(n):
pnts.append(tuple(map(int, input().strip().split(" "))))
new_pnts = convex_hull_graham(pnts)
if new_pnts:
hulls = 1
while len(pnts) - len(new_pnts) > 2:
hulls += 1
pnts = Diff(pnts, new_pnts)
new_pnts = convex_hull_graham(pnts)
#print(new_pnts)
FastDoubling(hulls + 2, res)
#print(hulls)
print(round(((res[0] - 1) * base_price)/ hulls)%MOD)
else:
# If no convex hulls possible from the given set
print(0)
Problem: Infinity Chess
Problem setter: @yashjb_29
Logic (Explanation)
We get the following things as input:
- T: Number of test cases.
- N: Order of the chess board.
Here we have (N/2) queens for our chess board. Where all the queens are placed in diagonal manner. So we can see a pattern where an odd number of n has the same number of safe squares as that of n-1. After finding out the number of queens if the no. of queens are odd then divide the number of queens by 2 and take floor value of it and finally take square value of it to find of the number of safe squares also this is for half side at the end this part is only for half part of the diagonal so u multiply by 2 to get the final answer.
If the no. of queens are even then we directly divide the no. of queens by 2 and subtract by 1
And finally to find out even number of squares we use summation formula that this x*(x+1)
And multiply by 2 to get the answer.
Example :
This is for n = 11 and we have even no. of queens so first of all we will -1 from n so now n = 10 this means 10 and 11 will have the same no. of safe squares . since queens are even we divide by 2 and subtract by 1 and then use the sum formula to find the series of alternate numbers here we have (1 + 3) and we multiply by 2 to get both the sides of the diagonal.
Solution in Python
MOD=10**9+7
for t in range(int(input())):
n = int(input())
if n % 2 == 1:
n -= 1
n /= 2
if n % 2 == 1:
num_of_odds = n // 2
print((int(num_of_odds ** 2) * 2)%MOD)
else:
num_of_evens = (n / 2) - 1
print((int(num_of_evens * (num_of_evens + 1)) * 2)%MOD)
Congratulations to the Contest Winner!