Fall for Code Problem A Gandhian Series

help
1

In the problem Gandhian Series…my code’s complexity is O(T*k) I guess which is feasible to solve the problem still it is showing TLE
https://www.codechef.com/viewsolution/26910067
Please have a look at this
I know that problems of this type where we have to get the summation of 1^k + …+ 2^k
we have to do them in O(k)
still TLE…Why :pleading_face:
help!!!

1 Like
2 
    m = k + 1
    for i in range(2, m):
        temp = 0
        for j in range(0, i):
            temp -= binom(i + 1, j) * S[j]
            temp %= p
            # print(temp)
        temp -= (1 - (n + 1) ** (i + 1))

These bits are your problem. The inner loop has complexity O(k^2) and the raising n to a silly power in total is O(k log(k)) before considering the length of things we’re multiplying (up to 12000 digits which is probably slower than the O(k^2) operation for the choices of parameters we’re interested in).

3

how to solve this problem? means how to find sum of series (1^k + 2^k + … + n^k) in o(K)?

4

it is given here in the editorial

1 Like
5

thanks for sharing link.

1 Like
6

@admin please update test data of these question,its showing wrong answer, even on accepted codes.

7

I have updated the test files. Previously it was only changed for contest page. I have now changed it for both. Thanks for reminding. Sorry for the inconvenience caused!:slightly_smiling_face:

8

It might help Counting sums of powers - Codeforces

9

I have taken this code from hackerrank Solution of “Summing the K-N series”
where constraints were like 1<=n<=10^18 and 1<-k<=1000…
still it works there for T queries…
and what should I do to improve its complexity…
Thank you in advance

1 Like