Zadanie Czwórki

Odpowiedz Nowy wątek
2017-04-20 17:32
0

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ź.

Pozostało 580 znaków

2017-04-20 18:07
0

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/[...]s-array-whose-sum-equal-zero/

edytowany 3x, ostatnio: nalik, 2017-04-20 18:46

Pozostało 580 znaków

2017-04-21 13:28
0

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

Pozostało 580 znaków

2017-04-21 13:31
0
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.

edytowany 2x, ostatnio: nalik, 2017-04-21 13:32

Pozostało 580 znaków

2017-04-21 13:36
0

dzieki za pomoc

Pozostało 580 znaków

2017-04-21 14:01
0

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)
edytowany 5x, ostatnio: nalik, 2017-04-21 22:20

Pozostało 580 znaków

2017-04-21 14:27
0

Czekaj to ty trzy pętle odpalasz ?

Nie. To zapis zależnosci. Dwie powinny wystarczyć. Znaczy można powiedzieć, że trzy, ale pierwsza dla i ma raptem trzy obiegi. Można też zamaist tworzyć wiekie tablice SumCnt skopresować to przy pomocy map (odrzucając sumy które są większe niż maksymalna liczba). - nalik 2017-04-21 14:32
Ile x, k spałnia zależność. To można robić w locie. Lecisz przez k z poprzedniej tablicy i sprawdzasz ile mamy takich x w zbiorze ze zaleznosc bedzie spelniona. To sprowadza sie do sprawdzenia czy istnieje w zbiorze taki x == j -SumCnt[i-1][k] - nalik 2017-04-21 14:40
trochę pokrętnie napisane wiec SumCnt[i][j] dodaje poprzedni pomnożony o ilość spełniające ten Count( SumCnt[i-1][k] + x == j) warunek?? Dobrze zrozumiałem - jedrzejd 2017-04-21 14:46
Tak. Chyba, że się rypnąłem :). Bo jeżeli na c sposobów da sie wybrać konkretną dwuelementową sumę, to dla trzyelementowej sumy (dwuelementowej powiększonej o x) musi się dać to zrobić na c * (ilość takich samych x) - nalik 2017-04-21 14:48
for each k, x iteruje po czym ? - jedrzejd 2017-04-21 14:56

Pozostało 580 znaków

2017-04-21 15:01
Chory Programista
0

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()
I jakim twoim zdaniem to będzie miało złożoność? :) Dokładnie O(n**4). Mistrzu. - nalik 2017-04-21 15:07

Pozostało 580 znaków

2017-04-21 15:08
0
vector<int> v
do {
 
}while(next_permutation(v.begin(),v.end()));

Takie coś ?

edytowany 4x, ostatnio: jedrzejd, 2017-04-21 15:09

Pozostało 580 znaków

2017-04-21 15:17
Chory Programista
0
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

Pozostało 580 znaków

2017-04-21 23:07
0

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.

edytowany 2x, ostatnio: nalik, 2017-04-21 23:17
500000 bi nie ma takiej liczby w tablicy? - jedrzejd 2017-04-22 08:24
Ale Ciebie interesują tylko te mniejsze od 500 000. - nalik 2017-04-22 08:25
Bo a + b + c = w <= 500 000 -> a + b = w - c <= 500 000, bo a,b,c,w są dodatnie zawsze. Wyniki większe odrzucasz bo nie mają szans spełnić równości. - nalik 2017-04-22 08:26

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0