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

tak tylko dla pewności:

kandydaci na dni do zbiorów to takie dni, po których ginie jakis grzyb tak?

---

Tak, zakładając, że ten dzień to x, to sprawdzasz momenty x-1 oraz x (Ostatni przed tym jak ginie, to x-1) oraz x jest wtedy gdy już zginie. Nie opłaca Ci się sprawdzać np. x - 5, zamiast x - 1, jak do dnia x-1 rośnie,to dla x-5 napewno nie będzie lepszy, bo wartości są dodatnie.

---

oczywiście zakładając, że x-5 lub x-4 to nie kandydat, bo jeśli jest na wektorze x-4, to też je sprawdzisz, tylko osobno. Tylko musisz jeszcze zrobić if-a że gdy dzien jest 1, to żeby nie sprawdzać x-1, bo to dzień 0, a go nie możesz.

---

@polandonion, przeszło?

---

40%, ale chyba przez jakiś błąd w mojej implementacji

#include <bits/stdc++.h>
 
using namespace std;
 
struct Grzyb {
    int a, b, c;
};
 
Grzyb a[1000001];
vector <int> v;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i ++) {
    	cin >> a[i].a >> a[i].b >> a[i].c;

    	if (a[i].c != 1)
    		v.push_back(a[i].c - 1);
    }

    v.push_back(-1);
    sort(v.begin(), v.end());

    /* for (auto a : v)
    	cout << a << ' '; */

    long long sum = 0, dz = 1;
    for (int i = 1; i < v.size(); i ++) {
    	if (v[i] != v[i - 1]) {
    		long long su = 0;
    		for (int j = 1; j <= n; j ++) {
    			if (a[j].c > v[i])
    				su += a[j].a + v[i] * a[j].b;
	    	}

	    	if (su > sum)
	    		sum = su, dz = v[i];
    	}
    }
    cout << dz;
}

PS, napisalem sort() a nie couting, zeby sprawdzic tylko poprawnosc kodu

---

To wydaje mi się, że masz O(N^2), cały mój pomysł polegał, na tym, żeby przyśpieszyć linijki od 36 do 39 i robić to w czasie stałym, O(1). Naliczasz na poszątku pętlą taką samą sumę wszystkich, i potem jak sprawdzasz moment x, gdzie element x ginie, to odejmujesz to o ile rośnie element x od sumy, a tą sumę mnożysz razy d_i. W ten sposób dostaniesz O(N)

---

a czemu mam sprawdzac dni x oraz x - 1 (przy zalozeniu, ze x to dzien w ktorym ginie jakis grzyb)?

nie wystarczy sprawdzac po prostu x - 1?

---

aaa no tak, lekki mistake

---

@polandonion, 

Podsumowująć

1 - Nawet nie trzeba robić counting sorta(przechodzi na 100 zwykły sort z STL-a O(N lg N))

2 - Jednak trzeba sprawdzać moment x, a nie tylko x-1(spróbuj znaleźć przykład dlaczego).

3 - Nie wiem, jak to lepiej ci wytłumaczyć. Napisałem taki kod, tylko jest baaaardzo ważna rzecz, całkowicie zrozum ten kod, (jak nie będziesz czegoś rozumiał to pisz!!!) i dopiero po całkowitym zrozumieniu zacznij pisać, bez patrzenia na niego. Przepisywanie nic nie daje, a tak jak zrozumiesz go całkowicie to moim zdaniem da ci tyle, jak byś normalnie zrobił sam zadanie, jak czegoś nie wiesz, to pytaj!!!, oczywiście jak zaczniesz pisać, i skapniesz się, że np. źle sobie myślałeś, to wróć do niego, bez spiny.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

struct Grzyb_stat
{
    ll masa;
    ll przyrost;
};

int n = 0, m = 0, p = 0, d = 0;
ll suma_zbiorow = 0, suma_masa_zebranych = 0, max_wyn = -1e18, max_wyn_dzien = -1, wyn = 0;
vector<int> kandydaci;
vector<Grzyb_stat> grzyby(1e5+1,{0,0}); // 1e5, bo max d_i to 1e5

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

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> m >> p >> d;
        kandydaci.push_back(d);
        grzyby[d].masa += m;
        grzyby[d].przyrost += p;
        suma_masa_zebranych += m;
        suma_zbiorow += p;
    }
    sort(kandydaci.begin(), kandydaci.end());
    for (int i = 0; i < n; ++i)
    {
        int spr = kandydaci[i]; // Sprawdzany dzien x.

        if (spr != 1) // Jesli jest dzien 1, to dzien 0 nie moze byc wynikiem!
        {
            // Sprawdzamy dzien x-1.
            wyn = suma_masa_zebranych + suma_zbiorow * (spr-1);
            if (wyn > max_wyn)
            {
                max_wyn = wyn;
                max_wyn_dzien = spr-1;
            }
        }

        suma_masa_zebranych -= grzyby[spr].masa;
        suma_zbiorow -= grzyby[spr].przyrost;

        // Sprawdzamy dzien x.
        wyn = suma_masa_zebranych + suma_zbiorow * spr;
        if (wyn > max_wyn)
        {
            max_wyn = wyn;
            max_wyn_dzien = spr;
        }
        grzyby[spr] = {0,0};
    }

    cout << max_wyn_dzien << '\n';

    return 0;
}

 

---

jeszcze nie patrzyłem na twoj kod, ale cos takiego wyklikalem i mam 50% i nie ma przekroczen czasu

#include <bits/stdc++.h>

using namespace std;

struct Grzyb {
	int a, b, c;
};

vector <int> v;
Grzyb a[1000001];
pair <bool, int> sor[100001];

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

    int n;
    cin >> n;

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

    	sor[a[i].c].first = 1; // sortuje kandydatow na dni (counting sort)
        sor[a[i].c].second = i; // zapisuje nr. grzyba, ktory ginie

    	su += a[i].a; // inicjuje sume poczatkowa
    	prz += a[i].b; // inicjuje przyrost
    }

    long long sum = 0, dz = 1;
    for (int i = 1; i <= 1e5; i ++) {
        if (sor[i].first == 1) {
            su += i * prz;

            if (su > sum)
                sum = su, dz = i;

            su -= a[sor[i].second].a + i * prz;

            prz -= a[sor[i].second].b;
        }
    }

    cout << dz;
}

 

---

jakie testy dostajesz WA?

---

• 3 wiersz 1: wczytano '99999', a oczekiwano '79999'
• 5 wiersz 1: wczytano '95181', a oczekiwano '57731'
• 8 wiersz 1: wczytano '49384', a oczekiwano '24726'
• 9 wiersz 1: wczytano '79966', a oczekiwano '40613'
• 10 wiersz 1: wczytano '98539', a oczekiwano '50455'

---

Bład jest napewno taki, że może być kilka grzybów, które giną w dniu x. Pozatym to wygląda podobnie co moje. Zauważ, że zamiast znaczyć gdzie jest grzyb możesz zrobić sobie vector dla dnia x o strukturze: suma_przyrostu_w_dniu_x oraz suma_masa_w_dniu_x (lepiej nazwij, to taki przykład) a ogólnie twoje rozwiazanie jest trochę czytelniejsze, korzystasz z tego, że max dni jest <= 10^5, więc wystarza przejśc naiwnie po wszystkich dniach. Mój algorytm zadziała dla dowonego d_i.

---

Dzieki za pomoc, ale ide spac bo zmeczony jestem i nie ma sensu pisac kodu naprzemiennie ziewajac, wiec wroce rano i dokonczymy watek :D

---

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