codeforces-scrape

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

255C.md (1667B)


      1 Source: https://codeforces.com/problemset/problem/255/C
      2 
      3 C. Almost Arithmetical Progression
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Gena loves sequences of numbers. Recently, he has discovered a new type of sequences which he called an almost arithmetical progression. A sequence is an almost arithmetical progression, if its elements can be represented as:
     22 
     23 * *a*1 = *p*, where *p* is some integer;
     24 * *a**i* = *a**i* - 1 + ( - 1)*i* + 1·*q* (*i* > 1), where *q* is some integer.
     25 
     26 Right now Gena has a piece of paper with sequence *b*, consisting of *n* integers. Help Gena, find there the longest subsequence of integers that is an almost arithmetical progression.
     27 
     28 Sequence *s*1,  *s*2,  ...,  *s**k* is a subsequence of sequence *b*1,  *b*2,  ...,  *b**n*, if there is such increasing sequence of indexes *i*1, *i*2, ..., *i**k* (1  ≤  *i*1  <  *i*2  < ...   <  *i**k*  ≤  *n*), that *b**i**j*  =  *s**j*. In other words, sequence *s* can be obtained from *b* by crossing out some elements.
     29 
     30 Input
     31 
     32 The first line contains integer *n* (1 ≤ *n* ≤ 4000). The next line contains *n* integers *b*1, *b*2, ..., *b**n* (1 ≤ *b**i* ≤ 106).
     33 
     34 Output
     35 
     36 Print a single integer — the length of the required longest subsequence.
     37 
     38 Examples
     39 
     40 Input
     41 
     42 ```
     43 2  
     44 3 5
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 2
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 4  
     57 10 20 10 30
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 3
     64 ```
     65 
     66 Note
     67 
     68 In the first test the sequence actually is the suitable subsequence.
     69 
     70 In the second test the following subsequence fits: 10, 20, 10.