Search Exercise
---------------
Exercise 1:
For given N, create a list of length N whose members are numbers
between 1 and N (inclusive), which are all different (easy so far)
and satisfy the following constraint.
For each element E of the list, its successors are divided into two sets,
BiggerE: the successors which are greater than E and
SmallerE: the successors less than E.
(Thus no successor takes the same value as E).
The cardinalities of the sets BiggerE and SmallerE differ by at most 1.
Exercise 2 (during the week...):
A harder version of the problem is similar.
For given N, create a list of length N whose members are numbers
between 1 and some upper bound Max (start with, say Max = N^2),
which are all different (easy so far)
and satisfy the following (more complex) constraint.
For each K from 1..N, call the Kth element of the list Ek.
Its successors are divided into two sets, as before:
BiggerEk: the successors which are greater than or equal to Ek + K and
SmallerEk: the successors less than or equal to Ek - K.
(Thus no successor takes a value between Ek-K+1 and Ek+K-1.)
The cardinalities of the sets BiggerEk and SmallerEk differ
by at most 1.
What is the smallest upper bound Max for which there is a feasible solution?