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.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.04.2026 06:07:50 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
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.
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
Sorry for necroposting, but here's my solution:
Consider an element $$$e$$$ with count $$$x$$$. Insert values $$$e, 2\cdot e, 4\cdot e, ... $$$ etc, with weight (the number of element inserted) as $$$1, 2, 4, ...$$$ while it's still doable ($$$2^k \leq x$$$). Insert $$$x\cdot e$$$ after that (if $$$x \gt 0$$$) the same way. By the sqrt-log theorem for knapsack problems ($$$\sum{\log(x)} \in O(\sqrt{\sum{a_i}})$$$), we got the total TC to be $$$O(K \sqrt{\sum{a_i}})$$$.
Or can't we do fft here? Binary search on no of boxes. Complexity will be $$$O(N*logN*log(max a_i))$$$
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 K with sum S. The link only talks about subsets with sum S which is quite a standard problem.