ICPC AlgoQueen 2022

Algo Queen
, , ,
1

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
2 
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()
3

Well done @gayatri

4

@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

5

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

2 Likes
6

@gayatri 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
7

i am not able to submit the code

8

Please share the error you are getting?

9

I can’t submit my code

10

this show that only accepted members can submit but i am a accepted member

11

Please share your error message

12

image
image904×155 7.04 KB

13

I’m not able to join
the contest

14

It shows you are not registered for the contest, please send email to hello@codedrills.io stating this issue, I will check whether your email is registered or not. Please don’t share your email here.
Or use chat feature on codedrills.io

15

Please share your error message from registered email hello@codedrills.io or use live chat support from codedrills.io during contest

16

but i registered & my team also shows

17

Hi, Palak as I shared in live chat, you are registered as coach 5 times, please make sure you are registered as member before next contest.
Note: Coach is optional you can leave that field empty in Registration form

18

how can i edit my registration form ?

19

Once contest started, you can’t. I will open registration for tomorrow’s contest. Please make sure to register for that.

20

by same email account. can i register again?