Problem LinkAuthor: Noszály Áron Tester: Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyEASY PrerequisitesBFS/Floyd Warshall, Observations ProblemYou are to convert number $A$ to number $B$ using the following operation in the minimum number of steps:
Remember the notation of $A'$ and $X$ as it is used everywhere in the editorial. ExplanationSubtask 1: A, B ≤ 128The problem asks to minimise the number of steps to go from $A$ to $B$. Generally, these type of problems can be easily modelled as a graph and perform BFS to find the answer. Here is a general idea: Let us model each step as an edge from initial number to final number with an edge of some cost. So, the path with the smallest weight from source to destination is the required answer and also gives us a way to achieve the transition. In this problem, we can just do what the operations ask us to do. Just all possible shuffling of the digits of A in binary representation and consider only those ones which give end result within the desired range ([0, 128]). Let us call this number as $X$. Add an edge of weight $1$ from $A$ to $X$. Build the complete graph based on all possible transitions. Make sure that this graph will be directed one as transforming from $A$ to $X$ might not be the same as transforming from $X$ to $A$ due to the last operation which adds $1$ to the result. Once, we have the directed graph, we can simply perform any all pair shortest path algorithm like BFS, Floyd Warshall (or Dynamic Programming as a graph is directed) and precalculate the answer for all possible cases. Once, the answers are precalculated, each test case can be answered in constant complexity. For more details, one can refer to the editorialist solution below. The maximum number of edges from a number $A$ emerging out will be $7! = 5040$ in the worst case, but in practice, it will be quite less. The number of vertices in the graph will be $128$. Using Floyd Warshall algorithm the precomputation can be achieved in $O(128^3)$, i.e. $O(A^3)$. This is enough to solve this subtask. Subtask 2: A, B ≤ ${10}^{18}$The constraints in this subtask are quite large and the number of test cases also suggest we need a logarithmic approach. This leads us to write $A$ and $B$ in binary representation and finding some observations to proceed with the solution. Let us first simplify the approach by trying to convert $A$ to $(B1)$ as in the end $1$ would be added as part of the last operation. We can see that in one step we can shuffle the digits of $A$ in such a manner that an extra $1$ is introduced in the binary representation of the newly formed number. This can be done by simply shuffling the digits to contain binary digit $1$ from the ${2}^{nd}$ position. For example: Let $A = 3$. In binary representation $A = 011$. We can shuffle the digits as $A' = 110$. On adding $1$, we get $X = 111$, i.e. $X = 7$. Thus, we can introduce a binary digit $1$ in one step. Also, we can decrease any number of binary digit $1$ from $A$. This can be done by easily placing the required in the number of $1$ in towards the end, followed by a $0$ and then placing the digits in any order we like. For example: Let $A = 13$, i.e. $A = 1101$ in binary representation. Say we want to decrease one binary digit $1$, we can arrange the digits as $A' = 1011$. On adding $1$, we get $X = 1100$. If we wanted to decrease two binary digit $1$, we can arrange the digits as $A' = 0111$. On adding $1$, we get $X = 1000$. Thus, we decrease any number of binary digit $1$ in one step. With the above 2 scenarios, the following is the algorithm
The only corner case is as follows:
The number of ones in binary representation can be calculated using the below pseudocode:
The time complexity of the above pseudocode will be $O(\log{x})$ as each iteration of the while loop decreases the value of $x$ by $2$. Feel free to share your approach, if it was somewhat different. Time Complexity$O(\log{A} + \log{B})$ per test case. Space Complexity$O(1)$ AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. (It will pass subtask 1 only and uses dynammic programming approach) Tester's solution can be found here. Editorialist's solution for subtask 1 can be found here. Editorialist's solution for full problem can be found here.
This question is marked "community wiki".
asked 06 Jun '18, 01:23

Here : https://www.codechef.com/viewsolution/18719196Is a commented solution of this problem till soln gets linked..I am in div1 though had written one for discuss :D answered 11 Jun '18, 17:17
1
Great one !!!
(13 Jun '18, 08:47)
Thanks :) .
(13 Jun '18, 12:30)
Thanks for upvoting guys.. specially @iamjoker I got 10 from u at last and now I can edit wiki questions... :)
(15 Jun '18, 18:35)
Why is the minimum number of steps 2 when Number of 1's in A (cnt_A) > Number of 1's in B1 (cnt_B): For example in the following testcase: A: 14, B: 12 Only one operation is required as follows  Binary A: 1110; Shuffle to make: 1011; Add 1 : 1100 which is 12 equal to B. The Algo according to editorial (including code linked by l_returns) produces 2 as output. Whereas as seen above minimum number of operations required is 1. Can anybody explain ?
(27 Jun '18, 17:46)

You can use __builtin_popcountll(num) to find the number of 1s in binary rep of num. https://www.codechef.com/viewsolution/18766756 Let me know if anyone has any query regarding the solution. answered 11 Jun '18, 20:12

Pretty straightforward solution with a slight modification. You can use the Brian Kernighan’s Algorithm for calculating set bits. It has a runtime of O(A) + O(B). counting set bits answered 15 Jun '18, 03:24
@shivan111, the logic mentioned is exactly the same as one used in fenwick trees. But your complexity analysis is wrong. it should be $O(\log{A} + \log{B})$. It is just that constant factor of the approach you mentioned is smaller.
(17 Jun '18, 14:20)

can you tell the mistake in my solution, its giving TLE. https://www.codechef.com/viewsolution/18854022. Thanks in advance! answered 16 Jun '18, 22:18
Check for infinite loops
(16 Jun '18, 22:22)
@poseidon_22, also there is an issue with the data types used by you in the solution. There will be overflow issues which can lead to unexpected behaviour in your code.
(17 Jun '18, 14:22)
