• 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

Aruba Cloud - Virtual Private Server VPS
0 głosów
537 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 (195,240 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 (195,240 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 (57,400 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 (57,400 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 (195,240 p.)

@Whistleroosh, 

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

A std::set nie?

komentarz 25 stycznia 2023 przez Whistleroosh Maniak (57,400 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ź 529 wizyt
0 głosów
1 odpowiedź 170 wizyt
0 głosów
1 odpowiedź 346 wizyt
pytanie zadane 19 maja 2023 w C i C++ przez Dani Obywatel (1,450 p.)

93,324 zapytań

142,323 odpowiedzi

322,390 komentarzy

62,653 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

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...