Dynamiczne programowanie - spoj

pytanie zadane 8 grudnia 2018 w PHP przez detmold Nowicjusz (180 p.)

Chodzi o zadanie ze spoja -> https://www.spoj.com/problems/COINS/ Dostaje status WA

Ogólnie to wykorzystałem tutaj rekurencję + technikę zapamiętywania wyników, działa to szybko. Dla górnego progu wykonuje się tak samo szybko jak dla małych liczb.

Testowałem wyniki tutaj -> http://spojtoolkit.com/test/COINS

54 testy czyli wszystkie jakie tam były proponowane i wszystko ok. Tak czytałem na temat spoja ale linki do działających wersji do tego problemu i tak bez problemu można znaleźć a nie o to tu chodzi, ogólnie to ciekawi mnie gdzie w moim programie jest błąd dlatego wrzucam kod: https://ideone.com/KnTkB5

1 odpowiedź

odpowiedź 8 grudnia 2018 przez jankustosz1 Nałogowiec (35,880 p.)
wybrane 8 grudnia 2018 przez detmold

Najlepsza

Array w php to coś typu map w c++? Jeżeli jest to zwykła tablica to wychodzi ci poza zakres bo tam są limity na 10^9.

Btw. lepiej pisać algorytmy w c++ bo wykonuje się on szybciej i limity zazwyczaj są ustawiane pod niego. Jest niskopoziomowy i zawsze wiesz jak się co wykona a taki php nie wiadomo jak wewnętrznie działa.

komentarz 8 grudnia 2018 przez detmold Nowicjusz (180 p.)

OK dzięki, chyba mi podpowiedziałeś w czym problem. To pewnie kwesta tego, że używam do indeskowania tablicy wartości z przedziału <0, 10^9> i mimo, że same dane zajmują tylko tyle ile ich było dostarczone, php pewnie dostając indeks 10^9 wywala na spoju memory limit.

Swoją drogą zaraz to sprawdzę bo u siebie testowałem na limicie 4 gb

komentarz 8 grudnia 2018 przez jankustosz1 Nałogowiec (35,880 p.)

To jest właśnie problem, że nie wiadomo czy jak się odwołasz do np. 100 elementu to on tworzy 100 elementów jeżeli wcześniej było mniej czy wrzuca to na drzewo binarne. Raczej jednak wątpię, aby to było zrobione w ten pierwszy sposób, bo hash cody stringów mogą być długie a te tablice to przecież też je mogą przechowywać. W każdym razie to jest problem że nie wiadomo jak array jest zaimplementowane.