I don't know why I got TLE on test 3. I use bruteforce with Python. But in my PC, it runs so fast with n = 20

My tests (N, Array, Answer):
[8, '6 7 9 13 18 24 31 50', 0],
[5, '5 5 4 3 3', 0],
[5, '3 3 4 5 5', 0],
[1, '1', 1],
[1, '2', 2],
[6, '1 4 5 6 7 9', 0],
[5, '5 8 13 27 14', 3],
[5, '5 4 3 3 3', 0],
[5, '11 10 8 7 6', 0],
[6, '1 4 5 6 7 9', 0],
[6, '9 7 6 5 4 1', 0],
[7, '1 2 3 4 5 6 6', 1],
[3, '1 1 5', 3],
[6, '1 2 3 4 100 100', 0],
[5, '5 8 13 14 15', 1],
[5, '4 6 6 7 9', 0],
[7, '36 25 12 10 8 7 1', 1],
[6, '101 51 51 3 2 2', 0],
[6, '1 4 5 6 7 9', 0],
[4, '1 3 9 27', 14],
[6, '6 6 5 4 3 2', 0],
[20, '1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20', 0]

All tests = True.
What I do wrong?

Edited by author 17.11.2016 19:27

Edited by author 17.11.2016 20:03

Edited by author 01.07.2016 01:40

Edited by author 01.07.2016 01:40

Use the generation of the subsets

Можете обьяснить пожалуйста что я делаю не так?
Я ходил по обсуждению задачи пробывал тесты которые предлагают, результаты вроде бы как правильные.
Может я неправильно организовал ввод/вывод данных?
Работает как-то так.
Считываю в 1 строку: 6 1 4 5 6 7 9
Очищаю консоль и вывожу Console.WriteLine ответ: 0

If you want to divide the heap into 2 parts - an expression (1≤n≥20) is not true! The number "n" can not be equal to one.

After going through all the discussion topics, I found that this problem can be solved using different techniques. I have made a list of keywords, and I would like to know exactly how many different ways are there to solve this problem?

1) Brute force
2) Bit mask
3) Dynamic Programming
4) Backtracking
5) Balanced Partition
6) Partition problem
7) Greedy algorithm

input test 2 is:
1
1

Edited by author 06.02.2016 22:45

How to solve it without of using brute force? It works, but, I've heard, there is better solution.

use bitmask.
i got ac at 0.093

Hello, I've implemented two solutions: DP and Brut Force on ruby,
but still no luck to pass tests (#3, #4).
Does someone have good solution on ruby for that problem?
Is it my bad hands, or tests were changed and ruby cant process it fast.

If you have accepted solution, please try to submit it again.
Also, if you resolved it on ruby, please give some specific hints about solution.
Thanks!

Who knows what is the test 7?
I failed at this test.

[code deleted]

Edited by moderator 29.01.2022 18:45

[code deleted]

Edited by moderator 29.01.2022 19:09

не могу найти ошибку,возможно ли узнать какие числа вбивает 8-й тест?

Solve it with brute force, afaik this problem is of NP class.

The problem says "You have a number of stones with known weights W1, …, Wn. " This is unclear because you can suppose there are more stones than the n weights  (you can imagine two different stones having the same weight). And worst, in the output description, the author's problem uses letter n with two different cases (upper N for the number of stones and lower n for the numbers of weights), this gave me trouble and lets me think the problem was more complicated than it really is.

Please, use the same case for the two letters and, better, be more explicit by starting the statement problem in this way :

You have a number n of stones with known weights W1, …, Wn




Edited by author 05.05.2013 19:55

There is a DP solution for this version of knapsack problem with O(n*max(wi)) time and O(max(n, max(wi))) space. It's a beat tricky, but still not so difficult in implementation. Just use your brains wisely ;)

But an easy one is a brute-force, where we need to search between 2^n sets of piles.

P.S. To admins, how about adding a new problem "Stone Pile 2" with N<=1000, 1<=Wi<=10000 and with writing the exact piles to output :)