MUL - Fast Multiplication

Multiply the given numbers.


n [the number of multiplications <= 1000]

l1 l2 [numbers to multiply (at most 10000 decimal digits each)]

Text grouped in [ ] does not appear in the input file.


The results of multiplications.


4 2
123 43
324 342
0 12
9999 12345


Warning: large Input/Output data, be careful with certain languages

hide comments
Howard Roark: 2014-05-13 18:20:42

Well, after some timings it is clear that converting a 20,000 digit integer to a base 10 string is about 10-15 times slower than multiplying two 10,000 digit integers in python 3.2.3. So I have a few ideas on how to optimize the conversion.

Last edit: 2013-07-06 02:26:52
Howard Roark: 2014-05-13 18:20:42

Interesting; my python 3.2.3 code is too slow using native mult, and my python karatsuba implementation is slower than the native! Time to get smarter I guess to avoid the TLE. Perhaps I'm getting killed by the conversion to base10 for output?

Last edit: 2013-07-04 14:57:53
Giovanni Botta: 2014-05-13 18:20:42

Why is java allowed? There's no coding to be doing in java!

Gurjaspal Singh Bedi: 2014-05-13 18:20:42

Is bot not supporting .net framework 4.5?

(Tjandra Satria Gunawan)(曾毅昆): 2014-05-13 18:20:42

karatsuba just make your algorithm 2x slower than naive implementation!
Based on my experiment: 1 multiplication + 4 addition is slower than 2 multiplication + 1 addition.

Gerard Lledó: 2014-05-13 18:20:42

Just wanted to confirm that this is solvable under one second with an O(N^2) algorithm. No need for Karatsuba...

p|-|0en!x: 2014-05-13 18:20:42

Last edit: 2012-09-26 17:46:47
anuradha yadav: 2014-05-13 18:20:42

My Code is working perfectly fine for each test case even the bigger ones. What could be the reason for still getting WA. Please Help :(

Sumit Khanna: 2014-05-13 18:20:42

Is Karatsuba the right approach?!?I wrote the code applying karatsuba and it gives correct outputs on ideone,but shows TLE here,,, ,,here's my code,,smbdy help plz...

nishant10: 2014-05-13 18:20:42

it gave wrong answer when its output r correct to my knowledge please gave some more testcase

Added by:Darek Dereniowski
Time limit:1.649s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)