codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.