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

×

COOKMACH - Editorial

4
2

PROBLEM LINK:

Contest
Practice

Author: Maksym Bevza
Tester: Hiroto Sekido
Editorialist: Kevin Atienza

DIFFICULTY:

Cakewalk

PREREQUISITES:

Ad hoc, bitwise operators

PROBLEM:

You need to convert an integer $A$ to integer $B$, where both are positive and $B$ is a power of two. The allowed moves are the following (if the current number is $v$):

  • If $v$ is even, replace it with $v/2$; if $v$ is odd, replace it with $(v-1)/2$.
  • Replace $v$ with $2v$.

What is the minimum number of moves to do this? (it can be shown that this is always possible!)

QUICK EXPLANATION:

The fastest way is the following:

  • Use the first step repeatedly until the number becomes a power of two.
  • If the current number is larger than $B$, use the first step even further until the number becomes $B$. Otherwise, use the second step repeatedly until the number becomes $B$.

The number of steps this takes is the answer.

EXPLANATION:

We will make use of the fact that the target integer, $B$, is a power of two. First, let's notice what the operations really do.

The first operation roughly "halves" $v$, and the second operation doubles $v$. Thus, it makes sense to consider the binary representation of $v$.

In fact, the operations are simply the Bitwise logical shift operations! In other words, the first operation is simply a single right shift, and the second operation is a single left shift.

A shift is simply an operation that "shifts" the binary representation of a number. For example, shifting the binary integer "1001101" left once results in "10011010". Note that we use a "0" for new digit places. Also, when shifting right, the rightmost digit is discarded: for example, the right shift of "1001101" and "1001100" are both "100110". It's fairly straightforward to see why the operations described in the problem statement are simply shifts.

With this in mind, how do we quickly go from $A$ to $B$? Since $B$ is a power of two, it has exactly one $1$ in its binary representation. Notice that using either operation doesn't increase the number of $1$s in the binary representation of a number. Therefore, the first action we must do is to convert the initial number into one that contains a single $1$ in its binary representation (i.e. a power of two). To do this, we shift right, until it becomes a power of two.

Now that our number is already a power of two, we can simply shift left or right repeatedly until it becomes equal to $B$!

The answer is simply the total number of shifts in both steps combined, and it's quite easy and intuitive to see why this is the optimal solution.

The following is an implementation in C++:

#include <stdio.h>
#include <stdlib.h>

int main() {
    int z;
    scanf("%d", &z);
    while (z--) {
        int a, b;
        scanf("%d%d", &a, &b);
        int steps = 0;
        while ((a & -a) != a) a >>= 1, steps++;
        while (a < b) a <<= 1, steps++;
        while (a > b) a >>= 1, steps++;
        printf("%d\n", steps);
    }
}

A somewhat faster solution

We can use a few more bitwise tricks to compute the answer without performing the steps themselves. Notice that there are two parts in calculating the answer:

  • Use the first step repeatedly until the number becomes a power of two.
  • If the current number is larger than $B$, use the first step even further until the number becomes $B$. Otherwise, use the second step repeatedly until the number becomes $B$.

How can we calculate the number of steps required in part one? Note that the answer is simply one more than the position from the right of the second most significant bit of $A$, or zero if there isn't such a bit (i.e. $A$ is a power of two already). We can compute this value quickly if we can perform the following operation quickly:

  • Extract the position of the second largest bit of a number

It can be dissected into a series of the following operations:

  • Extract the largest bit of a number.
  • Remove a particular bit of a number.
  • Get the place value of a particular bit, i.e. given $v = 2^i$, compute $i$.

Removing a particular bit is easy; the number A with the bit b removed is simply A ^ b, where ^ is the bitwise XOR operator. (This expression assumes that b is found in A. If you can't guarantee it, use the expression A ^ ~b instead, where ~ is the bitwise NOT operator) The first operation ("extract the largest bit") can be done with the following pseudocode which works for 32-bit integers (we invite the reader to see why this works):

int maxbit(int v) {
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    return v ^ (v >> 1);
}

Now, how do we implement the last one? Given $v = 2^i$, we want to compute $i$. Note that $i$ is simply the number of $1$ bits in the number $v-1$! But how do we count the $1$ bits in a given number? It can be done with the following pseudocode (once again, we invite the reader to see why this works):

int bitcount(int v) {
    v = (v & 0x55555555) + ((v >>  1) & 0x55555555);
    v = (v & 0x33333333) + ((v >>  2) & 0x33333333);
    v = (v & 0x0f0f0f0f) + ((v >>  4) & 0x0f0f0f0f);
    v = (v & 0x00ff00ff) + ((v >>  8) & 0x00ff00ff);
    v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
    return v;
}

With these, we can now extract the position of the second largest bit of a number:

int extractsecond(int v) {
    v ^= maxbit(v);
    if (v == 0) {
        // v was originally a power of two
        return 0;
    } else {
        return bitcount(maxbit(v) - 1) + 1;
    }
}

Now, for the second part: assuming the current number $A$ is a power of two, how many steps do we need to convert it to $B$? This is very simple: it's just the difference between the positions of the bits of $A$ and $B$, i.e. abs(bitcount(A-1) - bitcount(B-1))! Therefore, we now have the following (somewhat faster) solution:

#include <stdio.h>
#include <stdlib.h>
#define ll long long

int maxbit(int v) {
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    return v ^ (v >> 1);
}

int bitcount(int v) {
    v = (v & 0x55555555) + ((v >>  1) & 0x55555555);
    v = (v & 0x33333333) + ((v >>  2) & 0x33333333);
    v = (v & 0x0f0f0f0f) + ((v >>  4) & 0x0f0f0f0f);
    v = (v & 0x00ff00ff) + ((v >>  8) & 0x00ff00ff);
    v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
    return v;
}

int extractsecond(int v) {
    v ^= maxbit(v);
    if (v == 0) {
        // v was originally a power of two
        return 0;
    } else {
        return bitcount(maxbit(v) - 1) + 1;
    }
}

int main() {
    int z;
    scanf("%d", &z);
    while (z--) {
        int a, b;
        scanf("%d%d", &a, &b);
        int steps = extractsecond(a);
        a >>= steps;
        steps += abs(bitcount(a - 1) - bitcount(b - 1));
        printf("%d\n", steps);
    }
}

Time Complexity:

$O(\log A + \log B)$ or $O(\log \log A + \log \log B)$

AUTHOR'S AND TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 16 Aug '15, 13:06

kevinsogo's gravatar image

7★kevinsogo
1.7k479138
accept rate: 11%

edited 15 Jan '16, 18:00

admin's gravatar image

0★admin ♦♦
18.2k347492525


Check out the shortest solution to this problem:
https://www.codechef.com/viewsolution/7736218

link

answered 20 Aug '15, 23:15

harshgupta11's gravatar image

2★harshgupta11
362
accept rate: 12%

why not editorialist ,tester, author provide such short and easy code for editorial which easy to understand as well as good to see??

thanks to harshgupta11 sharing this solution

(25 Aug '15, 14:59) rcsldav20175★

I have understood the solution but still when a question comes on the screen Bitwise is the last option that comes to my mind. So here is what I tried :: get_i() is an input method, the algorithm goes the same way as the editorial suggests, what I guess is my if condition is wrong. I am trying to check whether the number whose log I am calculating is returning me a positive integer or not.

      int main( int argc, char *argv[]) 
      {
          int test = get_i();
          while(test--)
          {
              long int count = 0;
              long int a = get_i();
              long int b = get_i();
              long int x = 0;
              while(a!=b)
              {
                if(a==1)
                  break;

                if(a%2==0)
                {
                  if ((long int)(ceil((log10(a)/log10(2))))==(long int)(floor((log10(a)/log10(2)))))
                    break;
                  count++;
                  a /= 2;
                  continue;
                }

                else if(a%2==1)
                {
                  count++;
                  a = (a-1)/2;
                }

              }
              if (b>=a)
                x = log10(b/a)/log10(2);

              if(a>b)
                x = log10(a/b)/log10(2);

              printf("%ld\n",count+x );
          }

          return 0;
      }

I tried my level best to get to the answer and I failed so many times that I decided to go for "precompilation" as I was so desperate to get those 40 points. I am really ashamed of myself but even this method didn't work.

             static int array[] = {1,2,4,8,16,32,64,128};
     int main(int argc, char *argv[]) 
        {
            int test = get_i();
            while(test--)
            {
                int count = 0;
                int a = get_i();
                int b = get_i();
                int x = 0;
                if(a==b)
                {
                    printf("0 \n");
                    continue;
                }

                while(a!=1)
                {
                  if(a%2==0)
                  {
                    if(search(a))
                    {
                      if(b>a)
                        x = (int)(log10(b/a)/log10(2));
                      else
                        x = (int)(log10(a/b)/log10(2));

                      break;
                    }
                    else
                    {
                      count++;
                      a/=2;
                      continue;
                    }  
                  }
                  else if(a%2!=0)
                  {
                    count++;
                    a=(a-1)/2;
                  }
                }
                if(a==1)
                  x=(int)(log10(b)/log10(2));
                printf("%d\n",x+count);

            }

            return 0;
        }
        int search(int x)
        {
          int i = 0;
          while(i<=8)
          {
            if(array[i]==x)
              return 1;
            else
              i++;
          }
        }

I want to know that why my first method failed (the test case) and some suggestions as how to avoid such mistakes in future. I would also like to know , what was wrong in my second method.

link

answered 18 Aug '15, 19:50

durwasa_jec's gravatar image

2★durwasa_jec
312
accept rate: 0%

Brother nothing was wrong, I also checked log(a) is an integer or not to check it is a power of 2 or not. I also used the same but got WA.

Then it came to my mind that if a AND (a-1) == a then it is a power of 2.

Use this method.

I was also feeling ashamed as nothing was wrong in the code. But it happens. Dont worry about it and keep coding and practising. :)

(18 Aug '15, 20:00) bradley4★

@durwasa_jec, nothing was wrong in your approach.

Just some basic error which gave WA. These should be kept in mind always. There is always some precision error in C, especially with large values. The log function you use many a times return answer such as 12.999999999 etc. instead of 13. This happens many a times. A typically example illustrating this is given in the following code, http://ideone.com/3j3OmD. Since only integer part of the the logarithm was required, it can be calculated using while loop. I think the error was with the ceil and floor comparison. Try removing that. Also, instead of using log(b/a) and log(a/b), Use log(a)-log(b) and vice- versa.

I personally suggest you to use double instead of floats whenever required. If possible avoid them. Sometimes it passes, sometimes it may give an error on some corner cases.

Here is the link to my solution https://www.codechef.com/viewsolution/7642483 (python code), https://www.codechef.com/viewsolution/7637949 (c++ code).

Hope it helps :).

link

answered 18 Aug '15, 23:28

likecs's gravatar image

6★likecs
3.2k947
accept rate: 10%

why not Editorialist ,Tester, Author provide such short and easy code for editorial which easy to understand as well as good to see??

thanks to @harshgupta11 sharing this solution

HAPPY CODING

link

answered 25 Aug '15, 15:01

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

here is very easy implementation https://www.codechef.com/viewsolution/7890452 less then 25 lines easy to understand thanks:)

link

answered 25 Aug '15, 15:47

ankit777's gravatar image

1★ankit777
4919
accept rate: 12%

link

answered 11 Sep '16, 09:50

mr_nair's gravatar image

1★mr_nair
11
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:

×13,349
×1,270
×818
×185
×76

question asked: 16 Aug '15, 13:06

question was seen: 5,154 times

last updated: 11 Sep '16, 09:50