sarvesh_bawari's blog

What is wrong in my CODE. Help ?
By sarvesh_bawari, history, 4 months ago, In English

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

  • Vote: I like it
  • -26
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sarvesh_bawari (previous revision, new revision, compare).

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

5 3
2 2 2 2 2

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.

→ Reply