Since the requirements became stronger, and time was reduced from 2 sec down to 1 sec, now it is not possible to resolve the task using bruteforce method, python is very slow for such hard requirements.
Even I do empty loops the taken time is already about 1.3 sec.
from time import time time_before = time()
len_lst = 20
for i in range(1, ((2 ** len_lst) // 2) - 1):
for j in range(len_lst):
print(time() - time_before)
I think for Python the time should be rolled back to 2 sec. Of cause if I use bruteforce on "C" it takes about 0.2 sec, but Python is not "C".
Hi there! Here is my code for this task: https://notabug.org/thrashzone_ua/c_examples/src/master/rock_heap.c
Short notes: 1) Cases when there is one or two rocks from input are separated 2) In case amount of rocks is more then 2, I'm checking if there is a sublist in list of rocks with sum(sublist) = sum(list) / 2. If there is such a sublist and the number of sum is even - 0 will be printed, if number is not even - 1; 3) In case there no such sublist - it's time for greedy algorithm.
Could you please take a look and comment my code? Or maybe provide with test set, on which it will fail?
My Python program solved this problem using 0.7+ seconds and 64000+KB memory. However, I saw some people solved it with Python using just about 0.1 secs and 500KB mem. Can anyone give me a hint about how to reach that efficiency?
1) Why do you initialize min as 99? Weights can be up to 10^5. 2) This problem can't be solved so easily. It requires to examine all options (2^n in total). You can use recursive function, for example.
Как можно оптимизировать или перебором в лоб будет быстрее? __________________________________________________________
# Считываем данные N = int(input()) weight = list(map(int, input().split(' ')))
''' Задача разбиения множества чисел Псевдополиномиальный алгоритм https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D1%80%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D1%87%D0%B8%D1%81%D0%B5%D0%BB ''' # Создаем массив P S =  + weight K = sum(S) X = K//2+1 Y = len(S)+1 P = 
for i in range(X): P.append() for j in range(Y): if i == 0: P[i].append(1) else: P[i].append(0)
for i in range(1, X): for j in range(1, Y): if (i - S[j-1]) >= 0: P[i][j] = (P[i][j-1] or P[i - S[j-1]][j-1]) else: P[i][j] = (P[i][j-1])
for i in range(X-1, -1, -1): if 1 in P[i]: print(K - 2*i) break
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