PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
The most obvious approach here is to iterate over all permutations of digits of A, calculate B’ = C - A’ where A’ is a current permutation of A and check whether B’ is a permutation of B. Interestingly that under assumptions of the problem (that is X * len <= 80) this approach is fast enough for large bases 10, 9, 8 and even 7. But for small bases it is very slow, especially for 2, 3 and 4. Thus we need another algorithm here.
At first consider the worst case for the first approach - the base 2. Assume for simplicity that A, B and C all have equal length and denote it by L. Denote digits of C by C1, C2, …, Cl and its prefix of length k by C(k), that is C(k) = C1C2…Ck (see notation in the problem statement). Also denote by nA and nB the number of ones in binary representation of A and B respectively.
Let dp[d][k][na][nb] stands for the number of pairs of non-negative integers A’ and B’ such that
A’ and B’ has exactly k digits in binary (possibly with leading zeros);
A’ has na ones in binary;
B’ has nb ones in binary;
A’ + B’ + d = C(k).
It is easy to see that dp[0][0][0][0] = 1, dp[ 1 ][0][0][0] = 0 and the answer to the problem is dp[0][L][nA][nB].
Here for parameters d, k, na, nb the following inequalities hold
0 <= d <= 1;
0 <= k <= L;
0 <= na <= min(k, nA);
0 <= nb <= min(k, nB).
Now let’s consider what transitions we have between states of this dp. Let x and y be the last digits of numbers A’ and B’. Then equation A’ + B’ + d = C(k) is equivalent to the couple of relations
x + y + d = 2 * d’ + Ck where 0 <= d’ <= 1;
A’’ + B’’ + d’ = C(k - 1),
where A’’ is obtained from A’ by erasing its last digit and similar is for B’'.
If we fix x then y and d’ determined uniquely from the first condition
y = (Ck - d - x) mod 2;
d’ = (x + y + d) div 2.
Now consider the second condition A’’ + B’’ + d’ = C(k - 1). It is very similar to the 4th condition in definition of dp[d][k][na][nb]. Note that A’’ have na’ ones in binary where na’ = na if x = 0 and na’ = na - 1 if x = 1 and B’’ have nb’ ones in binary where nb’ = nb if y = 0 and nb’ = nb - 1 if y = 1. Hence we have transition from the state (d’, k - 1, na’, nb’) to (d, k, na, nb) provided that parameters d’, k - 1, na’, nb’ satisfy all needed inequalities. So by basic combinatorial principles dp[d][k][na][nb] is equal to the sum of dp[d’][k - 1][na’][nb’] over all valid states (d’, k - 1, na’, nb’) from which we have a transition to (d, k, na, nb). Thus we obtain an algorithm with complexity O(L3) for finding the answer if base is equal to 2. Indeed, we find each dp[d][k][na][nb] in O(1) time as a sum of at most two previous values of dp (this is because transition is uniquely determined by x) and we have at most 2 * (L + 1) * (nA + 1) * (nB + 1) states in our dp in total. Since L <= 40 it is very fast.
Now consider the general case when base is arbitrary.
If A, B and C has different lengths then some quite careful analysis is needed. Let La be the length of A, Lb be the length of B and L be the length of C. Swapping if needed A and B we can always assume that La >= Lb .
If L < La then we simply can pad C with La - L leading zeros and set L = La.
If L > La then there is big chance that the answer is zero. It can be non-zero only in the case when L = La +1 and C starts with 1. In this case if base is equal to 2 we can simply delete this 1 from C, decrease L by 1 and set dp[0][0][0][0]=0 and dp[1][0][0][0]=1. In the general case of base after we discuss what is dp here the same trick with initialization of dp can be done.
Thus we can assume that L = La >= Lb. When base is arbitrary the state in dp will be more complicated than for base 2. Namely the state is the following triple (d, maska, maskb) where maska = (na[0], na1, …, na[X - 1]) and maskb = (nb[0], nb1, …, nb[X - 1]). Here na[j] is the number of digits j in representation of A’ and similar is for B’. Also we must have La - na = Lb - nb where na = na[0] + na 1 + … + na[X - 1] and similar for nb. All other assumptions on parameters are the same as for the case of base 2. The meaning of dp[d][maska][maskb] is similar to that for the case of base 2. The transitions between states can be obtained in similar manner. The total number of states is equal to 2 * totA * totB where totA = (nA[0] + 1) * (nA 1 + 1) * … * (nA[X - 1] + 1) and similar is for totB. Under assumptions of the problem this number does not exceed 1296. We can code maska as a number of length X in positional numerical system where each digit has its own bounds, namely jth digit is from 0 to nA[j]. Then dp[d][maska][maskb] can be stored in usual three-dimensional array.
Thus we have obtained an algorithm which is fast enough now.
SETTER’S SOLUTION
Can be found here.
Problem Setter’s alternate solution.
TESTER’S SOLUTION
Can be found here.