Szczegółowe omówienie zadania Diamond Collector:

Link do powyższego omówienia zadania Diamond Collector: https://youtu.be/Jir3J__TIQs?t=1056
Omówienie kodu zadania Diamond Collector: https://youtu.be/Jir3J__TIQs?t=3732

Link do treści zadania Diamond Collector: http://www.usaco.org/index.php?page=viewproblem2&cpid=643

Zadanie Diamond Collector to trudniejsze zadanie ćwiczeniowe wykorzustujące algorytm gąsienicy:

• Wyjaśnienie algorytmu gąsienicy: https://youtu.be/JggX75UKThc?t=1830
• Wizualizacja gąsienicy: https://youtu.be/JggX75UKThc?t=1000
• Złożoność gąsienicy: https://youtu.be/JggX75UKThc?t=2990
• Złożoność algorytmu omówionego w zadaniu: https://youtu.be/Jir3J__TIQs?t=3572

Zadanie Diamond Collector pochodzi z dywizji Silver Amerykańskiej Olimpiady Informatycznej USACO – odpowiednika naszej Olimpiady Informatycznej Juniorów: https://youtu.be/KI7un-HU_Hk?t=49
Daje piękny wpis do CV: https://youtu.be/P2sLFZBjOmM?t=7223
Dlaczego warto brać udział w Amerykańskiej Olimpiady Informatycznej USACO? https://youtu.be/K7fZfJ8nN6A?t=6848
Co to jest USACO? https://youtu.be/nvA92I5nU0c?t=1414

–
Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/
Zajęcia: : https://oki.org.pl/harmonogram-zajec/

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109

–
Kod C++ programu Diamond Collector, który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50*1000 + 7;

int wielkosci[MAXN];
// dlugoscGasienicy[i] = najdluzsza dlugosc gasienicy o ogonie w i
int dlugoscGasienicy[MAXN];
// najwieksze[i] = max(dlugoscGasienicy[i], dlugoscGasienicy[i+1], ...)
int najwieksze[MAXN];

int main()
{
	ifstream in("diamond.in");
	ofstream out("diamond.out");

	int n, k;
	in >> n >> k;
	for (int i = 1; i <= n; ++i)
		in >> wielkosci[i];
	sort(wielkosci+1, wielkosci+n+1);

	int lewo = 0;
	int prawo = 0;
	while (lewo < n) {
		while (prawo <= n && (wielkosci[prawo] - wielkosci[lewo + 1] <= k)) {
			++prawo;
		}
		++lewo;
		// jezeli jestesmy tutaj - czyli wyszlismy z while, to znaczy
		// ze poprzednia glowa gasienicy (prawo - 1) byla ok - zapisujemy
		dlugoscGasienicy[lewo] = (prawo - 1) - lewo + 1;
	}

	// liczenie maximum na sufiksie
	for (int i = n; i >= 1; --i) {
		// wybieram wieksza opcje z: mojej wartosci, poprzedniego maximum
		najwieksze[i] = max(najwieksze[i + 1], dlugoscGasienicy[i]);
	}

	int wynik = 0;
	lewo = 0;
	prawo = 0;
	while (lewo < n) {
		while (prawo < n && (wielkosci[prawo] - wielkosci[lewo + 1] <= k)) {
			++prawo;
			if (wielkosci[prawo] - wielkosci[lewo + 1] <= k) {
				// wynik to moja aktualna dlugosc + najdluzsza gasienica,
				// ktora zaczela sie po mnie (ktorej ogon jest za moja glowa)
				wynik = max(prawo - lewo + najwieksze[prawo + 1], wynik);
			}
		}
		++lewo;
	}
	out << wynik << '\n';
	return 0;
}

–
Kod Python programu Diamond Collector, który otrzymuje 100%:

wielkosci = [0]

wejscie = open("diamond.in", "r")
n, k = map(int, wejscie.readline().split())

for i in range(n):
	wielkosci.append(int(wejscie.readline()))
wielkosci.sort()

# dlugoscGasienicy[i] = najdluzsza dlugosc gasienicy o ogonie w i
dlugoscGasienicy = (n+2) * [0]

lewo = 0
prawo = 0
while (lewo < n):
	while (prawo <= n and (wielkosci[prawo] - wielkosci[lewo + 1] <= k)):
		prawo = prawo + 1

	lewo = lewo + 1
	# jezeli jestesmy tutaj - czyli wyszlismy z while, to znaczy
	# ze poprzednia glowa gasienicy (prawo - 1) byla ok - zapisujemy
	dlugoscGasienicy[lewo] = (prawo - 1) - lewo + 1

# najwieksze[i] = max(dlugoscGasienicy[i], dlugoscGasienicy[i+1], ...)
najwieksze = (n+2) * [0]
for i in range(n-1, 0, -1):
	najwieksze[i] = max(najwieksze[i + 1], dlugoscGasienicy[i])

wynik = 0
lewo = 0
prawo = 0
while (lewo < n):
	while (prawo < n and (wielkosci[prawo] - wielkosci[lewo + 1] <= k)):
		prawo = prawo + 1
		if (wielkosci[prawo] - wielkosci[lewo + 1] <= k):
			# wynik to moja aktualna dlugosc + najdluzsza gasienica,
			# ktora zaczela sie po mnie (ktorej ogon jest za moja glowa)
			wynik = max(prawo - lewo + najwieksze[prawo + 1], wynik)

	lewo = lewo + 1

open("diamond.out", "w").write(str(wynik))