An array of size N is given and a value K. You have to find the minimum subset size so that subset sum is exactly equal to K, if not print -1. 0 < K, a[i], N < 10^6.

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

1 | tourist | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

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

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 182 |

5 | awoo | 180 |

6 | tourist | 176 |

6 | sus | 176 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 170 |

10 | -is-this-fft- | 169 |

An array of size N is given and a value K. You have to find the minimum subset size so that subset sum is exactly equal to K, if not print -1. 0 < K, a[i], N < 10^6.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2021 07:16:11 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Isn't this the famous coin change problem? You can easily find the solution online.

Sorry, can you explain how?

In problem which mentioned in post constraints for $$$N, K, a_i$$$ to high for stupid knapsack.

Other solution with sqrt opt works $$$O(n * log(max(a_i)) * sqrt(K))$$$, thats too much.

This problem came in Colortoken placement exam. Can you please tell me how can it be solved?

Can you say the time limit, and you sure that constraint is 10^6?

![ ]()

The sample output were: 2 and -1

Are you sure that they ask about finding subset?You tried submit solution for subsegment?

I think so too. Since the output for the second case is -1 they are probably asking for a subsegment (even if that is not clear in the statement). This could be solved in O(n) by using two pointers as well, which explains the constraints.

I did not clicked the photos of the question but I tried to find it in telegram. This much I have found.![ ]()

nice statement awesome task

Could you elaborate on this sqrt optmization (or provide links)? Depending on what it is maybe the solution is using it with bitset

Or can't we do fft here? Binary search on no of boxes. Complexity will be $$$O(N*logN*log(max a_i))$$$

binary search will not work here.

How do you check that you can collect this amount or not by FFT with fixed amount of items?

I mean Like we do "Fast subset transform" in a similar way if possible lets say $$$s$$$ will be the smallest size of some subset such that it's sum is $$$K$$$. then polynomial raise to power $$$s$$$ will contains non-zero coefficient for $$$x^K$$$ term right.

I encountered a similar problem recently, can someone suggest some solution:

Given an array A of size N, find the number of subsets of size exactly K that add up to S.

e.g:

explanation (0 based indexing)

I don't remember the constraints, but let's say 1 <= N,S <= 1000

and would it really be possible to solve under normal time-limits i.e. 1 or 2 sec if N,S were 10^5?

I dont know anything better than $$$O(NS)$$$. You can submit it here https://www.geeksforgeeks.org/count-of-subsets-with-sum-equal-to-x/

you missed out on the point

Subsets of length exactly Kwith sum S. The link only talks about subsets with sum S which is quite a standard problem.Yeah sorry thats a different problem I had posted. $$$O(NKS)$$$ DP is trivial for your problem. I dont have anything better.