MathDB
Problems
Contests
National and Regional Contests
Korea Contests
Korea Winter Program Practice Test
2016 Korea Winter Program Practice Test
4
Maximum length of strictly monotone sequence
Maximum length of strictly monotone sequence
Source: 2016 Korea Winter Camp 2nd Test #8
January 25, 2016
combinatorics
Problem Statement
Let
a
1
,
a
2
,
⋯
a
100
a_1, a_2, \cdots a_{100}
a
1
,
a
2
,
⋯
a
100
be a permutation of
1
,
2
,
⋯
100
1,2,\cdots 100
1
,
2
,
⋯
100
. Define
l
(
k
)
l(k)
l
(
k
)
as the maximum
m
m
m
such that there exists
i
1
,
i
2
⋯
i
m
i_1, i_2 \cdots i_m
i
1
,
i
2
⋯
i
m
such that
a
i
1
>
a
i
2
>
⋯
>
a
i
m
a_{i_1} > a_{i_2} > \cdots > a_{i_m}
a
i
1
>
a
i
2
>
⋯
>
a
i
m
or
a
i
1
<
a
i
2
<
⋯
<
a
i
m
a_{i_1} < a_{i_2} < \cdots < a_{i_m}
a
i
1
<
a
i
2
<
⋯
<
a
i
m
, where
i
1
=
k
i_1=k
i
1
=
k
and
i
1
<
i
2
<
⋯
<
i
m
i_1<i_2< \cdots <i_m
i
1
<
i
2
<
⋯
<
i
m
Find the minimum possible value for
∑
i
=
1
100
l
(
i
)
\sum_{i=1}^{100} l(i)
∑
i
=
1
100
l
(
i
)
.
Back to Problems
View on AoPS