Sum All Numbers

I did it in C++ using bigints and it works for 25/30 cases , the 5 fail because if i allow a number of digits high enough i get tle , if not i get WA , the algo is correct.

I did it in python too and i fail only on 3 cases i get TLE , so how did you implement the multiplication of bigints , O(N^2) is too much.

I tried to use the Karatsuba algo , but i cant find a good enough explanation so that i can code it out , it would reduce the complexity to O(N^1.58) which would be enough to pass the remaining 3 .

Any hints ?

There is a way to fast up bignum multiplication ... I think this is the key :)

p.s. try to make to your solution V times faster .... Figure out V^^

you can do it with:
((first + last) / 2) * n
you must code bignum.
I think that I helped you :)

I've already solved the problem , I used Toom-Cook 4 way multiplication of bigints

can you explain that algorithm??

I found it in this book - D. Knuth. The Art of Computer Programming

But there's a nice explanation on wikipedia:
http://en.wikipedia.org/wiki/Toom–Cook_multiplication

tnx

Може ли неко да ми каже како да убрзам овај код?
http://z-trening.com/submit.php?submit=7100074334&subm_code=1

Ja koliko mogu da vidim , ti imas O(N^2) mnozenje big numova , pokusaj naci na netu neki brzi algo za mnozenje 2 big numa
hint:
pogledaj postojece bibiloteke za bignum
pogledaj karatsuba algo
pogledaj toom-cook algo