21898. Suchary AL_19_05

[gardziej]

Witam serdecznie!

Utknąłem na tym zadaniu http://pl.spoj.com/problems/AL_19_05/, program chyba działa dobrze natomiast TLE.
Czy coś słabo z optymalizacją w kodzie, czy może jest jakiś magiczny algorytm, który nie będzie badał liniowo kolejnych żartów?
W kodzie pododawałem różne testowe max i mini dla żartów, ale bez tego również TLE.
Prosiłbym o jakieś nakierowanie. Z góry wielkie dzięki.

Tu był brzydki kod O(m*n), O(m*log n) powinno się lepiej wpasować :) AC

P.S. nauka o wyszukiwaniu binarnym przyjęta

[rr__sof]

Jasne, że jest lepszy algorytm
Mała podpowiedź:
Spójrz na taki test:
3
9 8
3 4
5 6
Odpowiedz sobie na następujące pytania: w jakich przypadkach (dla jakich c, d) pojedynek skończy się na 3. rundzie (czyli wyłoni ona zwycięzcę)? Dlaczego?

[yula]

Jakoś nie mogę wpaść na to jak przyśpieszyć

[yula]

Nie wiem czy dobrze rozumiem zadanie. Jeżeli oboje zaśmieją się z danego dowcipu to przechodzą do następnego? Tak? Przeczytałam omówienie do zadania na forum algoligi i dalej nie rozumiem jak to miałoby zadziałać chociażby dla przykładu wyżej

[mariusz193]

Miałem duże problemy ze zrozumieniem tego zadania, dużo większe, niż znalezienie prawidłowego algorytmu po zrozumieniu

jeżeli zaśmieją się równocześnie (lub wcale) to jest remis

[yula]

Czyli rozumiem że dla przykładu wyżej roztrzygnięcia w 3-ciej rundzie nie będzie nigdy, bo wcześniej zaśmieją sie ?

[mariusz193]

niekoniecznie zaśmieją się wcześniej, ale rzeczywiście nie może być rozstrzygnięcia w 3 rundzie

[yula]

Może ktoś podrzucić jakieś testy ? Ciągle WA, podejrzewam że gdzieś jeden znak nie ten Jedną literówkę już znalazłam …

[yula]

Uff… AC, tak jak myślałam zabrakło w jednym miejscu ‘=’. A wcześniej ciekawa formuła (l+r/2)

[bieniek_k]

Witajcie, podrzuci ktoś jakąś wskazówkę do tego zadanka ? Ciągle mam problem z TLE. Zapisuje tylko żarty o mniejszym współczynniku niż poprzedni. Następnie sprawdzam (wcześniej przypadki trywialne) w dwóch kierunkach (w jednej pętli for), “w przód” jeśli nastrój ma większy dla danego żartu i w drugą stronę jeśli nastrój ma mniejszy bądź równy (czyli zaśmiał się na tym o 1 dalej). Macie jakąś wskazówkę jak to można jeszcze usprawnić, czy wgl idę w dobrym kierunku czy raczej nie ma to sensu ?

[tarpauwatratar]

Nie ma sensu.

Wyszukiwanie binarne.

[whitewolf875]

Witajcie, zrobiłem te zadanie z zastosowaniem wyszukiwania binarnego, ale i tak jest TLE. Nie wiem co jeszcze mam zoptymalizować (ChatGPT nie wyrabia). Mój brzydki kod: https://ideone.com/imXc06