My code is giving wrong answer on hidden test case.

Problem https://mirror.codeforces.com/edu/course/2/lesson/6/2/practice/contest/283932/problem/G My code: Code

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

1 | tourist | 4009 |

2 | jiangly | 3839 |

3 | Radewoosh | 3646 |

4 | jqdai0815 | 3620 |

4 | Benq | 3620 |

6 | orzdevinwang | 3612 |

7 | Geothermal | 3569 |

8 | ecnerwala | 3494 |

9 | Um_nik | 3396 |

10 | gamegame | 3386 |

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

1 | Um_nik | 164 |

2 | -is-this-fft- | 160 |

2 | maomao90 | 160 |

4 | atcoder_official | 158 |

4 | cry | 158 |

4 | awoo | 158 |

7 | adamant | 155 |

8 | nor | 154 |

9 | TheScrasse | 153 |

10 | Dominater069 | 152 |

My code is giving wrong answer on hidden test case.

Problem https://mirror.codeforces.com/edu/course/2/lesson/6/2/practice/contest/283932/problem/G My code: Code

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/04/2024 05:36:44 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Understand carefully what you are actually doing in your code. You are running a binary search for finding $$$\left\lfloor \frac{sum}{k} \right\rfloor$$$, which could as you can see, have been easily calculated in constant time. This is obviously a wrong solution to the problem, for example in a test case like $$$k = 3$$$ and an array like $$$[1, 1, 4]$$$, your code will return 2, but the answer is 1.

Observe that the problem reduces to this: You have an array, in one operation pick exactly $$$k$$$ non zero elements and reduce them each by one, and increasing the number of councils by one. We need to optimally pick the elements in such a way that maximises the number of operations/councils.

It is important to understand why summing and dividing by k is wrong. It is obviously because a few large elements may contribute too much to the sum, while in reality after a while, only a few large elements (count of those large elements < k) will remain, and we will no longer be able to pick new councils.

However, if we know that in our $$$sum_x$$$, the involved elements are all $$$\leq$$$ some value $$$x$$$ and additionally the net sum, $$${sum_x} \geq x \times k$$$ , then we can be sure that we can always form $$$x$$$ councils. Also, if we can build $$$x$$$ councils, we do so by picking at most $$$x$$$ from each element in the total of our $$$x$$$ operations and $$$sum_x \geq x \times k$$$ (bijective condition). This $$$x$$$ is also monotonous. If we cant make $$$x$$$, we cant make $$$x + 1$$$. This is the idea behind the binary search. To solve this, you can do binary search on the value $$$x$$$. As for checking we take $$$sum_x$$$ as the sum of min of $$$x$$$ and each element, limiting the maximum element used in each $$$sum_x$$$.

However, I did this problem using a greedy algorithm, you can check it out once you solve it using binary search first.

Thankyou