Olimpiada STEMSfina India 2021 Problema 15

Una secuencia positiva es una secuencia finita de enteros positivos. La suma de una secuencia es la suma de todos los elementos en la secuencia. Decimos que una secuencia $A$ puede ser incrustada en otra secuencia $B$ , si existe una función estrictamente creciente \n$$\phi : \{1,2, \ldots, |A|\} \rightarrow \n\{1,2, \ldots, |B|\},$$ \ntal que $\forall i \in \{1, 2, \ldots ,|A|\}$ , \n$$A[i] \leq B[\phi(i)],$$ \ndonde $|S|$ denota la longitud de una secuencia $S$ . Por ejemplo, $(1,1,2)$ puede ser incrustado en $(1,2,3)$ , pero $(3,2,1)$ no puede ser incrustado en $(1,2,3)$ Dado un entero positivo $n$ , construya una secuencia positiva $U$ con suma $O(n \, \log \, n)$ , tal que todas las secuencias positivas con suma $n$ , puedan ser incrustadas en $U$ .

3

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados