Editorial for Pikado


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Analiza

Potrebno je naći sve elemente niza A koji se pojavljuju bar K puta u nizu. Elementi niza A su u intervalu [-N,N] tako da postoji 2 \cdot N+1 različitih vrednosti koje se mogu pojaviti u nizu. Možemo iskoristiti pomoćni niz B dužine 2 \cdot N+1 koji predstavlja broj pojavljivanja svakog elementa u početnom nizu.

Na početku niz B ima vrednost 0 na svakoj poziciji. Jednim prolaskom kroz niz A, kada naiđeimo na element A_i povećavamo broj pojavljivanja tog elementa za 1. Pošto ne možemo pristupiti negativnim indeksima broj pojavljivanja elementa koji ima vrednost X pamtimo u nizu B na poziciji X+N. Tako je interval [-N,N] preslikan u interval [0, 2 \cdot N] što nam omogućava da koristimo niz.

Prolaskom kroz niz B prebrojavamo i ispisujemo sve brojeve koji su se pojavili bar K puta u nizu. Ako za neko j važi da je B[j] \geq K to znači da se broj j-N pojavio bar K puta.

Implementacija korišćenjem niza je složenosti O(N). Može se koristiti i struktura zasnovana na pretraživačkom stablu (std::map složenosti O(N \log N)) ili heš tabela (std::unordered_map očekivane složenosti O(N)) što nam omogućava rešenje i kada su elementi niza A mnogo veliki i nemamo dovoljno memorije da napravimo niz koji obuhvata sve potencijalne vrednosti.


Comments

There are no comments at the moment.