przekroczenie limitu pamięci,wektory

Question

Problem z pamięcią :/ zastanawiam się czy tą wersję kodu da się jakoś "odchudzić" czy trzeba kombinować z inną strukturą? 

#include <iostream>
#include <vector>
using namespace std;
vector <char> Z;
vector <vector <char> > M; //M [k][n]
short int k; //zaprzęgi
int n; //wagoniki w  zaprz
int p;
short int T;
//int tmp[10000000];
//{1,1,1,2,2,2,3,3,3,2,1,1,3,3,2,1,2,3};
/*void display()
{
 for (int i=0;i<k;i++) //pętla po zaprzegach
 {
     for (int j=0;j<n;j++)cout<<M[i][j]<<" "; //pętla po wagonikach
     cout<<endl;
 }
}*/
bool zaladuj (int a)
{
    for (int j=0;j<k;j++)
    {
        if(M[j][a-1]=='0')
        {
            M[j][a-1]='1';
            return true;
        }

    }
    return false;
}
bool zaparkuj()
{
    bool czy_wag_pusty=false;
    for (int j=0;j<k;j++)
    {
        if (M[0][j]=='0')
        {
            czy_wag_pusty=true;
            j=k;
        }
    }
    if(czy_wag_pusty==false)
    {
        M.erase(M.begin());
        M.push_back(Z);
    }
}
bool wynik;
int u;
int main()
{
    cin>>T;
    for(int t=0;t<T;t++)
    {
          cin>>n>>k>>p;
          /*for  (int r=0;r<p;r++)
          {
              cin>>tmp[r];
          }*/
            Z.resize(n,'0');
            M.resize(k,Z);
           // display();
            for(int i=0;i<p;i++)
            {
                cin>>u;
                wynik=zaladuj(u);
                if (wynik==false)
                    {
                        i=p;
                    }
                zaparkuj();
            }
            if (wynik==false) cout<<"NIE";
            else cout<<"TAK";
            Z.clear();
            M.clear();
    }

return 0;}

Opis

Na kilka godzin przed dniem zero elfy postanowiły zastrajkować i porzuciły swoje stanowiska pracy. Na placu boju pozostał tylko jeden elf - Elf Łamistrajk. Pracy jest dużo, czasu mało, a sanie same się nie załadują. Trzeba robić to szybko, a nie jest to takie proste. W magazynie znajduje się k zaprzęgów reniferów, każdy wyposażony w n wagoników (ponumerowanych od 1 do n). Z taśmy produkcyjnej spadają jeden po drugim prezenty. Każdy prezent jest dobrze opisany, w szczególności posiada numer wagonika, w którym powinien się znaleźć. Każdy wagonik mieści dokładnie jeden prezent. Cel każdego wagonika wyznaczony jest przez jego numer. Nie jest więc ważne, do którego z zaprzęgów trafi prezent. Gdy wszystkie wagoniki z zaprzęgu zostaną zapełnione, renifer odjeżdża, a w jego miejsce natychmiast pojawia się nowy. Renifery z saniami nie odjadą dopóki wszystkie wagoniki nie będą zapełnione prezentami. Problem pojawia się wtedy, gdy nasz Elf Łamistrajk wypełni wszystkie wagoniki o danym numerze, a z linii wypadnie kolejny prezent o tym numerze. Wtedy nie ma co z nim zrobić. Nie można go nigdzie odłożyć ponieważ istnieje ryzyko że zamarznie na ziemi i zabawka w środku się popsuje. Nie można go też nikomu przekazać bo nie ma nikogo do pomocy. W tej sytuacji kolejne paczki spadną i się zepsują, bo Elf mając zajęte ręce nie będzie w stanie ich złapać. Czy Elfowi Łamistrajkowi uda się uratować wszystkie prezenty i wysłać je do grzecznych dzieci? Gdy ostatni prezent wypadnie z taśmy, przychodzi Mikołaj i woła wio, a wszystkie renifery z magazynu, obojętnie czy są w pełni zapakowane prezentami czy nie, wyruszają w świat. Jeśli do tego czasu Elf Łamistrajk był w stanie rozmieścić wszystkie prezenty, wówczas odnosi sukces. W przeciwnym przypadku oczywiście ponosi wielką porażkę.

Specyfikacja wejścia

W pierwszej linii wejścia znajduje się liczba testów T (1 <= T <= 10). W kolejnych T liniach następuje opis zestawu testowego. Każdy test rozpoczyna się od liczb całkowitych n, k (1 <= n <= 10^5 , 1 <= k <= 100) określających odpowiednio ile wagoników jest doczepionych do każdego renifera oraz rozmiar magazynu. Następnie podana jest liczba p (1 <= p <= 10^7 ) określająca liczbę prezentów, którą Elf Łamistrajk musi umieścić w wagonikach. W ostatnim wierszu zestawu testowego znajduje się opis prezentów wypadających z taśmy. Następne p liczb (z zakresu od 1 do n) wskazuje adresy paczek w kolejności ich zwracania

Specyfikacja wyjścia

Dla każdego zestawu testowego wypisz TAK jeżeli uda się uratować wszystkie prezenty oraz NIE w przeciwnym przypadku.

Przykład

3

1 2

3

1 1 1

2 2

3

1 1 1

3 3

12

1 1 1 2 2 2 3 3 3 2 1 1 3 3 2 1 2 3

Odpowiedź

TAK

NIE

TAK

Wyjaśnienie testu nr 2 Pierwsze dwa prezenty trafią do reniferów o numerach 1 i 2. Ponieważ wagoniki nr 2 będą puste, zatem żaden z nich nie odjedzie z magazynu. Elf Łamistrajk nie będzie miał więc gdzie zmieścić trzeciego prezentu przeznaczonego do pierwszego wagonika

Comments

Jedna sprawa, to ten kod się w ogóle nie kompiluje.

Druga, że jest napisany jakbyś nie chciał żeby ktokolwiek go zrozumiał :(

---

aaa wiem, błąd mógł być po zostało z poprzedniej wersji kodu "wynik=zaladuj(temp [u])" zamiast "wynik=zaladuj(u)" po poprawieniu powinno działać. Jak coś wytłumaczyć to pytaj.

---

W najgorszym wypadku stworzysz wektor o wymiarach 100x10^5 co prawdopodobnie wychodzi poza limit pamięci. Obawiam się też że złożoność Twojego rozwiązania nie jest zbyt dobra. Tutaj najprościej jest zastosować zwykle drzewo przedziałowe, które dodaje 1 w punkcie i podaje minimum na przedziale

---

ajj czyli pewnie będzie trzeba od nowa napisać cały kod, no nic, dzięki

Answer 1

Nie musisz mieć wektora dla każdego renifera. Możesz mieć jeden wektor na wszystkie renifery, który będzie przechowywał informację ile jest prezentów we wszystkich wagonikach o danym numerze(niech nazywa się renifery). I będzie potrzebny jeszcze drugi wektor, w którym przechowamy informację o liczebności elementów tego pierwszego(liczebność).

Np. jeśli n = 3, k = 3 i w wagonikach o numerach 1 jest 2 prezenty, w wagonikach o numerach 2 jest 1 prezent i w wagonikach o numerach 3 też jest 1 prezent, to wektor renifery={2,1,1}, a wektor liczebność={0, 2, 1}, bo nie ma w wektorze renifery liczb 0, jest 2 jedynki i 1 dwójka.

Mając te 2 wektory możemy łatwo obsłużyć dodanie nowego prezentu. jeśli widzimy, że trzeba dodać prezent x to wykonujemy następujące operacje:

int tmp = renifery[x] // zapisujemy ile tu juz było prezentów
renifery[x]++; // dorzucamy prezent;
// w wektorze renifery tak jakby usuwamy jedno tmp i dodajemy tmp+1 w jego miejsce
// odpowiednio aktualizujemy liczebność
liczebność[tmp]--;
liczebność[tmp+1]++; 

Co robimy jeśli jakiś renifer odjedzie? Nic. W tablicy renifery będzie też informacja o prezentach, które już opuściły warsztat. Jeśli w wektorze renifery najmniejsza wartość to np. 3, to wiemy, że na każdy adres mamy co najmniej 3 prezenty, więc wiemy, że 3 renifery mogły zostać załadowane i odjechać. Więc gdy w którymś momencie różnica wartości minimalnej i maksymalnej przekroczy k, to możemy odpowiedzieć, że nie da się dostarczyć prezentów, w przeciwnym przypadku da się to zrobić. Teraz, żeby szybko znaleźć minimum i maksimum w reniferach użyjemy wektora liczebność. Minimum w wektorze renifery, to najmniejszy indeks w liczebności, poz którym jest wartość różna od zera.

Np. dla wektora liczebność={0,0,0,0,1,0,2,3,4,0,1,0,0,0}, wiemy, że minimum w wektorze renifery to 4 a maksimum to 10 (liczymy od 0). Ale przeszukiwanie wektora liczebność za każdym razem też jest bardzo wolne. Ale w wektorze liczebność zawsze "przenosimy" jedną liczbę o 1 w górę, (jak w kodzie wyżej). Więc minimum i maksimum również może zmienić się tylko o 1. Możemy zapisać sobie w 2 dodatkowych zmiennych aktualne minimum i maksimum. Gdy liczebność[minimum] spadnie do 0 robimy minimum++, a gdy liczebność[maksimum+1] zwiększy się z 0 do 1 to również maksimum++.

Teraz gdy maksimum - minimum > k to wypisujemy, że się nie da, a gdy dojdziemy do końca to ok.

Rozwiązanie jest już dobre, ale jest jeszcze jeden haczyk. "wektor" liczebność jak go nazywałem musi mieć wielkość co najmniej 10^7 bo tyle może być prezentów jednego typu. Czyli na razie algorytm nie daje żadnego zysku pamięci. Ale można zauważyć, że liczebność zawsze jest postaci {dużo zer ... 0, jakieś liczby , 0 ... dużo zer} i długość fragmentu "jakieś liczby" jest <= k które jest co najwyżej 100. Więc można zasymulować ten wektor na bardzo małej tablicy lub łatwiej na std::map usuwając miejsca, gdzie mamy 0. Teraz pamięć powinna być ok

Comments

niestety to rozwiązanie nie przeszło :/

---

Możesz podać więcej szczegółów, albo wkleić kod?

---

#include <iostream>
#include <vector>
using namespace std;
vector <string> M; //M [k][n]
string S;
short int k; //zaprzęgi
int n; //wagoniki w  zaprz
int p;
short int T;
//int tmp[10000000];
//{1,1,1,2,2,2,3,3,3,2,1,1,3,3,2,1,2,3};
/*void display()
{
 for (int i=0;i<k;i++) //pętla po zaprzegach
 {
     for (int j=0;j<n;j++)cout<<M[i][j]<<" "; //pętla po wagonikach
     cout<<endl;
 }
}*/
bool zaladuj (int a)
{
    for (int j=0;j<k;j++)
    {
        if(M[j][a-1]=='0')
        {
            M[j][a-1]='1';
            return true;
        }

    }
    return false;
}
bool zaparkuj()
{
    bool czy_wag_pusty=false;
    for (int j=0;j<k;j++)
    {
        if (M[0][j]=='0')
        {
            czy_wag_pusty=true;
            j=k;
        }
    }
    if(czy_wag_pusty==false)
    {
        M.erase(M.begin());
        M.push_back(S);
    }
}
bool wynik;
int u;
int main()
{
    cin>>T;
    for(int t=0;t<T;t++)
    {
          cin>>n>>k>>p;
          /*for  (int r=0;r<p;r++)
          {
              cin>>tmp[r];
          }*/
            S.assign(n,'0');
            M.assign(k,S);
           // display();
            for(int i=0;i<p;i++)
            {
                cin>>u;
                wynik=zaladuj(u);
                if (wynik==false)
                    {
                        i=p;
                    }
                zaparkuj();
            }
            if (wynik==false) cout<<"NIE";
            else cout<<"TAK";
           // M.clear();
    }

return 0;}

trochę zmodyfikowana wersja, nawet na jednym wektorze, wydaje mi się że te rozwiązania oszczędzają na czasie ale na pamięci nie za bardzo :/ 

---

Ale tutaj nadal trzymasz informację o poszczególnych zaprzęgach. W moim rozwiązaniu chodzi o to, że masz vector<int> gdzie dla danego typu prezentów mamy tylko informację ile ich jest w sumie we wszystkich zaprzęgach, czyli mamy vector<int> długości n. Dokładna informacja gdzie są rozmieszczone prezenty nie jest potrzebna, żeby rozwiązać to zadanie