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.