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!