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 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 18:25:39 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
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.