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

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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3567 |

3 | Um_nik | 3527 |

4 | ecnerwala | 3458 |

5 | maroonrk | 3409 |

6 | 300iq | 3317 |

7 | Petr | 3272 |

8 | LHiC | 3229 |

9 | Benq | 3226 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 198 |

2 | antontrygubO_o | 188 |

3 | pikmike | 183 |

4 | Ashishgup | 182 |

5 | vovuh | 179 |

6 | Radewoosh | 167 |

7 | Um_nik | 164 |

8 | tourist | 163 |

9 | McDic | 162 |

10 | Monogon | 159 |

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/04/2020 03:36:15 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

Thanks;

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$$$.

Thanks for the detailed explanation;

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.

Understood.Thanks a lot