Ok, napisałem sobie tester, który idzie "na głupa" od liczby a do liczby b, sprawdza czy są pierwsze i jak nie to wydłuża przedział "niepierwszości". Wszystkie powyższe wyniki są prawidłowe. Tak więc muszę chyba sobie przejść po wszystkich (od 0 0 do 4000000 4000000) kombinacjach par i sprawdzić później wyniki.
Mam takie same wyniki.
Skąd taki wniosek? Sędzia na SPOJ'u działa trochę inaczej, niż sobie niewtajemniczeni wyobrażają. Jak? ZOstań problemsetterem, to poznasz metodę jego działania bardziej od kuchni.
[Raczej] TLE gwarantowane.
PS
System komentarzy pod zadaniami, jest moim zdaniem niezdrowy więc nie powinno się go używać w ogóle, a już szczególnie w takim celu w jakim go użyłeś dla tego zadania. Trochę lepszym miejscem byłby ten wątek.
Przecież chcę to zrobić u siebie na komputerze. Jakie TLE? Robi mi to nawet teraz (już około a=2, b=2miliony) i idzie dalej w poszukiwaniu pary, która daje błędny wynik. Szacunkowo skończy za kwartał.
Tu masz rację... nie mam pojęcia jak on działa. Po prostu skoro czasem mi się wywala wcześniej, a jak zmienię coś w programie to właśnie na jedenastym to podejrzewałem, że informuje o pierwszym błędnym teście. Przechodzi najpierw wszystkie?
"Problemsetterem" z chęcią zostanę, ale chcę trochę więcej problemów przed tym zrobić. 
Póki jest mogę go używać bez względu na Twoje zdanie (to stwierdzenie nie miało zabrzmieć arogancko jak coś). Natomiast zastanawiam się czemu w szczególnie w takim celu w jakim go użyłem jest według Ciebie złe? Skomentowałem treść zadania w komentarzu co mi się wydaje logiczne.
A teraz wracając. Mam kilka pytań (do Ciebie i kilkunastu innych osób co zrobiły to zadanie), które może mnie nakierują:
Czy testy są w pełni zgodne z matematyką i 0 oraz 1 jest niepierwsze? Czyli czy wynik testu0 0 to:1,
zaś 0 1 to:2?
Czy są jakieś inne szczególne przypadki, które trzeba specjalnie obsłużyć? Nie wiem... np. przedział typu [liczba_pierwsza,ta_sama_liczba_pierwsza] (jak dla mnie powinno tu być 0) lub na końcu (na końcu ostatniej liniii wyjścia) nie może być entera. Bo nie mogę dojść gdzie mogę mieć błąd.
Ogólnie mój algorytm:
od a do b wyliczam sitem liczby pierwsze (oczywiście sitem od 2 do pierwiastka z b) i mierzę długość przedziału od liczba_pierwsza+1 do następna_liczba_pierwsza-1 włącznie. Zapamiętuję zawsze najdłuższy i voila. Powinno działać, a jest błędna odpowiedź. Próbowałem też wyniki tablicować (wektorem oczywiście) i nawet też da się zmieścić w czasie, ale wynik błędny.
Przecież zamieściłeś swój test, który przepuściłem przez swój program a wyniki porównałem z twoimi i napisałem
Z bardzo prostego powodu. system komentarzy jest chory [moja opinia] i szkoda tam twojego [cennego] komentarza, aby się tam mógł ewentualnie zmarnować. Nie twierdzę, że tak się stanie, ale poczytaj [wszystkie] komentarze pod zadaniem liczby pierwsze [pierwsze zadanie z łatwych] i może zrozumiesz co miałem na myśli?
Jeżeli w swoim teście miałeś taki[e] przypadek[ki], to już Ci odpowiedziałem, jeżeli nie to odpowiem. Dla a == b, odpowiedzią jest zawsze 1 lub 0, Co do mierzenia długości przedziału, to nie wydaje mi się taka metoda ani poprawna ani szybka - sędzia widocznie podziela moje zdanie 
No tak. Doceniam to i dziękuję za to. "A teraz wracając ..." rozumiałem jako: ok to w takim razie szukajmy dalej przyczyny. Faktycznie w teście było 0 0 to mogłem o to nie pytać, ale 0 1 nie było
Czemu (pytam o "poprawna"?) Może tu coś nie rozumiem. Opisuję jak robię na przykładzie:
Załóżmy, że mam przedział [150,200]. Wynajduję liczby pierwsze w tym przedziale, czyli:151. Aktualnie najdłuższy przedział 151-150=1157. Aktualnie najdłuższy przedział156-152+1=5 (bo 152,153,154,155,156)163. Aktualnie najdłuższy przedział 162-158+1=5167. Aktualnie najdłuższy przedział nadal5 (bo 166-164+1=3)173. Dalej 5179. Dalej5181. Dalej 5191. Aktualnie najdłuższy przedział190-182+1=9193. Dalej 9197. Dalej9199. Dalej 9200. Dalej9 (sprawdzam oczywiście koniec przedziału z ostatnią znalezioną liczbą pierwszą)
Odpowiedź to 9.
Czy tu gdzieś się mylę? Liczby niepierwsze to wszak liczby właśnie z przedziału między kolejnymi liczbami pierwszymi (prócz 0 i 1 rzecz jasna).
Oczywiście wszystkie liczby pierwsze od 2 do 4000000 mam policzone raz przed rozpoczęciem powyższej zabawy (i przed przyjęciem informacji o ilości testów).
Widzę komentarze pod Liczby pierwsze i jak najbardziej można się załamać (np. wrzucaniem kodu). Jakby ludzie używali tego systemu do komentowania właśnie treści zadania (to co ja zrobiłem) myślę, że wyglądało by to lepiej. W trudnych myślę nie przepadnie. Gdyby jednak to dla osób, które natkną się na ten wątek:
Czy istnieje wzór wyznaczający liczby pierwsze?1
Super, dzięki (odpowiedziałeś oczywiście wcześniej, ale warto mieć to napisane tak stricte)
Nie szukamy przedziału, tylko, wielkości max podzbioru [w przedziale].:
.. jaki jest maksymalny podzbiór kolejnych liczb naturalnych należących do przedziału obustronnie domkniętego, które nie są pierwsze.
Dlatego dla a == b odpowiedzią może być albo 0 albo 1.
A do wyszukiwania [szybkiego] maxa w przedziale można [trzeba?] użyć np odpowiedniego drzewa + [plus] wcześniejszy preprocesing [np sito + tworzenie tego drzewa] .
PS
Większość zadań z algoligi, omówiona jest na forum strony algoligii. Zadania z fraktala na stronie fraktala [przeniesione na facebook]. Kilkanaście [raczej trudniejszych] zadań omówionych jest na już nie kontynuowanym blogu kokoska 
Może źle się wyraziłem, ale chyba właśnie to robię. Odpowiedź 9 to jak najbardziej wielkość największego podzbioru kolejnych liczb naturalnych niepierwszych w przedziale obustronnie domkniętym (w tym przypadku [150,200]).
Czy się mylę?
U mnie dla a==b jak najbardziej będzie też 0 lub 1
Co do szybkiego wyszukiwania to masz rację, że można drzewem szybciej, aczkolwiek chwilowo mam błędną odpowiedź i nadal nie wiem dlaczego. oczywiście wiem, że dlatego, że mam coś źle, ale wydaje mi się, że algorytm, prócz prędkości, jest poprawny i tu pytanie... czy tak jest?
---Edit---
Znalazłem omówienie tego zadania na stronie fraktala (nie jest to łatwe). Ostatniego akapitu jednak nie rozumiem:
Przy zapytaniach będziemy szukać wartość maksymalną w przedziale. Należy tylko liniowo rozpatrzyć początkową lewą część przedziału (liczb niepierwszych w tym przedziale może być co najwyżej 147).
Dlaczego tylko początkową lewą część przedziału? Nawias mi nie wyjaśnia. Ja bym zrobił tak: przeszukujemy cały przedział od lewej, chyba że napotkamy 147 to już dalej nie trzeba.
Chyba, że o to właśnie chodziło (ale jeśli tak to trochę niejasno napisane)
nadal jednak interesuje mnie rozwiązanie zagadki błędnej odpowiedzi w moim sposobie.
Masz większość zgłoszeń z TLE. Porównaj swój ostatni program tle z pierwszym wa i zobacz co tam zmieniłeś, może w ten sposób dojdziesz do odpowiedzi?
PS
Podpowiedzi na forach [które podałem] nie zawsze muszą być najlepsze i jedyne, Są to najczęściej omówienia rozwiązań wzorcowych - autorskich. Możliwe, że autor inaczej rozwiązał to zadanie, bo też w tej chwili nie bardzo mogę zrozumieć tego fragmentu opisu. Czasami, mimo prawidłowej wzorcówki, opisy są błędne lub niejasne. Ale w końcu zawsze chodzi o większą samodzielność rozwiązujących problemy.
szukamy maksymalnej wartości w drzewie - ale w lewej części liczby mogą nie zaczynać się od 0 lub 1 więc sprawdzamy lewą stronę do napotkania pierwszej liczby pierwszej (lub końca przedziału)
a następnie bierzemy większą z liczb: długość lewego przedziału , największa wartość z reszty
np. dla przedziału [28,35] mamy wstawione wartości
5 0 1 0 1 2 3 4
po lewej stronie do wystąpienia pierwszego 0 mamy tylko 1 liczbę, największa liczba w reszcie przedziału to 4 i ona będzie prawidłową odpowiedzią, a nie 5 gdybyśmy brali największą z całego przedziału.
A to nie jest tak (tutaj też nie wiem), że jeżeli jednocześnie przekroczyłem czas oraz miałem błędne odpowiedzi to najpierw się dowiem o przekroczeniu czasu? Bo jeśli tak to odkryję tylko dlaczego miałem TLE, a już nie ma, a to wiem (bo przestałem tablicować te rozpiętości, a porównywać na bieżąco). Chyba, że najpierw dostaję informację o WA, a później o ewentualnym TLE? Czy zależy od uruchomienia?
W ogóle (teraz dygresja), to że mam tyle TLE to wyjaśniam: dla mnie spoj to taka zabawa w wymyślanie własnych rozwiązań różnych od prawdopodobnie zaplanowanych przez autora. Lubię po prostu rozwiązać nieschematycznie zadanie i od razu tak próbuję. Stąd przy każdym moim rozwiązanym zadaniu sto innych TLE i WA, ale koniec końców wrzucam też ten najbardziej (wydaje mi się) wzorcowy.
Choć chyba nie przebiję użytkownika o nazwie @ostatni (już nieaktywny), który postanowił zawsze rozwiązać zadanie najgorzej (przykład2).
Czyli muszę przejść po całym przedziale z uprzednio przygotowaną mapą wartości dla wszystkich liczb z tego przedziału?
Co gdybyśmy nie napotkali 0? Byłoby (załóżmy) 5 6 7 8 i wzięlibyśmy 8?
Jeśli mogę prosić... omów przykład [15717,15726] (wszystkie liczby w tym przedziale są niepierwsze, a dla 15717 wartością jest 35)
@mariusz193 Masz rację , dokładnie tak, jakiś czas temu robiłem to zadannie i takie szczegóły uleciały z głowy
PS
Dobry czas w tym zadaniu [w porównaniu do wzorcówki autora] to zasługa fast i/o.
Nie. O ile się to nie zmieniło - w końcu SPOJ żyje i się rozwija, było tak:
Najpierw wykonywane są wszystkie testy, chyba że wystąpi błąd krytyczny [np SIGABORT].
Potem są po kolei sprawdzane do napotkania pierwszego błędu. Nawet jeżeli dzieje się inaczej, dowiesz się o pierwszym błedzie, więc może być to równie dobrze WA jak i TLE. Najczęściej na początku są "małe" testy, na których ciężko dostać TLE [nawet brutem].
Są też trochę inaczej działające programy sędziujące i [radosna] twórczość autorów zadań - programy sędziujące napisane przez autora zadania [wcześniej opisany był standartowy - napisany i rozwijany przez administrację systemu SPOJ].
Kiedyś spróbuję zrobić z tym drzewem, choć bardziej mnie interesuje co jest źle u mnie. Oto kod:
http://ideone.com/540Gkz10
jak nikt nie dojdzie to za jakiś czas skasuję.
Dzięki za wyjaśnienie. Szkoda, że nie dostaje się informacji o wszystkich błędach (jak w zadaniach punktowych).
PS. mój czas nie wydaje mi się najgorszy, a mogę go łatwo przyspieszyć dla dużych danych (dodając warunek, że jeżeli range>2100000 to podaj wynik 147).
oczywiście, że nie musisz (gdybyś musiał, to byłoby TLE) - po to jest drzewo przedziałowe
skoro wszystkie niepierwsze, to odpowiedzią jest długość przedziału, bo prawej części nie ma
Odpowiedź znam... nie rozumiem w Twojej wypowiedzi po prostu jednej części.
Ok... to w sensie kiedy byłby przypadek (dla jakiego przykładowego ciągu), że liczba po lewej (tutaj 5) byłaby odpowiedzią? W sensie po co mi w ciągu ta piątka? Może już z powodu godziny nie rozumiem
Stąd było pytanie o omówienie innego przykłądu.
Minął tydzień, drugi, a niedługo minie trzeci. Obiecałem więc acz niechętnie piszę
Jaki czas wydaje Ci się nie najgorszy? : http://pl.spoj.com/status/FR_02_13,redysz/4 Czas 0.02 zgłoszenia nr 19826638, czy może czas 0.22 ostatniego zgłoszenia? Przecież jeżeli masz błędną odpowiedz, to ten czas jest też błędny [dotyczy tylko pierwszego[ych] testu[ów]
Przecież nawet na ideone, dla twojego malutkiego teściku [n=tylko 101] już masz czas 0.14.
Kolejność jest taka: najpierw uzyskaj AC, a potem baw się optymalizacjami, ulepszaczami i przyśpieszeaniem swojego programu. W tym wypadku wiesz jak zrobić program - drzewo maximów + zwykłe sito + wzbogacenie tabeli liczb pierwszych.
PS
Jeżeli chodzi o twój zamieszczony program, to czy warto szukać tam błędu? I tak będzieTLE. jEŻELI KONIECZNIE JEDNAK CHCESZ GO ZNALEŹĆ LUB PROSIĆ O POMOC W ZNALEZIENIU [sorry caps się włączył] błędu to uprość kod. W tej chwili masz tam i bruta i swoją implementrację kodu napisanego w pythonie. Czy wiesz czym w pythonie jest S = {} ?
PS 2
Czym jest wzbogacona tabela liczb pierwszych? [ma to w algorytmice swoją nazwę, ale w tej chwili nie pamiętam]
Zwykła tablica liczb pierwszych:
0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 ...... itd
lub [odwrotnaa]
1 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0
wzbogacona [np liczymy ile jest liczb pierwszych od początku:]
0 0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 77 7 7 7 8
dla naszego zadania "wzbogacamy" inaczej:
1 2 0 0 1 0 1 0 1 2 3 0 1 0 1 2 3 0 1 2 3 4 5 0 .... itd
Dla dowolnego wybranego fragmentu takiej nasze wzbogaconej tablicy, może wystąpić np:
.... 0 1 2 3 4 5 0 1 0 1 2 3 4 5 6 7 ....
Interesuje nas pogrubiony przedział.
z fragmentu 0 1 0 1 2 3 4 5 max obliczamy drzewem, ale dodatkowo musimy "ręcznie" sprawdzić lewy fragment
Inny przykład:
.... 0 1 2 3 4 5 6 7 8 9 10 0 1 0 1 2 3 4 5 6 7 ...
Powyżej drzewo analogicznie "podaje". maks 5, {0 1 0 1 2 3 4 5} ale ręcznie obliczamy lewy fragment, który tu wynosi 6.{5, 6, 7, 8, 9, 10}
AD PS
Sorry, na githubie, jest też kod w cpp, nie zauważyłem. W tym kodzie chodzi o zmniejszenie zużycia pamięci, ale dla małych n, kod jest wolniejszty [jak pisze autor] od zwykłego sita, więc w zadaniu lepiej po prostu nie kombinować i użyć zwykłego sita. A błąd, może porównaj swój kod z orginałem? Użycie long long czy uint64_t jest całkowicie zbędne. "Zwykły" zupełnie wystarcza do tego zadania [to oczywiście nie zmieni w cudowny sposób tle w AC].
PS 3
Aby "uzyskać przesiane" liczby pierwsze i "wzbogacić" uzyskaną tabelę o dodatkową informacje i tak "twój" kod z githuba na niewiele się przyda - odzielnie trzymana jest lista liczb pierwszych ii fargmentarycznie liczb złożonych [na bieżąco uzupełniana i odpowiednio zubożana-kasowana]
Dzięki za odpowiedź.
Kolejny raz na tym forum rozmywamy się co do celowości tego co robię. Wytłumaczę by nie było nieporozumień:
Tobie zależy na poprawnym wykonaniu zadaniu na spoja - super, cudownie. Taki masz cel i ok. Chciałbym byś nie mierzył innych swoją miarą. Mój cel jest całkiem inny:
Wchodzę na spoja by znaleźć ciekawe zagadki i sobie je rozwiązać, by się czegoś nauczyć (najczęściej z matematyki). Na drugim miejscu mam to czy dostanę AC czy nie (choć finalnie AC jest potwierdzeniem tego czy dobrze zagadkę rozwiązałem). Wielokrotnie potrafię rozwiązać zadanie (jak to zadanie z prostokątami), ale o wiele bardziej interesuje mnie niejasne matematyczne twierdzenie. Dopiero jak się uporam z twierdzeniem, które na amerykańskiej stronie brzmi "By stwierdzić, czy można zmieścić jeden prostokąt w drugi wystarczy poniższy wzór" - i to twierdzenie jest błędne (co sam potwierdzasz) bo sam wzór nie jest wystarczający, to dopiero rozwiążę sobie to zadanie na spoju poprawnie co jest banalne.
Podobnie... umiem rozwiązać to zadanie sposobem na jaki mnie nakierowałeś (i za to jak najbardziej dziękuję). Natomiast na drugim miejscu mam rozwiązanie tego zadania i otrzymanie AC. Spoj to tylko serwis, którego jutro może nie być. Znalazłem natomiast ciekawą zagadkę - mam program, który dla wszystkich wymyślonych przeze mnie (wielu) par dostaje błędną odpowiedź i się zastanawiam gdzie się wywala. Chcę tę zagadkę rozwiązać przede wszystkim. Jak już dojdę gdzie jest błąd (nie dostanę błędnej odpowiedzi tylko tle) to sobie (albo i nie - w zależności jak będzie mi się chciało) przepiszę ten program tak by dostać AC. Schemat jest prosty więc pewnie go dostanę.
Inaczej pisząc: nawet jakbym zrobił zadanie drzewem, dostał AC (co jest dla mnie nieważne) to i tak bym ten temat założył by dojść czemu w tym rozwiązaniu mam błąd. Gdzie on jest? To jest dla mnie fascynujące. To jest też rozwijające. Ku temu założyłem wątek.
To tak by wyjaśnić swój sposób rozumowania i właśnie dlatego taka propozycja:
Kolejność jest taka: najpierw uzyskaj AC, a potem baw się optymalizacjami, ulepszaczami i przyśpieszeaniem swojego programu. W tym wypadku wiesz jak zrobić program - drzewo maximów + zwykłe sito + wzbogacenie tabeli liczb pierwszych.
do mnie nie przemawia.
Mam nadzieję, że rozumiesz
Nie chciałem uzyskać AC (nie w pierwszej kolejności oczywiście) - tylko znaleźć błąd w tym rozwiązaniu, by się czegoś nauczyć. Po to założyłem wątek.
Więc jeżeli chodzi o zdanie:
Jeżeli chodzi o twój zamieszczony program, to czy warto szukać tam błędu?
skoro po to założyłem wątek by znaleźć właśnie w nim błąd... to nie wiem czy warto szukać tam błędu 
Mylisz się. Moim celem jest nauka programowania, poprzez rozwiązywanie problemów, AC jest tylko miernikiem [wskaźnikiem], czy poprawnie [zgodnie z intencją i testami autora] rozwiązałem problem. Potem, w celu dalszego doskonalenia mogę się bawić i eksperymentować ze swoim kodem, ale gdy mam AC to od razu widzę efekty eksperymentu, bo albo dostaję odpowiedź, że uzyskany - poprawiony kod jest lepszy [dużo lepszy] lub zgoła zły [lub tle] ale wtedy bez flustarcji i spokojnie mogę wrócuić do bazowego AC i dalej eksperymentować lubg zająć się innym problemem [także problemami innych na forum].
Gdy notorycznie dostaję WA czy TLE i poprawiony kod to nadal WA lub TLE to w efekcie nie mam zielonego pojęcia, czy kod jest lepszy czy gorszy. Oczywiście mogę to robić u siebie, ale to już inna bajka.
W zasadzie chyba już napisałem co nieco o twoim kodzie, [a właściwie bez sensu dwa kody:
if(stop-start<500) {
więc nie będę się powtarzał.
| Topic | Category | Replies | Views | Activity |
|---|---|---|---|---|
| Liczby Pierwsze | Zbiór zadań | 2 | 176 | May '24 |
| FR_08_11 - Gra w bańki | Zbiór zadań | 1 | 130 | Jun '24 |
| MBPROB01 - History version in plaintext pl.spoj.com | Zbiór zadań | 6 | 105 | Jul '24 |
| TOPSORTL - Porządek leksykograficzny w grafie | Zbiór zadań | 3 | 107 | Jul '24 |
| TFRACAL - Kalkulator ułamków | Zbiór zadań | 2 | 109 | Feb 1 |
