Spinning Up Palindromes
This problem gives us a number, and asks what is the minimum number of additions by a powers of ten we must do to form a palindrome.
The limit of 10^40 gives a big hint that we must do this digit at a time, rather than mathematically.
If we knew the target number, we could simply perform a subtraction, but we don't. We also can't guarantee that it is the next smallest palindrome larger than the input number, since the solution could involve twiddling high bits.
If when adding, we could discard rollover, this problem would be trivial, since we could go by pairs of digits, starting outside and moving inward and solve each pair individually.
This leads us pretty close to a solution. Discarding rollover, the "answer" would be
- examine the outer pair of digits
- determine the minimum additions to make them equal
- recurse to the next pair
Now, to deal with rollover. Note that when we do recursion like this, every sub-problem has to be stable...that is, it only depends on the information passed in. So what extra information do we need for rollover
- we need to know if the less-significant of the pair of digits rolled over into the next digit
- we need to know if the more-significant received rollover from the digit before it (i.e. our solution for the next pair MUST have the more significant digit rollover.
This leads to 4 cases total
- no rollover occurs between this pair and the next pair
- the lower digit rolls only
- the upper digit receives rollover only
- both rollovers occur
We can try, and recurse, over each of the 4 cases (which case it is becomes a parameter to the recursion), choosing the minimum. Assuming we memoize, our state is 4*(40/2). Plenty fast.
Example
Lets say our number is
5xxxx1
The four cases above would yield
- add 4 to the 1 and recurse, there is no rollover
- we have to add at least 9 to the 1 to get a rollover, and then we have to add another 5 to get it to match
- since the 5 is receiving rollover, it is now at 6. we can add 5 to the 1 to make them match at 6
- the 1 has to rollover, so we add 9 there. The 5 becomes a 6 because it received rollover. Then we have to add another 6 to the 1's digit to make them match at 6
Note that which of the 4 options we choose above may be limited by what we have to do. For example, if we recursed to a pair which must NOT rollover the higher digit (remember this is a parameter to the recursion), we cannot receive rollover if that digit is already a 9, since that would force a rollover of ourselves! This fact ultimately leads to 16 cases: we have 4 cases to handle because of the incoming recursive call, and we have potentially 4 recursive calls to make for each.
Then to add to those, we have to special case handle the inner digits, differently, of course, if the number has an odd or even number of digits. This yields another 16 cases or so to deal with. See the code for description.
import java.util.*;
public class f {
static Scanner in=new Scanner(System.in);
public static void main(String[] args) {
String s=in.nextLine();
int[] num=new int[s.length()];
for(int i=0;i<s.length();i++)num[i]=Integer.parseInt(s.substring(s.length()-i-1, s.length()-i));
int[][] dp=new int[s.length()/2][4];//0=no rollover on either side, 1=lower number rolls over, 2=higher number RECEIVES rollover, 3=both
for(int[] i:dp)Arrays.fill(i, Integer.MAX_VALUE);
System.out.println(Math.min(recurse(num, dp, 0, 0), recurse(num,dp,0,2)));//no rollover INTO first lower number
}
private static int recurse(int[] num, int[][] dp, int index, int rollover) {
int low=num[index],high=num[num.length-index-1], min=Integer.MAX_VALUE/100;
if(index==num.length-index-1) {//special case handling when we've reached the middle number of an odd number of digits
if(rollover==0)return 0;//no rollover...nothing special
if(rollover==1)return low==9?Integer.MAX_VALUE/100:0;//impossible to receive rollover and not pass it back if number is a 9
if(rollover==2)return 10-low;
if(rollover==3)return 10-(low+1);
}
if(index+1==num.length-index-1) {//special case handling when we've reached the two middle numbers of an even number of digits
if(rollover==0) {
min=Math.min(min, Math.abs(low-high));
if(high<9)min=Math.min(min, (10-low)+(high+1));//if high is less then 9, then optimal solution might be to rollover between the two
return min;
}
if(rollover==1) {
if(low==9&&high==9)return Integer.MAX_VALUE/100;//impossible case
if(low==9) return high+1;// guaranteed rollover
min=Math.min(min, Math.abs(high-(low+1)));
if(high<9)min=Math.min(min, (10-(low+1))+(high+1));
return min;
}
if(rollover==2) return Math.min((10-high)+low, (10-(high+1))+(10-low));//two cases here...1) spin high until it rolls, then spin until it matches low, 2) low number rolls, then high number rolls
if(rollover==3) {
if(low==9)return 10-(high+1);//just roll the high number
else return Math.min((10-high)+low+1, (10-high+1)+(10-(low+1)));//two cases here...1) spin high until it rolls, then matches low plus rollover, 2) roll low number, then roll high
}
}
if(dp[index][rollover]<Integer.MAX_VALUE)return dp[index][rollover];
if (rollover==0) {//lower number didn't rollover into us, upper number doesn't have rollover
min=Math.min(min, Math.abs(high-low)+recurse(num,dp,index+1,0));//neither rolls over
min=Math.min(min, high+(10-low)+recurse(num,dp,index+1,1));//lower number rolls over
if(high<9) {//can't do cases where high accepts rollover if we are a 9 but aren't allowed to pass rollover through
min=Math.min(min, Math.abs(low-(high+1))+recurse(num,dp,index+1,2));//upper number receives rollover
min=Math.min(min, (high+1)+(10-low)+recurse(num,dp,index+1,3));//lower number rolls, and upper receives rollover
}
} else if(rollover==1) {//lower number has to receive rollover...must skip cases where this would force us to pass rollover through when not supposed to on low number
if(low<9)min=Math.min(min, Math.abs((low+1)-high)+recurse(num,dp,index+1,0));//neither rolls over
min=Math.min(min, high+(10-(low+1))+recurse(num,dp,index+1,1));//lower number rolls over
if(high<9) {
if(low<9)min=Math.min(min, Math.abs((low+1)-(high+1))+recurse(num,dp,index+1,2));//upper number receives rollover
min=Math.min(min, (high+1)+(10-(low+1))+recurse(num,dp,index+1,3));//lower number rolls, and upper receives rollover
}
} else if(rollover==2) {//higher number has to rollover...lower number does NOT receive rollover
min=Math.min(min, (10-high)+low+recurse(num,dp,index+1,0));
min=Math.min(min, (10-high)+(10-low)+recurse(num,dp,index+1,1));//both numbers rollover
min=Math.min(min, (10-(high+1))+low+recurse(num,dp,index+1,2));
min=Math.min(min, (10-(high+1))+(10-low)+recurse(num,dp,index+1,3));
} else {//higher number has to rollover, lower number has to receive rollover
if(low<9)min=Math.min(min, (10-high)+(low+1)+recurse(num,dp,index+1,0));
min=Math.min(min, (10-high)+(10-(low+1))+recurse(num,dp,index+1,1));
if(low<9) min=Math.min(min, (10-(high+1))+(low+1)+recurse(num,dp,index+1,2));
min=Math.min(min, (10-(high+1))+(10-(low+1))+recurse(num,dp,index+1,3));
}
dp[index][rollover]=min;
return dp[index][rollover];
}
}