• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie temperatura - problem

VPS Starter Arubacloud
0 głosów
441 wizyt
pytanie zadane 22 maja 2023 w C i C++ przez Dani Obywatel (1,420 p.)

Witam, napisałem kod z gąsienicą i kolejką monotoniczną, i gdy wrzucamy do szkopuła, to w niektórych testach przekracza on limit czasowy, co dziwne bo powinno wchodzić czasowo, najwyraźniej coś przegapiłem. Byłbym wdzięczny jakby ktoś mi wytłumaczył co jest nie tak, i czemu on jest za wolny.https://szkopul.edu.pl/problemset/problem/6sGsrkO-SrmtogJ7u3RIOj3f/site/?key=statement

#include <iostream>
#include <deque>
#include <utility>
#include <vector>
#include <cstdio>

using namespace std;

struct para {
    int first;
    int second;
} ;


deque<pair<int,int>> kolejka;
para tab[1000000+5];

void push_(int x,int idx){
    while(!kolejka.empty() && kolejka.back().first <= x)
        kolejka.pop_back();
    
    kolejka.push_back(make_pair(x,idx));
}

void pop_(int idx){
    if(!kolejka.empty() && kolejka.front().second == idx)
        kolejka.pop_front();
}

int get_maximum_(){
    return kolejka.front().first;;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;

    for(int i=0;i<n;++i){
        cin >> tab[i].first;
        cin >> tab[i].second;
    }
    push_(-1e9-5,-1);
    int l=0,r=0;
    int wynik=1;
    while(r < n){
        while(get_maximum_() > tab[r].second){
            pop_(l);
            ++l;
        }
        if(get_maximum_() <= tab[r].second){
            wynik = max(wynik,r - l + 1);
            push_(tab[r].first,r);
        }
        
        ++r;
    }
    printf("%d",wynik);

    return 0;
}

 

komentarz 22 maja 2023 przez j23 Mędrzec (194,920 p.)

Tak nawiasem. Po co definiujesz strukturę para, skoro w kolejce i tak używasz std::pair?

2 odpowiedzi

0 głosów
odpowiedź 22 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
W funkcji push powinno być < zamiast <= to napewno.
komentarz 23 maja 2023 przez Dani Obywatel (1,420 p.)
Rzeczywiście, ale i tak to nie chce wejść
0 głosów
odpowiedź 24 maja 2023 przez MikDal Mądrala (5,660 p.)

Na początku analizowałem złożoność obliczeniową zaprezentowanego algorytmu i zatrzymałem się na tym konstrukcie:

while(get_maximum_() > tab[r].second){
   pop_(l);
   ++l;
}

Rozwijając ten kod otrzymujemy coś takiego:

while(kolejka.front().first > tab[r].second) {
   // funkcja pop_
   if(!kolejka.empty() && kolejka.front().second == l)
        kolejka.pop_front();
   ++l;
}

Generalnie program jest dla mnie bardzo ciężki w analizie przez enigmatyczne nazwy zmiennych ("l"), ale udało mi się wprowadzić program w bardzo długie czasy wykonania, dostarczając po prostu zera. Dając takie dane jak poniżej, program zamyka się w tej pętli, nie będąc w stanie zdjąć elementów ze stosu, bo l jest już daleko większe niż 0. 

0: 1 5 
1: 4 8 
2: 2 5 
3: 6 8 
4: 0 0 
5: 0 0 

Udało mi się również zrobić to z innymi liczbami (1, 5, -100). Program ewidentnie nie lubi dwóch następujących po sobie niskich wyników. 

 

Generalnie program jest wykonany dość złożenie obliczeniowo i wydaje mi się, że jego wykonanie może nawet zająć O(n^2) w najbardziej pesymistycznym momencie. Proponowałbym wersję, bez jakiejkolwiek pamięci w postaci listy/kolejki. 

komentarz 24 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Ciężko zaproponowac wersję bez kolejki / listy, bo nie da się dostać 100pkt bez tego. (chyba że chcesz zrobić listę/kolejkę na vectorze, ale to nie ma sensu).
komentarz 24 maja 2023 przez MikDal Mądrala (5,660 p.)
edycja 25 maja 2023 przez MikDal

=== EDIT ===

Jednak źle zrozumiałem zadanie, ale treść komentarza zostawiam nie zmienioną.

===

O ile dobrze rozumiem zadanie, to:

  • Dany jest ciąg n, który reprezentuje kolejne dni pomiaru temperatury,
  • Dana jest relacja n-1 ►n, która zwraca prawde, gdy temperatura dnia poprzedniego była niższa lub równa w dniu n. 
  • Zwróć liczbę elementów, w których relacja ► była nieprzerwana najdłużej. 

Aby to zrealizować potrzebujemy trzymać tylko n i n-1 oraz aktualną liczbę dni o niemalejącej temperaturze oraz najdłuższy dotychczasowy rekord dni o niemalejącej temperaturze. 

Z tego co widzę na przykładzie relacja ► jest w rzeczywistości sprawdzeniem, czy najniższa temperatura dnia poprzedniego jest niższa od temperatury maksymalnej dnia n.

Dlatego tez nie widzę potrzeby trzymania wszystkich danych wejściowych w pamięci. Ale możliwe, że "szkopuł" nakłada jakieś ograniczenia, lub źle przeczytałem zadanie, choć nie wydaje mi się :). 

komentarz 25 maja 2023 przez Whistleroosh Maniak (56,900 p.)
Może się zdażyć, że w dniach i...j temperatura mogła być niemalejąca, w dniach i..(j+1) nie, a w dniach (i+1)...(j+1) tak. Wtedy sprawdzanie dwóch ostatnich dni nie wystarczy
komentarz 25 maja 2023 przez Dani Obywatel (1,420 p.)

@MikDal, A kolejka monotoniczna wraz z gąsienicą nie ma złożoności O(n) ?

1
komentarz 25 maja 2023 przez Whistleroosh Maniak (56,900 p.)
Działa w O(n), ale najwidoczniej program wiesza się na nieskończonej petli while. Musisz poprawić warunki w pętli
komentarz 25 maja 2023 przez MikDal Mądrala (5,660 p.)

@Whistleroosh, przysiadłem do tego na spokojnie, masz rację, pomyliłem się, nie można tego zadania wykonać w O(n). Także moje założenie powyżej jest błędne. 

@Dani, co do samej kolejki z gąsienicą to podaje się, że ma złożoności O(n). Niektóre źródła (np. to Informatyka. Konkursy i algorytmy. (oki.org.pl)) podają O(2n), co podoba mi się bardziej. 

komentarz 26 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Tak kolejka monotonniczna wykona pesymistycznie 2N operacji, bo każdy element maksymalnie raz dodasz i raz usuniesz. Ale 2N to O(N).
1
komentarz 26 maja 2023 przez Dani Obywatel (1,420 p.)
int get_maximum_(){
    if(kolejka.empty())
       return -1e9-5;
    return kolejka.front().first;;
}

W końcu znalazłem problem. Mianowicie trzeba było w otrzymywaniu maksa uwzględnić przypadek pustej kolejki, i teraz wchodzi na 100 pkt. Dziękuję wszystkim za poświęcony czas!

Podobne pytania

0 głosów
1 odpowiedź 178 wizyt
pytanie zadane 19 maja 2023 w C i C++ przez Dani Obywatel (1,420 p.)
0 głosów
1 odpowiedź 176 wizyt
pytanie zadane 16 sierpnia 2023 w C i C++ przez Dani Obywatel (1,420 p.)
0 głosów
1 odpowiedź 116 wizyt

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...