Subcontests
(6)Weird (Is it?) sequences
Let a1,a2,…an be positive real numbers. Define b1,b2,…bn as follows.
\begin{align*}
b_1&=a_1 \\
b_2&=max(a_1,a_2)\\
b_i&=max(b_{i-1},b_{i-2}+a_i) \text{ for } i=3,4 \dots n
\end{align*}
Also define c1,c2…cn as follows.
\begin{align*}
c_n&=a_n \\
c_{n-1}&=max(a_n,a_{n-1})\\
c_i&=max(c_{i+1},c_{i+2}+a_i) \text{ for } i=n-2,n-3 \dots 1
\end{align*}
Prove that bn=c1.\\ embed within O(nlogn) sum
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 A can be embedded into another sequence B, if there exists a strictly increasing function ϕ:{1,2,…,∣A∣}→{1,2,…,∣B∣}, such that ∀i∈{1,2,…,∣A∣}, A≤B[ϕ(i)], where ∣S∣ denotes the length of
a sequence S. For example, (1,1,2) can be embedded in (1,2,3), but (3,2,1) can not be in (1,2,3)\\
Given a positive integer n, construct a positive sequence U with sum O(nlogn), such that all the positive sequences with sum n, can be embedded into U.\\