It gives wrong answer ignore the last test case.
Question link -> https://www.codechef.com/problems/DIVIDE_GROUP?tab=statement
Solution link → https://www.codechef.com/viewsolution/97381828
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
It gives wrong answer ignore the last test case.
Question link -> https://www.codechef.com/problems/DIVIDE_GROUP?tab=statement
Solution link → https://www.codechef.com/viewsolution/97381828
Name |
---|
Auto comment: topic has been updated by sarvesh_bawari (previous revision, new revision, compare).
Looking at it your method seems to be taking the lowest remaining value in the array each time (call this x), then subtracting x from the k-1 highest remaining values in the array to create x groups, repeating this process until no more groups can be created. In this case the greedy method fails in the following case:
In this case 3 groups can be made from boxes [1,2,3] , [2,3,4] , and [1,4,5]. In your current solution what is happening currently is that you take the lowest value 2, and end up creating two boxes of [1,2,5], leaving only two types of candies left. Technically this can be fixed by only making one box at a time and then resorting the array after each box, but the problem constraints (1 <= A[I] <= 10^9) would cause this to TLE. In practice the actual solution doesn't require you to explicitly determine how each group is created in the solution.
Thank you........Sir.