Hi, Can anybody help me to figure out how to apply binary search for the problem 231C - To Add or Not to Add.

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

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

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

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

4 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 179 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

Hi, Can anybody help me to figure out how to apply binary search for the problem 231C - To Add or Not to Add.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/07/2020 07:28:18 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Why not to read editorial?

Referring to editorial was my first destination but ,I can't clearly get the idea. So if you could help me out , it'd be great.

Well. First part — second number in answer should be a number from initial array. It's explained good enough there. So, we need to check all the numbers from array and calculate, how many operations of "+1" we need to use — the first number for our answer depends on that. That's true, as much operations we use — so much equal numbers we can obtain. Consider the following forward algo: first, we take a[i-1] and apply "+1" to it until a[i-1]==a[i], then go to a[i-2] and so on:

we apply more operations — we get more numbers. Hence, first part of answer is monotonic function, which depends on number of applied operations. And we can use binary search here. Letcntbe that number of operations... And then — last part of editorial as it is. Is it better now?clear thinking. I think lama_codes will solve it.

Thanks for the support radical! :P

my family was searching for a form a few weeks ago and was informed of an online service that has 6,000,000 forms . If others are looking for it as well , here's a http://pdf.ac/1YepwQ.