DMOPC '14 Contest 6 P3 - Brotherly Sequence

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Kamina is interested in brotherly sequences. A brotherly sequence is a sequence S where for every index i, |S[i-1]-S[i]| \le 2 and |S[i]-S[i+1]| \le 2. Given a sequence of numbers S of length N (3 \le N \le 100), what is the length of the longest contiguous brotherly subsequence it contains?

Input Specification

The first line of input will contain the integer N.
The second line of input will contain N space-separated integers making up the sequence S. The numbers in S are in the range [-1000, +1000].

Output Specification

The positive integer length of the longest brotherly subsequence in the sequence S.

Sample Input

5
1 1 2 4 8

Sample Output

4

Note

A subsequence of a sequence is a sequence that is formed by deleting some elements of the original sequence, but preserving the relative order of the remaining elements. A contiguous subsequence is a subsequence formed by deleting some prefix and some suffix of the sequence (possibly empty for either or both).


Comments


  • 0
    zwang24  commented on Aug. 21, 2018, 6:00 p.m. edited

    Hello! :D This is a hard question if you ask me. :(


  • 0
    jlsajfj  commented on Feb. 15, 2016, 9:35 p.m.

    Shouldnt it be contest 5?


    • 0
      r3mark  commented on Feb. 15, 2016, 9:46 p.m.

      No, because Exam Time was the fourth contest of the 2014 DMOPCs. The URL for the Exam Time problems had "ce" instead of "c4" though, so I guess that's why the URL for all the 2014 DMOPCs after Exam Time were 1 off.


  • 0
    Axiomschema  commented on March 10, 2015, 5:37 p.m.

    Can we have another input/output sample?


    • 0
      FatalEagle  commented on March 10, 2015, 6:15 p.m.

      No, we believe the existing sample is enough.


  • 0
    Spirit  commented on March 10, 2015, 5:03 p.m.

    Can there be an explanation for the sample output? Such as what the longest contiguous brotherly subsequence would be?


    • 0
      Xyene  commented on March 10, 2015, 5:09 p.m.

      For the sample input, we can remove the last element of the sequence. The resulting subsequence is maximal.