Ponieważ I etap się już skończył, więc myślę, że mogę to udostępnić:

15
pppjjpjpjpjjppj

(by Adrian Siwiec)

powinno wyjść 5

Podobno wywalało to większość liniówek

Otóż bynajmniej nie Ty jeden wpadłeś na tego typu test. Nie jest to jakaś wielka niespodzianka czy mądrość. Mało, bo mało, ale kilka testów z paczek dostępnych na forum już wcześniej również rozkładało te same liniówki co i Twój test.
Przyznaję tego typu test położył moje pierwsze rozwiązanie do tego zadania

Jak już zaznaczyłem, nie jestem tego testu autorem, również mojego programu (n log n) on nie rozwalił.

ufff, przez ostatnie 15 minut byłem przekonany, że wysłałem błędne rozwiązanie (wychodził mi wynik 1), ale na szczęście po prostu kopiowałem bez "15" na początku ;)

Również wydaję mi się, że było kilka testów tego typu na forum :P

no cóż...
http://www.youtube.com/watch?v=qy03EDdDsBw

Może mi ktoś powiedzieć (w sensie napisać), co jest w tym teście takiego specyficznego?

Algorytmy, które działały na zasadzie wyznaczania granic pomiędzy "prawidłowymi" przedziałami,a "nieprawidłowymi" wywalały przedziały nieprawidłowe, jednakże w przedziałach nieprawidłowych mogły mieścić się przedziały prawidłowe jak w tym powyżej, przez co pokazywały zły wynik. Ciekawe jest jeszcze inne pytanie, jaką złożoność miałby zmieniony powyższy algorytm, który by wyznaczał granice dopóki można to robić? Z moich obserwacji(ale być może istnieją gorsze przypadki) wystarczało 5 razy od prawa i od lewa to zrobić, co oznaczałoby to, że jest to liniówka, ale jakoś w to nie wierzę. No cóż, zobaczymy czy testy ubiją moje algo na maxtestach

Moje rozwiązanie jest podobne do opisanego powyżej - wyznacza granice dopóki się da. Cóż - czas pokaże czy jest to optymalne rozwiązanie :)

Moje również, chociaż dodatkowo dodałem optymalizację polegającą na aktualizowaniu jedynie małych fragmentów, które faktycznie tego potrzebują, a nie całej tablicy. Takie rozwiązanie na maxtestach z forum dawało mi czasy poniżej 0.1s (OITIMETOOL) :).

Jeżeli tyle osób, ma to rozwiązanie, to może ktoś oszacował lepiej niż ja, ile trzeba razy przejechać po tej tablicy od prawa i od lewa,żeby wyznaczyć wszystkie granice? Albo inaczej, czy istnieje przykład dla którego nie wystarczy przejść 5 razy?

Łukasz Wołoszyn, mam to rozwiązanie, które Cię ciekawi i wg moich wyliczeń opartych na obserwacjach, najgorszym możliwym przypadkiem może być nlog(n/2), ale nie potrafiłem takiego przykładu stworzyć i mój program podobnie jak Twój miał najgorszą złożoność na wszystkich testach z forum 6n.

Ależ Wy tu kombinujecie. A nie da się tego zadania zrobić jednym przejściem po całym ciągu bawiąc się jakimś stosem? :-)

eeee... Nie?

To chętnie poznam test, który zepsuje ten kod: http://ideone.com/cnNf55 ;-)

Wydaje mi się, że zapomniałeś chyba o zwróceniu 0 na końcu programu :)

W c++ nie trzeba jawnie zwracać 0. ;-)

C++ Standard, chapter 3.6.1 paragraph 5:

A return statement in main has the effect of leaving the main function (destroying any objects with auto- matic storage duration) and calling exit with the return value as the argument. If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;

DOBRZE!!! Nauczyłeś pokory conajmniej 2 osób. ;]

Ja też napisałem taki algorytm, który patrzy na przemian w prawo i lewo, jednak można skonstruować przykład, w którym musimy powtórzyć tą czynność O(sqrt(n)) razy. Zasada generowania jest całkiem prosta, poniżej mały przykład:
193
pppppppppppppjjjjjjjjjjjjpppppppppppjjjjjjjjjjpppppppppjjjjjjjjpppppppjjjjjjpppppjjjjpppjjpjjjppppjjjjjppppppjjjjjjjppppppppjjjjjjjjjppppppppppjjjjjjjjjjjppppppppppppjjjjjjjjjjjjjpppppppppppppp
(13p 12j 11p 10j 9p 8j 7p 6j 5p 4j 3p 2j 1p 3j 4p 5j 6p 7j 8p 9j 10p 11j 12p 13j 14p)
Duży przykład: http://cubix.one.pl/public/max4.in
Ja dodałem optymalizację, że zamieniam np. pppppjjppp -> 5 2 3. Tak nowo powstały ciąg jest długości O(sqrt(n)) dla powyższych testów, więc całość ma złożoność O(n). Dla takiej optymalizacji maxtest poniżej, na oitimetoolu czas miałem ok 1,3 s, jednak złożonościowo jest to chyba O(n sqrt(n)) z dość małą stałą:
http://cubix.one.pl/public/max18.in

Nie wiem jak twój algorytm, ale mojemu wystarczyło 2 RAZY przejechać po tym przykładzie czyli tyle samo co w pierwszym poście. Również myślałem o testach takiej budowy, ale one akurat nie są jakieś trudne, bo zawsze wystarczą dla nich dwa obroty pętlą w tą i wewte.
// edit
Wcale nie tak łatwo jest z tymi testami :P

To opiszcie dokładniej co robicie patrząc w lewo i prawo, chętnie się dowiem :)

@Jakub: Czy możesz powiedzieć jaki jest out dla testu z Twojego przedostatniego wpisu? :-)

@Nobert 1000, chociaż nie wiem, czemu nie zaklepałeś bruta, żeby sprawdzić
@Grzegorz Graczyk Masz całkowicie inny sposób działania niż zwykłe stawianie granic, więc nie wiem czy to heura czy wzorcówa
@Jakub Cisło Ja mam zrealizowane stawianie granic poprzez fcja rekurencyjna szukająca najlepszego wyniku na danym przedziale.Błędnie założyłem, że trudność przykładu zależy od głębokości stosu rekurencyjnego, jednakże jest inaczej.

Dzięki - brut gdzieś leży na dysku mojego komputera, jednakże jestem w terenie i nie mam do niego dostępu ;-)

@Norbert: max4: 1000, tak jak napisał Łukasz, max18: 675103
@Łukasz: dalej nie wiem, jaki jest Twój algorytm. W sumie nie wiem nawet w końcu, co rozumiesz poprzez stawianie granic. Ja idę w prawo od początku i gdy zejdzie mi suma poniżej zera (czyli liczba p < j), to tutaj stawiam tę granicę, od tego miejsca zaczynam od nowa i lecę dalej na prawo. Mam więc najdłuższe fragmenty, które są ok w prawo. Teraz dla tych fragmentów sprawdzam, je analogicznie w lewo i ew. dostawiam granice. I tak w kółko dopóki cały fragment nie jest dobry w dwie strony. Też to mam rekurencyjnie zrobione.

@Jakub wynik 675103 wydaje się być dość duży.. pewnie jest jeszcze jakiś większy maxtest?

A co sądzicie o tym? Np. dla :
1 -2 5 -3 3 -1 1 -5 1
początkowo maxem, początkiem oraz końcem najlepszego ciągu jest element pierwszy z brzegu (ciąg czyszczę tak aby zawsze z przodu i na końcu znajdowała się liczba dodatnia), idąc w prawo sumuję kolejne elementy, jeśli suma jest równa/wieksza maxowi to przesuwam koniec ciągu na aktualnie dodawany do sumy element i nowym maxem jest suma. Jeśli suma zejdzie poniżej zera to sumuje abs wartości ciągu z zakresu początek-koniec i sprawdzam czy uzyskana suma jest większa od jakiegoś tam wcześniej ustalonego maxa2. Następnie powtarzam wszystko od nowa dla kolejnych elementów. Wypisuje max2. Może znajdzie ktoś kontrprzykład?

@Jakub Cisło czyli dokładnie jak ja
@Filip Łubniewski Jest dowód na poprawność takiego algo, więc kontrprzykładu nie będzie, jednakże mam nadzieję, że sumy abs liczysz w stałym czasie :)
@Jan Góra przy tym sposobie tworzenia testów nie ma większego maxtesta

@Jakub Cisło
Faktycznie ciężkie testy dla tego typu algorytmu, szkoda, że nie wymyśliłem ich w czasie zawodów. Tak to jest, jak się robi zadania w ostatnie kilka dni :).

@Grzegorz Graczyk
Byłem tak ciekawy że postanowiłem sprawdzić czy Twój program przechodzi testy ^^ Twój algorytm wymiata

Dla ciekawych dobrze skodzone "stawianie granic"(czyli to co już opisywałem tu kilka razy) dostaje 100, 90 gdy działa na ciągu -1 1 -1 -1 etc. , 100 gdy działa na -3 5 -7 4 etc.