Pomoć oko zadatka Krompir (Okružno 2017)

Pitanja i problemi
1

Pitanje ili opis problema

Pokušao sam da rešim sledeći zadatak medjutim nisam uspeo i imam nekoliko pitanja:
Zašto su mi testcases uglavnom TLE ?
Kako da uspešno rešim zadatak ?

  • Kako da napravim matricu koja ispunjava ograničenja ?
  • Kako da proverim da li je moj algoritam validan i odredim njegovu složenost ? ( I na osnovu nje uvidim da li će ispuniti vremensko ograničenje)

Ovo je kod:
#include iostream // znakovi < i > su prisutni
#include vector

using namespace std;

int main()
{
vector Redovi;
vector Kolone;

int DimenzijaN;
int BrojPocKrompiraM;
cin >> DimenzijaN >> BrojPocKrompiraM;
int PoljeKrompira[505][505];

for (int i = 0; i < DimenzijaN; ++i)
{
	for (int j = 0; j < DimenzijaN; ++j)
	{
		PoljeKrompira[i][j] = 0;
	}
}

for (int i = 0; i < BrojPocKrompiraM; ++i)
{

	int x, y;
	cin >> x;
	cin >> y;

	PoljeKrompira[x-1][y-1] = 1;
}

int predhodni=-1;
int predhodni2 = -1;
for (int i = 0; i < DimenzijaN; ++i) // for every column do few rows
{
	for (int j = 0; j < DimenzijaN; ++j) //
	{
		if ((PoljeKrompira[i][j] == 1) && (j > predhodni))
		{
			Redovi.push_back(j);
			predhodni = j;
		}
		if ((PoljeKrompira[i][j] == 1) && (i > predhodni2))
		{
			Kolone.push_back(i);
			predhodni2 = i;
		}
	}

}




cout << Redovi.size()*DimenzijaN + Kolone.size()*(DimenzijaN - Redovi.size());

	

return 0;

}

Link ka zadatku ili odgovarajućoj stranici

https://petlja.org/BubbleBee/r/problemi/takmicenja-srednje-skole/01_krompir

2

Nisam siguran sta se desava ovde tacno, vidim da si na kraju shvatio sta je resenje.
Prebroj koliko imas razlicitih redova i kolona i resenje je ovo sto si napisao. rn + k(n-r)

3

i koristi long long za rezultat jer (10^6)^2

4

Kao prvo, TLE dobijas jer ti je slozenost resenja O(N^2). To je zato sto imas petlju u petlji, koje obe idu do N,pa ti je slozenost N * N, a N <= 10^6. To bi vec za N nesto vece od 10000 probijalo ogranicenje.
Takodje, ne mozes napraviti matricu od 10^6 * 10^6.
E sad, ovako sam ja radio,mislim da je ovalo dosta lakse:
Znamo da ce u svakoj koloni i redu u kojoj postoji bar jedno pocetno polje izrasti krompiri. Zato prakticno mozemo posmatrati poziciju pocetnog polja koju dobijemo u inputu kao broj kolone u kojoj ce na svim poljima izrasti krompiri, i broj vrste u kojoj ce na svim poljima izrasti krompiri. Izacunacemo broj polja na kojima krompir nije porastao, kao (broj_nespomenutih_kolona) * (broj_nespomenutih_vrsti). To je tacno jer ce u preseku svake kolone i vrste u kojima ne postoji ni jedno pocetno polje biti jedno prazno polje(bez krompira). Zatim samo oduzmemo dobijeni broj od ukupnog broja polja, i dobili smo resenje.

Mozes da pogledas kod ovde.

PS:
Vidim da si i ti mozda pokusavao nesto slicno, ali mozda nisi smislio nesto dovoljno brzo.

5

Pojasnio si mi zadatak i složenost algoritma, izgleda da sam inpute nepotrebno učitavao u matricu i zatim ih čitao iz nje. U svakom slučaju imam odgovore na pitanja, hvalaa

1 Like