Please help me with this
Give n ropes, each rope in length a[i] (n<=10^3). Then divide them into two group
- Sum1 = sum of all ropes in group 1
- Sum2 = sum of all ropes in group 2
The task asked if there is a way to divide them into two group which S1=S2`
Note : the numbers of rope in each group maybe not equal to the other
Sorry for my bad at English :(
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.04.2026 04:38:26 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by tsminh_3 (previous revision, new revision, compare).
What is the size of array a?
n<=10^3; a[i]<=10^9
sum all the elements of the array . if sum is odd print no otherwise find subset sum of sum/2 if this exist . B-)
He has mentioned a[i] <= 10^9. You cannot solve the problem.
Can you please give me the link of this question?
According to Wiki Link , this problem is NP-complete and has pseudo-polynomial (O(n*sum)) time dp solution which is feasible only when sum is small. Hence, it would be nice if you could give a link to problem so that people can verify that your description and/or constraints about the problem are accurate.
This is basically the subset sum problem, and it's NP-complete, so you can't expect to solve it in polynomial time. If values were smaller (maybe ≤ 105), you could do DP.
Please can you explain how to do a DP for a[i] < = 105 ?
At every step just update all possible sums you can reach if you added current element or if you subtracted current element. If after the last element you could have reached 0 then it is possible to split the set into 2 parts.
I still don't understand it. Would you do the updates using a map/set ? Wouldn't the total possible sums for a[i] < = 105, n < = 103 be 108 and storing them in a map would cause the program to exceed memory limit for sure.
Yes, I mean the total sum of elements ≤ 105...
For i elements the total possible sums can be i * (i + 1) / 2 if the array is of numbers sequentially like 1,2,3.. and so on so it would atleast get a TLE as time taken could be
and this is not even the worst case.
Let A be the array and DP[i][j] the DP matrix. DP[i][j] is true if it is possible to have a sum of j by taking some elements from the first i elements.
At every state, you can either add the next element or not, so from a valid state DP[i][j] we can get either to DP[i + 1][j] (do not take the next element) or to DP[i + 1][j + Ai + 1] (take the next element).
If S is the sum of all elements and
is true, then you can divide the array into two parts with equal sum.
Sorry.. Didn't read your comment above.