2056C.md (3036B)
1 Source: https://codeforces.com/problemset/problem/2056/C 2 3 C. Palindromic Subsequences 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 For an integer sequence $a = [a_1, a_2, \ldots, a_n]$, we define $f(a)$ as the length of the longest subsequence$^{\text{∗}}$ of $a$ that is a palindrome$^{\text{†}}$. 22 23 Let $g(a)$ represent the number of subsequences of length $f(a)$ that are palindromes. In other words, $g(a)$ counts the number of palindromic subsequences in $a$ that have the maximum length. 24 25 Given an integer $n$, your task is to find any sequence $a$ of $n$ integers that satisfies the following conditions: 26 27 * $1 \le a_i \le n$ for all $1 \le i \le n$. 28 * $g(a) \gt n$ 29 30 It can be proven that such a sequence always exists under the given constraints. 31 32 $^{\text{∗}}$A sequence $x$ is a subsequence of a sequence $y$ if $x$ can be obtained from $y$ by the deletion of several (possibly, zero or all) element from arbitrary positions. 33 34 $^{\text{†}}$A palindrome is a sequence that reads the same from left to right as from right to left. For example, $[1, 2, 1, 3, 1, 2, 1]$, $[5, 5, 5, 5]$, and $[4, 3, 3, 4]$ are palindromes, while $[1, 2]$ and $[2, 3, 3, 3, 3]$ are not. 35 36 Input 37 38 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows. 39 40 The first line of each test case contains a single integer $n$ ($\color{red}{6} \le n \le 100$) — the length of the sequence. 41 42 Note that there are no constraints on the sum of $n$ over all test cases. 43 44 Output 45 46 For each test case, output $n$ integers $a_1, a_2, \ldots, a_n$, representing an array that satisfies the conditions. 47 48 If there are multiple solutions, you may output any of them. 49 50 Example 51 52 Input 53 54 ``` 55 3 56 57 6 58 59 9 60 61 15 62 ``` 63 64 Output 65 66 ``` 67 1 1 2 3 1 2 68 7 3 3 7 5 3 7 7 3 69 15 8 8 8 15 5 8 1 15 5 8 15 15 15 8 70 ``` 71 72 Note 73 74 In the first example, one possible solution is $a = [1, 1, 2, 3, 1, 2]$. In this case, $f(a) = 3$ as the longest palindromic subsequence has length $3$. There are $7$ ways to choose a subsequence of length $3$ that is a palindrome, as shown below: 75 76 1. $[a_1, a_2, a_5] = [1, 1, 1]$ 77 2. $[a_1, a_3, a_5] = [1, 2, 1]$ 78 3. $[a_1, a_4, a_5] = [1, 3, 1]$ 79 4. $[a_2, a_3, a_5] = [1, 2, 1]$ 80 5. $[a_2, a_4, a_5] = [1, 3, 1]$ 81 6. $[a_3, a_4, a_6] = [2, 3, 2]$ 82 7. $[a_3, a_5, a_6] = [2, 1, 2]$ 83 84 Therefore, $g(a) = 7$, which is greater than $n = 6$. Hence, $a = [1, 1, 2, 3, 1, 2]$ is a valid solution. 85 86 In the second example, one possible solution is $a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$. In this case, $f(a) = 5$. There are $24$ ways to choose a subsequence of length $5$ that is a palindrome. Some examples are $[a_2, a_4, a_5, a_8, a_9] = [3, 7, 5, 7, 3]$ and $[a_1, a_4, a_6, a_7, a_8] = [7, 7, 3, 7, 7]$. Therefore, $g(a) = 24$, which is greater than $n = 9$. Hence, $a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$ is a valid solution. 87 88 In the third example, $f(a) = 7$ and $g(a) = 190$, which is greater than $n = 15$.