Zadanie Czwórki

Witam!
Zacząłem robić zadanie http://ki.staszic.waw.pl/task.php?name=czworki
Jednak mój algorytm nie daję AC. Myślę jak to poprawić i nic nie mogę wymyślić.
Da ktoś punkt zaczepienia lub pomysł do tego zadania?
Z góry dziękuję za odpowiedź.

Bo pewnie zrobiłeś poczwórną pętlę, a to brzmi jak zadanie na programowanie dynamiczne albo sortowanie.

Może to pomoże:
https://en.wikipedia.org/wiki/3SUM
http://www.programcreek.com/2013/02/leetcode-4sum-java/
http://www.geeksforgeeks.org/find-triplets-array-whose-sum-equal-zero/

Te twoje linki zaczepiają się o temat , ale chyba nie do końca.

jedrzejd napisał(a):

Te twoje linki zaczepiają się o temat , ale chyba nie do końca.

O matko, Ty chcesz pod nos gotowe rozwiązanie zamiast samemu pomyśleć ... W ten sposób niczego się nie nauczysz.

dzieki za pomoc

Możesz spróbować ugryźć to dynamicznie. Te liczby są małe, do 500000. Trzeba by wykorzystać zależność

SumCnt[i][j] := Sum (SumCnt[i-1][k] * Count( k + x == j ) for each k, x)

gdzie:

• i to ilość elementów sumy
• j, k to kolejne możliwe sumy
• x to elementy zbioru
• x mozna wybierać bisekcją z posortowanej tablicy (albo idąc na łatwiznę, sprawdzać czy istnieją w std::set)

Czekaj to ty trzy pętle odpalasz ?

W pythonie jest obiekt, który generuje wszystkie kombinacje, itertools.product()
w c++ powinno być coś podobnego, a działanie miej wiecej takie chyba wszystko jest dobrze i to jest raczej łatwe zadanie, a niżeli trudne, poziom gimnazjum.

import itertools as it

def checkEqual(value):
	amount = 0
	result = False
	size = len(value)
	equal = value[size-1]
	for i in xrange(0, size-1):
		amount += value[i]

	if(amount == equal):
		result = True

	return result

def main():
	value = map(int, raw_input("Enter a numbers: ").split())
	next_perm = it.product(value, repeat=4)
	for i in next_perm:
		if(checkEqual(i)):
			print "{0}+{1}+{2}=={3}".format(i[0], i[1], i[2], i[3])
	

if __name__ == "__main__":
	main()

vector<int> v
do {



}while(next_permutation(v.begin(),v.end()));

Takie coś ?

nalik napisał(a):

I jakim twoim zdaniem to będzie miało złożoność? :) Dokładnie O(n**4). Mistrzu.

W sumie, to metoda brute force, jak dobrze zauważyłeś :D

No niestety. Rozwiązanie dynamiczne przechodzi na 70/100 pkt.

Można zadanie jeszcze bardziej uprościć, jeżeli przepisze się z a + b + c = w na a + b = w - c. Wszytkie a + b <= 500000 i 0 <= w-c <= 500000 da się policzyć w O(n^2). Pozostaje tylko sprawdzić ile z nich spełnia równość. I to już przechodzi na 100/100pkt.