For further information
or to submit your
Research and Practice
(DGOV) is an
journal on the
potential and impact
innovations and its
public institutions. It
promotes applied and
and data sciences
Research and Practice
2. In the case of a linear fence, the max
number of autonomous sub-sequences is the number obtained in an O(N)
“pass” over the columns from left to
right, while “collecting” the autonomous sub-sequences inductively.
The circular case is much harder. In
this case, there is no left-end. For the
sequence: 6 5 5 7 3 8 5 1 6 4, if we
start the computation from the leftmost
6, we will obtain only two autonomous
sub-sequences. This will also be the case if
we start the (circular) pass from the right
6. However, if we start the pass from the
the rightmost 4, or from the left 5, we will
obtain four autonomous sub-sequences.
Thus, different starting points may yield
different amounts of autonomous sub-sequences. One solution approach may be to
pass N times over the input—each starting
at a different column. This solution is correct, but its time complexity is O(N²). We
would like to do better.
Some problem solvers offer to conduct
only passes that start with columns of
height H. However, there may not always
be such columns, and even if there are, will
they always yield the optimal solution? We
let the reader answer this question.
It is interesting to examine various
problem solvers’ attempts and see how
they progress (or not). Unfortunately, our
space here is limited. Therefore, we just
display an observation offered by the more
creative problem solvers. Capitalization
on this observation yields an O(NlogN)
solution, which requires only one pass over
the column heights (and may start at any
column), plus some extra work. The observation is the following.
In a circular fence, the sequence of N
values of the accumulated (partial)
sum of the number of tiles, starting at
the 1-st column, of height c1, equals the
sequence starting at the 2-nd column,
in which each value is reduced by −c1.
(Notice that the sequence of 3 sum-values for the input 6 5 4 starting at
the 6 is: 6 11 15.)
The above observation illuminates the
characteristic that sequences of sum-val-
ues that start from different starting points
are very similar. The challenge that remains
is to recognize a pattern in a sequence of
N sum-values, which characterizes the max
number of autonomous sub-sequences.
In our experience, students find the
challenge puzzling. Although the case of
a linear fence is not that subtle, some stu-
dents still struggle with that case as they
seek not only the number of transfers but
also their actual directions and amounts. In
addition, students are not always con-
vinced about optimality. Some do not see
that the greedy approach of one pass from
left to right is optimal (due to the optimal
autonomous sub-sequence for the first
column, followed by an inductive argu-
ment for the remaining input sequence).
The case of a circular fence is much more
difficult. We pose it to the better students.
Those who examine different inputs, and
compare sequences of partial sums, recog-
nize and capitalize on the latter displayed
pattern. They demonstrate the importance
of flexibly examining diverse inputs in
seeking hidden patterns.
DOI: 10.1145/3341096 Copyright held by author/owner