Zadanie Grzybki ILOCAMP

Question

Siema, pomoze ktos z kodem?

Najprawdopodobniej robie jakims dziwnym sposobem dla Was i mam prosbe o ewentualne nakierowanie.

zadanie: https://szkopul.edu.pl/problemset/problem/UDIADIj0TZR7zMUXeF6XlM1T/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

struct Grzyb {
	int mas, del, dni;
	// mas - masa grzyba, del - przyrost, dni - ilosc dni zycia
};

Grzyb arr[1000001];
unordered_map <int, pair <long long, int>> m;

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

	int n;
	cin >> n;

	int maxDz = 0, dz = 1;
	// dz - wynik (optymalny dzien)

	long long sum = 0, su = 0, prz = 0;
	// sum - zmienna pomocnicza

	for (int i = 1; i <= n; i ++) {
		cin >> arr[i].mas >> arr[i].del >> arr[i].dni;
		// wczytanie danych

		su += arr[i].mas;
		// suma grzybow w dniu 0.

		maxDz = max(maxDz, arr[i].dni);
		// jaki jest max dzien do sprawdzenia w symulacji

		m[arr[i].dni].first += (arr[i].dni - 1) * arr[i].del + arr[i].mas;
		// suma (mas poczatkowych oraz doladowywanych
		// z dnia na dzien), ktore umieraja w dniu arr[i].dni (*)

		m[arr[i].dni].second += arr[i].del;
		// suma mas grzybow, ktore umieraja w dniu arr[i].dni (**)

		prz += arr[i].del;
		// przyrost z dnia na dzien
	}

	for (int i = 1; i <= maxDz; i ++) {
		su += prz;
		// za kazdym razem dodaje przyrost

		if (m.find(i) != m.end())
			su -= m[i].first + m[i].second, prz -= m[i].second;
			// jezeli jakas ryba/ryby umiera w dniu i, to od su odejmuje
			// (*) oraz (**), jednoczesnie aktualizujac przyrost

		if (su > sum)
			sum = su, dz = i;
			//sprawdzam, czy aktualna suma nie jest najlepsza i aktualizuje sume i dzien
	}

	cout << dz;// << ' ' << sum;
}

 

Answer 1

A to tu nie wchodzi jakieś proste O(N)?

Sortujesz counting sortem(jak posortujesz normalnie, to dostaniesz O(N lg N)) kandydatów na dzień zbioru grzybów, i sprawdzasz wszystkich kandydatów. Jak sprawdzasz pojedyńczego kandydata, to zakładając, że jest to moment x, to sprawdzasz momenty x oraz x-1(przed i po zebraniu), trzymasz zmienną suma wszystkich o ile wzrasta. Sumujesz liniowo, naiwnie z wejścia i mnożysz przez ile dni, na bierząco. Jeżeli zdejmujesz element Z, to odejmujesz od sumy i będziesz mnożył mniej grzybów.

Wydaje się to takie wmiarę intuicyjne.

Myślę, że jakaś podpucha autora polegała na tym, że N <= 10^6 i ktoś nie zauważy, że d_i <= 10^5 i zrobi sorta w O(N lg N) i nie przejdzie mu czas, tylko np wejdzie na jakieś 80pkt.

Btw. Wczytując d_i odjałbym na starcie dla czytelności kodu 1, bo tam jak np d_i = 4, to dodaje do dnia 3, a nie 4. Ale to już kwestia implementacji

Abstrahując od tego, że poleciłbym najpierw napisać dla treningu bruta, gdzie dla każdego kandydata sprawdzasz naiwnie. O(N^2)

Comments

Wiesz co, myślałem, że mój sposób jest jakiś zwalony, ale okazało się, że C++ czasami dziwnie konwertuje int'a na long long'a i najprawdopodobniej podczas jakiejś konwersji najpierw zamienił mi jakąś zmienną na int'a a dopieo potem na long long'a i dlatego wynik ucierpiał. Teraz wszystko działa, lecz nie na 100%, tylko 99. Jeden test przekracza czas o 0.01s.

Przyznam szczerze, że nie patrzyłem w twój kod, bo próbowałem zostać przy mojej wersji i opłaciło się. Oczywiście Twój może działać szybciej, ale nie zminia to faktu, że jakoś wolę prostsze implementacje.

A, no i dodam, że nie trzeba zapamiętywać dni x oraz x - 1 w jakimś wektorze. Przeprowadziłem pełną symulację i mój program działa dobrze. :D

Tak czy siak, dzięki za poświęcony czas nt. tego zadanka.

Wzorcówka:

#include <bits/stdc++.h>

using namespace std;

struct Grzyb {
	long long a, b, c;
    // a - masa, b - przyrost, c - dni zycia
};

unordered_map <int, pair <long long, long long>> m;
Grzyb a[1000001];

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

    int n;
    cin >> n;

    long long su = 0, prz = 0, mxDz = 0;
    for (int i = 1; i <= n; i ++) {
    	cin >> a[i].a >> a[i].b >> a[i].c;

        mxDz = max(mxDz, a[i].c);

        su += a[i].a; // suma poczatkowa
        prz += a[i].b; // przyrost poczatkowy

        m[a[i].c].first += (a[i].c - 1) * a[i].b + a[i].a;
        m[a[i].c].second += a[i].b;
    }

    long long sum = 0, dz = 1;
    for (int i = 1; i <= mxDz; i ++) {
        su += prz;
        if (m.find(i) != m.end())
            su -= m[i].first + m[i].second, prz -= m[i].second;

        //cout << su << ' ';
        if (su > sum)
            sum = su, dz = i;
    }

    cout << dz;
}

---

Masz rację, nie trzeba trzymać kandydatów w vectorze, bo d_i <= 10^5, więc twój kod jest lepszy niż mój (robią praktycznie to samo, tylko że mój ma kandydatów i sprawdza x i x-1, a twój korzysta z tego, że moze sprawdzić wszystkie d_i). Ale zwróc uwage, że twój kod nie zadziała dla d_i <= 10^9, a mój tak, a mają taką samą złożonność

---

Teraz wszystko działa, lecz nie na 100%, tylko 99. Jeden test przekracza czas o 0.01s.

---

w strukturze grzyb masz long longi, zmien na int-y. Chyba przyspieszy to wczytywanie. usun long longi, tam gdzie ich nie potrzebujesz

---

przyspieszyło o 0.25s, co wystarczyło do uzyskania setki. Dzięki wielkie