Boris Coding Blog

Hello folks, back from a trip to Europe, and with a nasty flu virus type A. In any case, I realized that I never posted the follow-up to the "palindrome with errors" problem - so here it is. As I had mentioned, a naïve brute-force solution would lead to a runtime of O(2^(length of string)), which given the constraints of length of string <= 120,000, such solution would be intractable. A slightly better solution is still exponential, but exponential in the max number of errors which the problem limits to 13. The solution below will work in O(3^13), or ~2,000,000 steps, which is super fast. The idea is to analyze the string as if it was already a palindrome. Therefore, take a look at the extremes of the string. If they match, then it is so far a palindrome. In which case you continue the analysis by moving inwards. The moment that you determine that the extremes don't match, that's when the exponential aspect will take place. What you'd have to do then is r

The great Euclid came up with one of the oldest and most acclaimed mathematical proofs of all times: the proof that there is no upper-bound limit to the set of prime numbers. Or, put in a different way, prime numbers are infinite. There is no question whatsoever that the proof is not only correct beyond any doubt but also marvelously simple to understand. However, despite all the brilliance in the proof, there are two aspects of it that slightly bothered some (very picky) mathematicians out there.  The first one is that there is an underlying assumption (more like an insinuation, a hint) that not only the largest prime needs to be known for the proof to work, but also all the other primes too. I can see why it kind of bothers some purists, although the vast majority of mathematicians will argue that such assumption is complete non-sense, that the proof is designed to work even without that assumption in place, which I understand. But in any case, the controversy is t