MathDB
embed within O(nlogn) sum

Source: STEMS 2021 CS Cat A Q3

January 23, 2021
combinatorics

Problem Statement

A positive sequence is a finite sequence of positive integers. Sum of a sequence is the sum of all the elements in the sequence. We say that a sequence AA can be embedded into another sequence BB, if there exists a strictly increasing function ϕ:{1,2,…,∣A∣}→{1,2,…,∣B∣},\phi : \{1,2, \ldots, |A|\} \rightarrow \{1,2, \ldots, |B|\}, such that ∀i∈{1,2,…,∣A∣}\forall i \in \{1, 2, \ldots ,|A|\}, A≤B[ϕ(i)],A \leq B[\phi(i)], where ∣S∣|S| denotes the length of a sequence SS. For example, (1,1,2)(1,1,2) can be embedded in (1,2,3)(1,2,3), but (3,2,1)(3,2,1) can not be in (1,2,3)(1,2,3)\\ Given a positive integer nn, construct a positive sequence UU with sum O(n log⁡ n)O(n \, \log \, n), such that all the positive sequences with sum nn, can be embedded into UU.\\
Back to ProblemsView on AoPS