codeforces-scrape

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

1335E1.md (2180B)


      1 Source: https://codeforces.com/problemset/problem/1335/E1
      2 
      3 E1. Three Blocks Palindrome (easy version)
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 The only difference between easy and hard versions is constraints.
     22 
     23 You are given a sequence $a$ consisting of $n$ positive integers.
     24 
     25 Let's define a three blocks palindrome as the sequence, consisting of at most two distinct elements (let these elements are $a$ and $b$, $a$ can be equal $b$) and is as follows: $[\underbrace{a, a, \dots, a}_{x}, \underbrace{b, b, \dots, b}_{y}, \underbrace{a, a, \dots, a}_{x}]$. There $x, y$ are integers greater than or equal to $0$. For example, sequences $[]$, $[2]$, $[1, 1]$, $[1, 2, 1]$, $[1, 2, 2, 1]$ and $[1, 1, 2, 1, 1]$ are three block palindromes but $[1, 2, 3, 2, 1]$, $[1, 2, 1, 2, 1]$ and $[1, 2]$ are not.
     26 
     27 Your task is to choose the maximum by length subsequence of $a$ that is a three blocks palindrome.
     28 
     29 You have to answer $t$ independent test cases.
     30 
     31 Recall that the sequence $t$ is a a subsequence of the sequence $s$ if $t$ can be derived from $s$ by removing zero or more elements without changing the order of the remaining elements. For example, if $s=[1, 2, 1, 3, 1, 2, 1]$, then possible subsequences are: $[1, 1, 1, 1]$, $[3]$ and $[1, 2, 1, 3, 1, 2, 1]$, but not $[3, 2, 3]$ and $[1, 1, 1, 1, 2]$.
     32 
     33 Input
     34 
     35 The first line of the input contains one integer $t$ ($1 \le t \le 2000$) — the number of test cases. Then $t$ test cases follow.
     36 
     37 The first line of the test case contains one integer $n$ ($1 \le n \le 2000$) — the length of $a$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 26$), where $a_i$ is the $i$-th element of $a$. Note that the maximum value of $a_i$ can be up to $26$.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$ ($\sum n \le 2000$).
     40 
     41 Output
     42 
     43 For each test case, print the answer — the maximum possible length of some subsequence of $a$ that is a three blocks palindrome.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 6
     51 8
     52 1 1 2 2 3 2 1 1
     53 3
     54 1 3 3
     55 4
     56 1 10 10 1
     57 1
     58 26
     59 2
     60 2 1
     61 3
     62 1 1 1
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 7
     69 2
     70 4
     71 1
     72 1
     73 3
     74 ```