Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

nmnsharma007's blog

By nmnsharma007, history, 5 weeks ago, In English,

I need help in this question. I read the editorial but couldn't understand it. Please explain the logic applied in this question. Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Count the number of '1's in the binary representation of x. If you put 1 bacteria on day 1, it becomes 2 on day 2, 4 on day 3. So, the best case is just the binary representation of x, where if there is a '1', you should add a bacteria on that day.

5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

If you put one bac into the box it will be two the next day, then 4 and so on. Your have to find a way to make the number equals to a given $$$n$$$, but minimize the number of bacteria you put manually into the box.

It turns out that such grow can be nicely visualized by binary numbers. Putting one bacteria into the box makes $$$10_2$$$ bac the next day, $$$100_2$$$ the day after... and so on. If you put another bac into the box on fourth day, you will get $$$1001_2$$$ bacteria, then the next day $$$10010_2$$$ etc.

So, to find the minimum number of bacs you have to put into the box count the $$$1$$$ in the binary representation of $$$n$$$.

5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Count the number of 1's in bits. If you will ask me why, I would tell you that as Binary is the representation of power of 2. like 1,2,4,8,16,32 .......... This pattern is similar to the bacterial increment day per day. lets take example of 12. Its binary representation is 1100. Guess where the 1s are? At 3rd and 4th place from left, which are used for 4 and 8.

8 4 2 1
1 1 0 0

to simplify it, I will again tell you when you put one bacteria into the box, such that it becomes 8 bacteria on 'xth' day. Then, you should put another bacteria such that it will become on 4 on that 'xth' day. Here we are only into the minimum number of days which can be calculated optimally if you will count the bits whose value is 1.