Editorial for Podudarajuće Permutacije

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.

Author: Pajaraja

U ovom zadatku je potrebno zameniti mesta nekim članovima dva niza i naći na koliko mesta mogu najviše da se poklapaju. Ako gledamo sva pojavljivanja broja $x$ ~x~ u nizu $A$ ~A~ i nizu $B$ ~B~ (i oznčimo ove vrednosti sa npr. $a$ ~a~ i $b$ ~b~) vidimo da $x$ ~x~ može da učestvuje u najviše $\min(a,b)$ ~\min(a,b)~ preklapanja. Stoga ako izračunamo nizove $cnta$ ~cnta~ i $cntb$ ~cntb~ gde vrednost $cnta[x]$ ~cnta[x]~ predstavlja broj pojavljivanja broja $x$ ~x~ u nizu $A$ ~A~, a $cntb[x]$ ~cntb[x]~ predstavlja broj pojavljivanja broja $x$ ~x~ u nizu $B$ ~B~, vidimo da je broj preklapanja sigurno najviše $\min(cnta[1],cntb[1])+\min(cnta[2],cntb[2])+\min(cnta[3],cntb[3])+\cdots+\min(cnta[100000],cntb[100000])$ .

Možemo primetiti da je i ovo uvek moguće dostići tako što unapred izaberemo tih $\min(cnta[1],cntb[1])+\min(cnta[2],cntb[2])+\min(cnta[3],cntb[3])+\cdots+\min(cnta[100000],cntb[100000])$ parova koje ćemo upariti, ispermutujemo niz tako da se oni upare, i ostatak ispermutovali proizvoljno. Implementacija ovog algoritma se radi lako u $O(N+\max A_i+\max B_i)$ ~O(N+\max A_i+\max B_i)~

Mogući pristup koji nije tačan je da se oba niza samo sortiraju. Ovaj pristup ima eksplicitan kontraprimer u slučaju $N=3,A={1,2,3},B={2,3,4}$ ~N=3,A={1,2,3},B={2,3,4}~

Comments

0

pshyotic commented on April 5, 2020, 11:11 p.m.

kod?
2

MladenP commented on April 5, 2020, 10:00 p.m.

Pazi kamen!