## DMOPC '14 Contest 6 P3 - Brotherly Sequence

View as PDF

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 where for every index , and . Given a sequence of numbers of length , what is the length of the longest contiguous brotherly subsequence it contains?

#### Input Specification

The first line of input will contain the integer .
The second line of input will contain space-separated integers making up the sequence . The numbers in are in the range .

#### Output Specification

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

#### 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).

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

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

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

Shouldnt it be contest 5?

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

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

Can we have another input/output sample?

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

No, we believe the existing sample is enough.

• 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?

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