Editorial for Još jedna konstrukcija

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: milisav

Primetimo da je rešenje uvek moguće pronaći sa nizom dužine $2N-1$ ~2N-1~ i vrednostima:

$1$ ~1~ $2$ ~2~ $3$ ~3~ ... $N-1$ ~N-1~ $N$ ~N~ $N-1$ ~N-1~ $N-2$ ~N-2~ ... $2$ ~2~ $1$ ~1~

Primetimo da se u nizu svaka vrednost mora pojaviti bar jednom, pa niz mora imati dužinu bar $N$ ~N~. Takođe, primetimo da ukoliko bi niz imao dužinu manju od $2N-1$ ~2N-1~, to znači da postoje bar dve različite vrednosti $A$ ~A~ i $B$ ~B~, koje se pojavljuju tačno jednom. Ukoliko se vrednost $A$ ~A~ pojavljuje pre vrednosti $B$ ~B~, ne postoji par indeksa za par vrednosti $(B,A)$ ~(B,A)~, u suprotnom ne postoji par indeksa za par vrednosti $(A,B)$ ~(A,B)~.

Comments

There are no comments at the moment.