| Submit | All submissions | Best solutions | Back to list |
MUL - Fast Multiplication |
Multiply the given numbers.
Input
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.
Output
The results of multiplications.
Example
Input: 5 4 2 123 43 324 342 0 12 9999 12345 Output: 8 5289 110808 0 123437655
Warning: large Input/Output data, be careful with certain languages
| Added by: | Darek Dereniowski |
| Date: | 2004-06-01 |
| Time limit: | 1.649s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
| Resource: | PAL |
hide comments
|
||||||||||||||
|
2014-05-13 18:20:42 Howard Roark
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 |
||||||||||||||
|
2014-05-13 18:20:42 Howard Roark
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 |
||||||||||||||
|
2014-05-13 18:20:42 Giovanni Botta
Why is java allowed? There's no coding to be doing in java! |
||||||||||||||
|
2014-05-13 18:20:42 Gurjaspal Singh Bedi
Is bot not supporting .net framework 4.5? |
||||||||||||||
|
2014-05-13 18:20:42 (Tjandra Satria Gunawan)(曾毅昆)
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. |
||||||||||||||
|
2014-05-13 18:20:42 Gerard Lledó
Just wanted to confirm that this is solvable under one second with an O(N^2) algorithm. No need for Karatsuba... |
||||||||||||||
|
2014-05-13 18:20:42 anuradha yadav
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 :( |
||||||||||||||
|
2014-05-13 18:20:42 Sumit Khanna
Is Karatsuba the right approach?!?I wrote the code applying karatsuba and it gives correct outputs on ideone,but shows TLE here,,,<snip> ,,here's my code,,smbdy help plz... Last edit: 2023-05-17 20:50:14 |
||||||||||||||
|
2014-05-13 18:20:42 nishant10
it gave wrong answer when its output r correct to my knowledge please gave some more testcase |
||||||||||||||
|
2014-05-13 18:20:42 Sandeep Singh Jakhar
nice problem of karatsuba..!! |
||||||||||||||
RSS