1 / 12
Jan 2015

Witam serdecznie!

Utknąłem na tym zadaniu http://pl.spoj.com/problems/AL_19_05/33, 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

  • created

    Jan '15
  • last reply

    Jun '23
  • 11

    replies

  • 1.0k

    views

  • 7

    users

  • 2

    likes

  • 2

    links

Jasne, że jest lepszy algorytm smile
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?

3 years later

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

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 :confused:

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

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

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

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

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

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

2 years later

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 ? :smiley:

2 years later