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