Zadania na gąsienicę?

pytanie zadane 10 maja 2023 w C i C++ przez Dani Obywatel (1,450 p.)

Witam, czy macie jakieś fajne zadania na gąsienicę godne polecenia? Najlepiej jakby były z oi bądź oij

komentarz 15 maja 2023 przez reaktywny Nałogowiec (41,050 p.)

A gąsienica to ???

komentarz 15 maja 2023 przez Dani Obywatel (1,450 p.)

Larwa, bądź w tym kontekście jeden z algorytmów. Tutaj masz film, w którym jest rozwiązywane zadanie z użyciem gąsienicy : https://www.youtube.com/watch?v=TMgFEpTuBvQ

2 odpowiedzi

odpowiedź 10 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
wybrane 10 maja 2023 przez Dani

Najlepsza

Najbardziej klasyczny przykład użycia gasienicy, to znajdź w ciągu, którego wszystkie liczby są nieujemne spójny fragment (może być też najdłuższy) o sumie równej x.

Zadania jakie ja pamietam na gąsienicę, to:

Lizak, 2 etap XVI OIJ: https://szkopul.edu.pl/problemset/problem/9y5Fywu8h7DyO89-gd5ifrju/site/?key=statement

Notowania akcji, 2 etap XIV OIJ: https://szkopul.edu.pl/problemset/problem/Vtr5pP-RRtjqnivWocv8xaad/site/?key=statement

O ile dobrze pamiętam, to też to: https://szkopul.edu.pl/problemset/problem/GE48t27fgAbn4WNGoGhVChb-/site/?key=statement

Na zdalnych warsztatach olimpijskich dla juniorów 2022, Adam Gąsienica Samek robił wykład o gąsienicy(jest na kanale OIJ na yt) i na sio2 są zadania z sprawdzarką: https://sio2.mimuw.edu.pl/c/zwo22/p/

Dołożyłbym jeszcze zadanie Zespoły z 2 etapu XV OIJ, ono nie jest na strikte gąsienicę, ale pomysł i tak fajny(a prosty): https://szkopul.edu.pl/problemset/problem/WsCEgGZvejeElRDr0xT7Nwwf/site/?key=statement

Dodam jeszcze, że gąsienica często występuje z różnymi strukturami danych np. utrzymującymi co jest w gąsienicy. Czasem jest to zwykła tablica, czy kilka zmiennych, ale czasem może to być np. set / multiset / mapa / kolejka monotonniczna itp.

komentarz 10 maja 2023 przez Dani Obywatel (1,450 p.)

Dziękuję bardzo (;

komentarz 10 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Ogólnie jak masz jakieś pytania do zadań z OIJ, to śmiało pisz. Przerobiłem prawie wszystkie, więc będę mógł coś tam raczej pomóc.

komentarz 10 maja 2023 przez Dani Obywatel (1,450 p.)
edycja 10 maja 2023 przez Dani

#include <bits/stdc++.h>
// #define ll long long
using namespace std;
vector<int> a;
vector<int> zlicz;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    long long n;
    cin >> n;
    int maxi = 0;
    for(int i=0;i<n;++i){
        int x;
        cin >> x;
        a.push_back(x);
        maxi = max(maxi,x);
    }
    zlicz.resize(maxi+5,0);
    int l=0,r=0;
    int s=5e5+5;
    while(r < n){
        zlicz[a[r]] += 1;
        while(zlicz[a[r]] == 3){
            s = min(s,r - l + 1);
            zlicz[a[l]] -= 1;
            ++l;
        }
        ++r;
    }
    if(s == 5e5+5)
        cout << "NIE" << '\n';
    else
        cout << s << '\n';
    return 0;
}

Właśnie robię zadanie lizak, którego podesłałeś mi, fajne zadanko. Napisałem kodzik wchodzi na 80 pkt, jednak w niektórych testach pokazuje, że przekroczyłem pamięć. Wiesz może co to dokładnie znaczy i jaki może być powód? Wydaje mi się, że wszystkim zmienne ustawiłem właściwie pod względem pojemności. Z góry dziękuję Tobie bardzo!

komentarz 10 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

maxi może być nawet 10^9 o ile dobrze pamiętam, zmień na mapę / unordered mape

komentarz 11 maja 2023 przez Dani Obywatel (1,450 p.)

Zmieniłem na mapę i działa! Dzięki. Ale zastanawia mnie czm ten vector nie działa?

1	komentarz 11 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.) element vectora ma powiedzmy, 4bajty pamięci pomnóż sobie 10^9 * 4, zamień na MB, i porównaj z limitem zadania.

odpowiedź 11 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Trochę pomyślałem i przypomniałem sobie jeszcze zadania:

EJOI: http://ejoi.org/wp-content/uploads/2017/09/count.pdf

z OIa: Wilcze doły, temperatura

Pokaż 10 poprzednich komentarzy

1	komentarz 15 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.) nie lepiej to napisac np. tak: for (int i = 0; i < n-2; ++i) { if (tab[i+2] - tab[i] <= 1) { wyn++; l += 2; } }