Can someone please explain how to solve this problem.

https://csacademy.com/contest/round-79/task/smallest-subsets/statement/

Thanks in Advance!

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

1 | tourist | 3509 |

2 | OO0OOO00O0OOO0O0…O | 3327 |

3 | Syloviaely | 3274 |

4 | Um_nik | 3237 |

5 | Petr | 3161 |

6 | fjzzq2002 | 3137 |

7 | LHiC | 3135 |

8 | Benq | 3130 |

9 | ko_osaga | 3115 |

10 | Swistakk | 3089 |

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

1 | Radewoosh | 185 |

2 | rng_58 | 161 |

3 | tourist | 158 |

4 | Petr | 152 |

5 | Swistakk | 150 |

5 | Vovuh | 150 |

7 | Um_nik | 148 |

8 | PikMike | 147 |

9 | csacademy | 146 |

10 | Errichto | 145 |

Can someone please explain how to solve this problem.

https://csacademy.com/contest/round-79/task/smallest-subsets/statement/

Thanks in Advance!

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/25/2018 09:10:07 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|

Let's assume that all elements are non-negative.

Let's binary search for the value of the largest (sum) subset. Denote the current value to be checked

p. How do we check if there exist at leastksubsets of sum less than or equal top?The trick is to modify the usual recursive subset generating method:

This way every time you recurse in, you are guaranteed with a satisfying subset and you stop once you generate enough k subsets or you can't generate any more from the current branch.

What if we have negative elements though? Fortunately there is an easy fix. Initialize currentSum = sum of all negative elements, then treat all elements as non-negative. Convince yourself why this is correct.

Hello!

Thanks for your response! sir, your solution is helpful. I was unaware that this can also be done using binary search.

I too found a solution and would like to share it. It was too get the minimum sum from the given array, which will be sum of all negatives or zero(if no negative element in the array). This will be the sum of smallest sum subset.

Then, after getting this sum we may consider all elements of the array to be positive and sort the array.

Now, we can use a priority queue(or set) and insert the minimum sum in it. And, then on each iteration(from 0 to k), we pick the smallest element from the priority queue and remove it, let it be (x), and inplace of it add (x + a[itr+1]) and (x + a[itr+1] — a[itr]) in the priority queue. Where (itr) is the rightmost element chosen from the sorted array.

Now, in all k iterations the smallest elements picked from the priority queue will give us the k subsets in increasing order of their sum.

This works as in each iteration we choose one element and remove the previously taken. So, it will form all the subsets possible. And, due to the ordering of the array and the smallest sum subset chosen in each iteration, the subsets formed are in increasing order of sum.

The image shows how all subsets are evaluated, for 4 elements.