Dear All,
Firstly, please read Prime Numbers and Primality Test.
Great! But, what if we calculate the whole array before submitting the problem to the judge?!
This is actually a very important trick that all good ACMers must know, so please read this message with great concentration.
Firstly, thank you very much, Hafez. You've chosen a very important topic; and a glitch that happens to appear every now and then in ACM problems – which is dealing with prime numbers.
I'll now solve problem 10924.
We have the string length = 20 as a maximum. This means that the "longest" string (I mean the string with the maximum sum) is "ZZZZZZZZZZZZZZZZZZZZ", which is equal to 52 * 20 = 1040. This means that – simply – the array called "prime" can be completely computed at compile time, so that we don't consume time at the judge.
So, I solved the whole issue on 2 steps. Firstly, I'll write a complete program to generate the array isPrime.
Then I'll just take this ready-made array and put it in my easy program…
And here we come to the most important lesson… that’s actually my aim behind sending this message…
WHENEVER THE DATA CAN BE INDEPENDENT OF THE INPUT, COMPUTE IT AT COMPILE TIME.
And I think you now understand that it’s actually your task to determine what data are independent of the input. This is very important, and can easily improve the performance of your solution drastically.
This is the pdf version of this article.
Firstly, please read Prime Numbers and Primality Test.
Great! But, what if we calculate the whole array before submitting the problem to the judge?!
This is actually a very important trick that all good ACMers must know, so please read this message with great concentration.
Firstly, thank you very much, Hafez. You've chosen a very important topic; and a glitch that happens to appear every now and then in ACM problems – which is dealing with prime numbers.
I'll now solve problem 10924.
We have the string length = 20 as a maximum. This means that the "longest" string (I mean the string with the maximum sum) is "ZZZZZZZZZZZZZZZZZZZZ", which is equal to 52 * 20 = 1040. This means that – simply – the array called "prime" can be completely computed at compile time, so that we don't consume time at the judge.
So, I solved the whole issue on 2 steps. Firstly, I'll write a complete program to generate the array isPrime.
Then I'll just take this ready-made array and put it in my easy program…
And here we come to the most important lesson… that’s actually my aim behind sending this message…
WHENEVER THE DATA CAN BE INDEPENDENT OF THE INPUT, COMPUTE IT AT COMPILE TIME.
And I think you now understand that it’s actually your task to determine what data are independent of the input. This is very important, and can easily improve the performance of your solution drastically.
This is the pdf version of this article.