Natus ad codicem (Обговорення)

1. MathModel•23 серп. 2025 р., 18:52

   So I find the editorial of B is too obvious style , so I decided to share a detailed one Here.

   We claim that p=[\underbrace{1,2}_{\displaystyle \lfloor \frac{n}{2} \rfloor \text{ times}}] + \underbrace{[1]}_{\displaystyle \text{ if } n \text{ is odd}}

   Each subarray of $[1]$ is a valid permutation , Here by our construction $[1]$ appears exactly \lceil \frac{n}{2} \rceil

   Each subarray of $[1,2]$ is a valid permutation , Here by our construction $[1,2]$ appears exactly \lfloor \frac{n}{2} \rfloor.

   Each subarray of $[2,1]$ is a valid permutation , Here by our construction $[2,1]$ appears exactly \lceil \frac{n}{2} \rceil

   yields a final count of (\lfloor \frac{n}{2} \rfloor + \lceil \frac{n}{2} \rceil)=n and n+\lceil \frac{n}{2} \rceil as the final count.

   \displaystyle n+\lfloor \frac{n}{2} \rfloor \ge \lceil \frac{3n}{2} \rceil -1

   We want to prove that

   we can split the integer and non integer part so we get

   n+\lfloor \frac{n}{2} \rfloor \ge n+\lceil \frac{n}{2} \rceil -1

   \lfloor \frac{n}{2} \rfloor \ge \lceil \frac{n}{2} \rceil -1

   From definition of floor and ceil

   \lceil x \rceil - \lfloor x \rfloor \in \{0,1\}

   which is equivalent to

   \lfloor \frac{n}{2} \rfloor - \lceil \frac{n}{2} \rceil \ge -1 \Leftrightarrow \lfloor \frac{n}{2} \rfloor - \lceil \frac{n}{2} \rceil \in \{-1,0\}

   Thus our construction is correct.

   Hope it helps..