ICPC AlgoQueen 2022

For AlgoQueen 2022, register here - AlgoQueen 2023 Registration

And start practising by solving last year’s question from here

AlgoQueen 2021

AlgoQueen 2021 Round 0
AlgoQueen 2021 Semi Finals
AlgoQueen 2021 Finals

If you have any questions feel free to ask here

3 Likes
def main():
	 i = int(input())
	 for _ in range(i):
	 	A, N = map(int, input().split(" "))
	 	ans = solver(N, A)
	 	print(ans)

def solver(N, A):

	middle_term = (N+1)//2
	series_list = []
	for i in range(0, (N + 1)):
		x = A ** i
		series_list.append(x)
	series_list = sorted(series_list)
	return series_list[middle_term]


if '__main__' == __name__:
	main()

Well done @Gayatri_Taneja

@Deepa_Panwar1, I am sorry for the incomplete post, I intended to ask a question, with reference to the above code snippet. Mentioning it below for reference:

I tried to use this for Integer on Stones, it seems to be working but shows the time limit exceeded error. I am not sure if it completely accurate though it passed the initial test case.

Could you please help me out?
Thanks

The A ** i is too slow as numbers are very big. Think little more and derive mathematical formula.

@Gayatri_Taneja some optimisations you can do in your code:

  • You are calculating all A^i, but is there a way to skip calculating all? Let us see.

    1. If A is positive we know that A^N will always be greater than A^(N-1) which will in turn be greater than A^(N-2) and so on, we can determine that A^(middle_term) will always be the answer.
    2. If A is negative, then the sign of the terms would alternate. So for each positive number, there will also be a matching negative number. So the middle term would be A^0 = 1. E.g. if A = -2, N = 4 then the terms are [1,-2,4,-8,16] and sorting them we will have [-8,-2,1,4,16] so the answer here will be 1

However just this observation alone is not enough. For the first case, you will need to calculate A^(middle_term). But middle_term can be very large. Note that the answer has to be modulo mod. For that there is a technique called modular exponentiation. You can read more about fast modular exponentiation in this and next few lessons on this link.

Here is a sample solution in python for the same:

mod = int(1e9) + 7

def modpow(a, b):
    if a == 0:
        return 0
    global mod
    res = 1
    while b > 0:
        if b % 2 == 1:
            res = res * a % mod
        a = a * a % mod
        b = b // 2
    
    return res
    
T = int(input())
for _ in range(T):
    A, N = map(int, input().split(' '))
    ans = 0
    if A > 0:   
        ans = modpow(A, N // 2)
    if A < 0:
        ans = 1
    print(ans)
2 Likes