Wątek zablokowany 2017-04-20 13:40 przez Patryk27.

Czwórki - x+y+z=w w zbiorze S

0

Witam!

Mam do zrobienia takie zadanie: http://ki.staszic.waw.pl/task.php?name=czworki

I teraz myślę jak to rozwiązać i nic nie mogę wymyślić. Jedyne co mi sie udało to to, żeby zrobić kilka pętl i tak jakoś jechać. Ale to ort! jest zbyt wolne rozwiązanie. Ma ktoś jakiś POMYSŁ jak to zrobić? Może jest jakiś do tego specjalny algorytm?

Proszę o pomoc.

*q: proponuję się zapoznać z http:*sjp.pwn.pl/lista.php?co=bynajmniej

0
kradyr napisał(a)

Witam!

Mam do zrobienia takie zadanie: http://ki.staszic.waw.pl/task.php?name=czworki

I teraz myślę jak to rozwiązać i nic nie mogę wymyślić. Jedyne co mi sie udało to to, żeby zrobić kilka pętl i tak jakoś jechać. Ale to ort! jest zbyt wolne rozwiązanie. Ma ktoś jakiś POMYSŁ jak to zrobić? Może jest jakiś do tego specjalny algorytm?

Proszę o pomoc.

Pokaż, by udowodnić, że naprawdę to zrobiłeś, wtedy ktoś wskaże jak to poprawić.
Czyli udowodnij, że nie jesteś kolejnym kodo-żebrakiem (leniem), który szuka jelenia do zrobienia zadania domowego.

0

Ale to ort! jest zbyt wolne rozwiązanie

O(n^4) to chyba nie jest tragedia?

Ale...

Hint1: zbuduj hashset do szybkiego sprawdzenia, czy suma siedzi w zbiorze. => O(n^3)
Hint2: skoro są nieujemne, posortuj rosnąco, znajdź maksimum i odcinaj iteracje, jak tylko suma przekroczy maksimum => nadal O(n^3), ale znacznie lepsze, bo dużą część obrotów pętli odetniesz...

Hint3: a + b = d - c (i śmiga w O(n^2))

0

http://main.edu.pl/user.phtml?op=showtask&task=szy&con=OI9
Praktycznie identyczny sposób rozwiązania. Rozwiązanie możesz znaleźć na stronie
http://oi.edu.pl/

0

A co mi tam. Rozwiązanie w 4 linijkach, złożoność O(n^2), z dodatkową optymalizacją:

def fours(list: List[Int]) = {
    val max = list.reduceLeft(Math.max(_, _))
    val x = (for(a <- list; b <- list if a + b <= max) yield a + b)
    val y = (for(a <- list; b <- list if a - b >= 0) yield (a - b, a, b)).groupBy(_._1)
    x.foldLeft(0)(_ + y.getOrElse(_, Nil).length)
}

Test:

scala> fours(List(1,2,3,4))
res8: Int = 4

scala> fours(List(1,2,3))
res9: Int = 1

scala> fours(List(1,2))
res10: Int = 0

scala> fours(List(1,3))
res10: Int = 1

scala> fours((1 to 1000).toList)
res11: Int = 166167000     // czas wykonania: ~5 sekund

Na C++ już sobie przetłumaczycie.

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