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

Zadanie Promocja finał OI, optymalizacja pamięci - set

VPS Starter Arubacloud
0 głosów
243 wizyt
pytanie zadane 24 stycznia 2023 w C i C++ przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Mam problem z optymalizacją tego zadania z finału 7 OI-a: https://szkopul.edu.pl/problemset/problem/VD_bKhKPiYjm8uq-R8O1r88h/site/?key=statement

Kod jest bardzo prosty. Oprócz wczytania danych jest dokładnie 5 linii.

#include <iostream>
#include <set>

using namespace std;
typedef long long ll;

int n = 0, k = 0, wczytana_liczba = 0;
ll wyn = 0;
multiset<int> S;

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

    cin >> n;
    while(n--)
    {
        cin >> k;
        while(k--)
        {
            cin >> wczytana_liczba;
            S.insert(wczytana_liczba);
        }
        wyn += *S.rbegin() - *S.begin();
        S.erase(S.lower_bound(*S.begin()));
        S.erase(S.lower_bound(*S.rbegin()));
    }
    printf("%lld",wyn);
    return 0;
}

Przechodzi tylko na 80pkt, wywala się pamięć. Pewnie trzeba dobrać jakąś lepszą strukturę danych, ma ktoś jakiś pomysł?

Z góry dziękuję za pomoc i poświęcony czas.

komentarz 24 stycznia 2023 przez j23 Mędrzec (194,920 p.)

wywala się pamięć.

Co to znaczy? Jakiś błąd wykonania, czy po prostu program przekracza limit?

komentarz 24 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
dostępna pamięc na zadanie to 32MB, a program przekracza limit.
komentarz 24 stycznia 2023 przez j23 Mędrzec (194,920 p.)
Próbowałeś użyć wektora?
komentarz 24 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
No tak wsumie, sobie myślę, że na rozwiązanie tego w dobrej pamięci są 2 opcje:

1 - To co ja zrobiłem z drzewami przedziałowymi punkt-przedział min i max. O(n log n)

2 - Zaimplementować kopiec binarny i też by przeszło w O(n log n).

Set z tego co wyczytałem to jest bardzo pamieciożerny. To zadanie jest z finału OI-a a jest bardzo proste.

I kopiec by działał jak max_val > 10^6, a to działa tylko dlatego, bo max val <= 10^6

1 odpowiedź

0 głosów
odpowiedź 24 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Przeszło już na 100pkt w O(n log n), korzystając z tego, że max val <= 10^6 zrobiłem drzewo przedziałowe minów i drzewo przedziałowe maxów i pamięć jest liniowa, bo drzewo przedziałowe to vector. Kod

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

int n = 0, k = 0, wczytana_liczba = 0, base = 0, rozmiar_drzewa = 0, min_zap = 0, max_zap = 0;
ll wyn = 0;
vector<int> ile(1e6+1,0);
vector<int> drzewo_przedzialowe_max;
vector<int> drzewo_przedzialowe_min;

void update_min(int v, int val)
{
    v += base;
    drzewo_przedzialowe_min[v] = val;
    v /= 2;
    while (v > 0)
    {
        drzewo_przedzialowe_min[v] = min(drzewo_przedzialowe_min[v * 2], drzewo_przedzialowe_min[v * 2 + 1]);
        v /= 2;
    }
}

void update_max(int v, int val)
{
    v += base;
    drzewo_przedzialowe_max[v] = val;
    v /= 2;
    while (v > 0)
    {
        drzewo_przedzialowe_max[v] = max(drzewo_przedzialowe_max[v * 2], drzewo_przedzialowe_max[v * 2 + 1]);
        v /= 2;
    }
}

int querry_min(int l, int p)
{
    l = l + base - 1;
    p = p + base + 1;
    int res = 1e6+5;
    while(l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res = min(res,drzewo_przedzialowe_min[l+1]);
        if (p % 2 == 1)
            res = min(res, drzewo_przedzialowe_min[p-1]);
        l /= 2;
        p /= 2;
    }
    return res;
}

int querry_max(int l, int p)
{
    l = l + base - 1;
    p = p + base + 1;
    int res = -1e6+5;
    while(l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res = max(res,drzewo_przedzialowe_max[l+1]);
        if (p % 2 == 1)
            res = max(res, drzewo_przedzialowe_max[p-1]);
        l /= 2;
        p /= 2;
    }
    return res;
}

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

    base = (1 << ((int)ceil((double)log2(1e6+1))));
    rozmiar_drzewa = base * 2;
    drzewo_przedzialowe_min.assign(rozmiar_drzewa,1e6+5);
    drzewo_przedzialowe_max.assign(rozmiar_drzewa,0);

    cin >> n;
    while(n--)
    {
        cin >> k;
        while(k--)
        {
            cin >> wczytana_liczba;
            ile[wczytana_liczba]++;
            update_min(wczytana_liczba,wczytana_liczba);
            update_max(wczytana_liczba,wczytana_liczba);
        }
        max_zap = querry_max(1,1e6);
        //cout << "MAX ZAP: " << max_zap << endl;
        ile[max_zap]--;
        if (ile[max_zap] == 0)
        {
            update_max(max_zap,0);
            update_min(max_zap,1e6+5);
        }
        min_zap = querry_min(1,1e6);
        ile[min_zap]--;
        if (ile[min_zap] == 0)
        {
            update_max(min_zap,0);
            update_min(min_zap,1e6+5);
        }
        wyn += max_zap - min_zap;
        //cout << "Wyn:" << wyn << endl;
    }
    printf("%lld",wyn);
    return 0;
}

 

komentarz 24 stycznia 2023 przez Whistleroosh Maniak (56,900 p.)
Można też zwykłą mapą zrobić
komentarz 24 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
A mapa ma mniejszą pamięc niż set?
komentarz 24 stycznia 2023 przez Whistleroosh Maniak (56,900 p.)
Powinna mieć mniej więcej taką samą pamięć. Ale przynajmniej redukuje duplikaty i może to pomogło
komentarz 24 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Mapa też wchodzi na 100(pamięc spoko), z czasami praktycznie takimisamymi jak drzewo przedziałowe. W niektórych testach minimalnie gorzej, w niektórych minimalnie lepiej. Wniosek taki, że gdy nie trzeba robić żadnego find-a albo coś takiego, to lepiej użyć mapy.

Zauważyłem, że na OI-u mają taki bardzo dziwny zwyczaj, że jak nie zależy na pamięci to dają np 1GB, 512MB, 256MB, 128MB albo coś takiego, a jak zależy to dają np 64MB, 32MB itp. xD
komentarz 25 stycznia 2023 przez j23 Mędrzec (194,920 p.)

@Whistleroosh, 

Ale przynajmniej redukuje duplikaty i może to pomogło

A std::set nie?

komentarz 25 stycznia 2023 przez Whistleroosh Maniak (56,900 p.)
Racja, mówiłem to w odniesieniu do multiseta użytego w zadaniu.
komentarz 27 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@pasjonat_algorytmiki, 

btw, bardzo podobne zadanie na drzewo punkt-przedział po wartościach: 

https://sio2.mimuw.edu.pl/c/zwo21/p/naj-cpp/

Bardzo polecam.

Podobne pytania

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

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!

...