Recently in the BESU tech fest, the final round of programming event contained a series of interesting questions.
Even though I was unlucky enough to not win a prize (after making some kiddish mistakes), I happen to have discovered something of a problem that read:
Anusha, an over-enthusiastic R&D manager of a pharmaceutical company known for her love of cryptography, has hidden the lifetime of each new drug within it's product code. Let x be the product code of a drug in some base. If x is a palindrome, it is left unaltered. Otherwise, x is added to its reverse. This process is continued until the number becomes a palindrome. The number of steps required to make x into a palindrome is called StepsToPalindrome. Each drug has a shelf life after which it is withdrawn from the market and reprocessed by the company and a time to rejection after which it is deemed unfit for use and is discarded by the company. The shelf life is the minimum StepsToPalindrome and time to rejection is the maximum StepsToPalindrome among all bases in which x can be represented.
So, this basically means that one needs to first find the smallest base in which the product code can be expressed. In this problem the product code was to have digits (0-9) and alphabets (A-F). So it would effectively mean that the maximum single digit will be 'F' or the minimum base will be 16.
Now the first part of the solution is what I am concerned about right now. How can I find the smallest number of steps to palindrome in any base?
Well, after much thought (not in the event though) I found that the result will always be 1. Since if a number can be expressed in a base say 'X', then the largest digit within the number must be 'X-1'. Now, the number would become a palindrome only when the reverse of itself added would not generate any carry. Thus, it is always possible to find a base Y, such that the sum of 2 digits ( where the digit can be within the range >= X/2 and <= X-1 ) would not yield a carry! Hence making the number turn into a palindrome in 1-step.Of course, Y>= 2*(X-1).
Even though I was unlucky enough to not win a prize (after making some kiddish mistakes), I happen to have discovered something of a problem that read:
Anusha, an over-enthusiastic R&D manager of a pharmaceutical company known for her love of cryptography, has hidden the lifetime of each new drug within it's product code. Let x be the product code of a drug in some base. If x is a palindrome, it is left unaltered. Otherwise, x is added to its reverse. This process is continued until the number becomes a palindrome. The number of steps required to make x into a palindrome is called StepsToPalindrome. Each drug has a shelf life after which it is withdrawn from the market and reprocessed by the company and a time to rejection after which it is deemed unfit for use and is discarded by the company. The shelf life is the minimum StepsToPalindrome and time to rejection is the maximum StepsToPalindrome among all bases in which x can be represented.
So, this basically means that one needs to first find the smallest base in which the product code can be expressed. In this problem the product code was to have digits (0-9) and alphabets (A-F). So it would effectively mean that the maximum single digit will be 'F' or the minimum base will be 16.
Now the first part of the solution is what I am concerned about right now. How can I find the smallest number of steps to palindrome in any base?
Well, after much thought (not in the event though) I found that the result will always be 1. Since if a number can be expressed in a base say 'X', then the largest digit within the number must be 'X-1'. Now, the number would become a palindrome only when the reverse of itself added would not generate any carry. Thus, it is always possible to find a base Y, such that the sum of 2 digits ( where the digit can be within the range >= X/2 and <= X-1 ) would not yield a carry! Hence making the number turn into a palindrome in 1-step.Of course, Y>= 2*(X-1).
No comments:
Post a Comment