You are not logged in. Please login at www.codechef.com to post your questions!

×

BINSHFFL - Editorial

2
1

Problem Link

Practice

Contest

Author: Noszály Áron

Tester: Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

EASY

Prerequisites

BFS/Floyd Warshall, Observations

Problem

You are to convert number $A$ to number $B$ using the following operation in the minimum number of steps:

  • Write A as a binary number with arbitrary number of leading zeros (possibly none)
  • Shuffle the binary digits of the A in an arbitrary order. Call it $A'$
  • The output is $(A' + 1)$. Let us call this number as $X$.

Remember the notation of $A'$ and $X$ as it is used everywhere in the editorial.

Explanation

Subtask 1: A, B ≤ 128

The 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 $(B-1)$ 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-

  1. Find the number of ones in the binary representation of $A$ and $(B - 1)$. Let us denote then by $OA$ and $OB$
  2. If $OA > OB$, then we can achieve the operation in $2$ steps. First decreasing the number of ones in the first step and then rearranging the digits in another step.
  3. If $OA <= OB$, then we need $(OB - OA)$ steps to first make the number of ones equal (see decrease operation takes place at one step each). Finally, we can arrange the digits to achieve the desired number.

The only corner case is as follows:

  1. If $B$ is $0$ then, we can't achieve the desired state whatever the value of $A$ is. Since we are adding $1$ in the last step we are guaranteed to have atleast one binary digit $1$ in binary representation. Thus the answer for this case is $-1$.
  2. If $B$ is $1$ then, we can achieve the desired state only if $A = 0$, in one step. In another case, it is impossible as even though decreasing the number of binary digit $1$, the end result would be a number greater than $1$. So the answer is $1$ if $A = 0$, else $-1$.

The number of ones in binary representation can be calculated using the below pseudo-code:


    def count_ones(integer x):
        ones = 0
        while x > 0:
            if x % 2 == 1:
                ones += 1
            x /= 2
        return ones

The time complexity of the above pseudo-code 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, 01:23

likecs's gravatar image

6★likecs
3.4k1356
accept rate: 9%

edited 17 Jun, 14:23


12next »

Here : https://www.codechef.com/viewsolution/18719196

Is a commented solution of this problem till soln gets linked..

I am in div1 though had written one for discuss :D
Feel free to ask queries..
PS: The code is simple enough to understand and it ll help....

link

answered 11 Jun, 17:17

l_returns's gravatar image

3★l_returns
77018
accept rate: 27%

1

Great one !!!

(13 Jun, 08:47) umangahuja12★

Thanks :) .

(13 Jun, 12:30) l_returns3★

Thanks for upvoting guys.. specially @iamjoker I got 10 from u at last and now I can edit wiki questions... :)

(15 Jun, 18:35) l_returns3★

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.

link

answered 11 Jun, 20:12

yash_ja's gravatar image

3★yash_ja
111
accept rate: 0%

I have a doubt, with regard to the editorial. Can you please explain me the case of getting output as 2 when A = 15 and B = 8. As per editorial output should be 2. As from editorial, OA = 4 and OB = (ones in B-1) = 3. So how to get 3 ones from 4 ones in 2 steps?

link

answered 11 Jun, 23:57

mohit_raj1994's gravatar image

1★mohit_raj1994
112
accept rate: 0%

edited 11 Jun, 23:59

With respect to the editorial, kindly explain me the case when A = 15 and B = 8. So, OA = (15 = 1111) = 4 and OB = (8-1 = 0111) = 3. How to get from OA to OB in 2 steps, since output is 2 ?

link

answered 12 Jun, 00:04

mohit_raj1994's gravatar image

1★mohit_raj1994
112
accept rate: 0%

edited 12 Jun, 00:04

Hello! I understand this editorial but can someone help me through this example. Let us say I got A =9 (1001) and B =16 (10000) So B-1=1111 in binary and the steps are.

1001 Becomes 1100 (reshuffled) ,add one to get 1101,this was Step 1. Next reshuffle this to get 1110,and then add 1,you get 1111,and this was step 2.

but this is B-1 but not B and I have completed OB-OA steps!?

link

answered 12 Jun, 00:47

mr_jt's gravatar image

2★mr_jt
0
accept rate: 0%

yeah true.. you need $OB-OA+1$ steps
to get B from A when
$ Cnt(A)<=Cnt(B-1)$

(12 Jun, 00:56) l_returns3★

look at my solution it has AC... I printed $OB-OA+1$

(12 Jun, 00:56) l_returns3★

and that is what editorialist meant to say...

(12 Jun, 00:58) l_returns3★
1

Thanks Man! Appreciated!

(12 Jun, 01:20) mr_jt2★

thanks and welcome :)

(12 Jun, 01:26) l_returns3★

Can anyone tell me how to convert 127 to 52 in just 2 operations?

link

answered 12 Jun, 12:32

hardik45's gravatar image

3★hardik45
1
accept rate: 0%

can someone tell me in the first testcase A=2 and B=4 , why we can not shuffle 010 to 100 in one step??

link

answered 12 Jun, 13:46

yo_coder's gravatar image

2★yo_coder
1
accept rate: 0%

You have to add $1$ as well in last step.

(12 Jun, 14:27) vijju123 ♦5★

You can but at the end you will have to add 1, and thus the final number will be 4 + 1 = 5. Read the problem again carefully. You can do arbitrary shuffles(including 0) and arbitrary prefixing of 0s(including 0) but for each operation you must add 1.

The alternate way to think of how to solve this problem is that you must get B - 1 from A(because in the last operation you will add 1 to it, getting B - 1 + 1 = B). Now to get B - 1 from A, they must have the same number of set bits. Now how to make the set bits same? This has been explained in the editorial well. Read the editorial carefully.

(12 Jun, 14:33) sorb19974★

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

link

answered 15 Jun, 03:24

shivan111's gravatar image

2★shivan111
101
accept rate: 0%

@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, 14:20) likecs6★

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

link

answered 15 Jun, 03:24

shivan111's gravatar image

2★shivan111
101
accept rate: 0%

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

link

answered 15 Jun, 03:24

shivan111's gravatar image

2★shivan111
101
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,366
×3,155
×357
×160
×63
×19
×13

question asked: 06 Jun, 01:23

question was seen: 1,925 times

last updated: 17 Jun, 14:23