We can now reformulate the problem as follows.
Given are numbers `n`, `m`, and `k`
with `1 <= n <= 6` and
`1 <= m,k <= 20`.
The objective is to find *all* circular arrangements
of `n` numbers, each number being at least `k`,
such that the tail of `m` is as large as possible.
It is also required to output that tail.
In fact, the problem statement prescribes the output more precisely:
the first line contains the maximum tail,
the following lines present the circular arrangements (one per line),
such that they start with their smallest number.

Observe that creatable numbers are at least `k`.
Thus, for `m < k` the tail of `m` is `m-1`,
because `m` itself is not creatable.
For `k <= m` the maximum tail is *at least* `m+n-1`,
because of the circular arrangement consisting of the `n` numbers
`m`, `m+1`, ..., `m+n-1` *in arbitrary order*.
Since in the output these arrangements should all start with the smallest
number---that is, with `m`---there are `(n-1)!` such
arrangements.
These arrangements and also their tail are called *trivial*.
The trivial tail is a *lower bound* on the maximum tail
(provided that `m >= k`).

**N.B.**
The number `(n-1)!` of trivial arrangements is *not*
an *upper bound* on the number of arrangements to be output.
In fact, it turns out that the input `n,m,k = 5,10,5`
has 32 arrangements for the maximum tail of 14.

From now on we assumek <= m(the Competition Rules explicitly state that all test data will have solutions; this also implies that 1 is alower boundon the number of arrangements to be output). Furthermore, when we speak of the tail, we mean the tail ofm.

The cases `n = 1, 2, 3` are special,
because *every* non-empty subset of the numbers appears as
a segment of adjacent numbers in the circle.
The case `n=1` is uninteresting: the maximum tail is `m`
obtained by the unique arrangement `m`.

The cases `n = 2, 3` can also be solved ``by hand'',
but they are tricky!
For instance, for `n=2` and `m > 1` there is
the arrangement `m`, `m+1` yielding the maximum
tail `m+1`
(observe that `m+2` is not creatable since `2m+1 > m+2`).
But if `k=1` then there is also the arrangement
`m`, `1` yielding tail `m+1`.
If `m=1`, then the arrangement `1`, `2`
yields the maximum tail `m+2 = 3`.

We have already given the lower bound `m+n-1` on the maximum tail.
We can also give an *upper bound*.
The maximum tail is at most the sum of all numbers in the circle.
This upper bound is not very instructive.
Observe that for `1 <= p < n`,
there are `n` segments of `p` adjacent numbers,
Furthermore, there is a single segment of `n` adjacent numbers
(consisting of *all* numbers in the circle).
Thus, in total there are `(n-1)*n+1` segment sums.
In the best case every such segment creates a different number.
This means that the maximum tail is at most `m+(n-1)*n`.

const Max_n = 6; Max_m = 20; Max_k = 20; type Circle = array [1..Max_n] of integer; { intended: array [1..n] of integer } var n: 1..Max_n; { input value } m: 1..Max_m; { input value } k: 1..Max_k; { input value }Reading the input is easy. After that we will go through all possible arrangements once and store the best arrangements so far.

var BestCount: integer; { # best arrangements so far } BestArr: array [1..1000] of Circle; { BestArr[1..BestCount] = best arrangements so far } BestTail: integer; { maximum tail found so far }It is not clear at this point what upper bound to choose for the array

The final output is produced by procedure `WriteOutput`:

procedure WriteOutput; var i, j: integer; begin writeln(out, BestTail:1) ; for i := 1 to BestCount do begin for j := 1 to n do write(out, ' ', BestArr[i][j]:2) ; writeln(out) end { for i } ; if Test then writeln('Max tail = ', BestTail:1, '; # arr. = ', BestCount:1) end { WriteOutput } ;We will use the following global variables for constructing and checking arrangements:

var Arr: Circle; { Arr[1..n] is the circular arrangement } Tail: integer; { tail of Arr[1..n] }Given an arrangement of

procedure ComputeTail; { post: Tail = tail of m for circular arrangement Arr[1..n] } var a, b, s, u: integer ; Creatable: array[1..51] of boolean ; { Creatable[i] = i is creatable } begin u := 1 + m + (n-1)*n ; { 1 + upper bound on maximum tail } for a := 1 to u do Creatable[a] := false ; for a := 1 to n do begin s := 0 ; { s = sum of Arr[a..b] } for b := a to n do begin s := s + Arr[b] ; if s <= u then Creatable[s] := true end { for b } ; for b := 1 to a-2 do begin s := s + Arr[b] ; if s <= u then Creatable[s] := true end { for b } end { for a } ; Tail := m ; { linear search for smallest uncreatable number } while Creatable[Tail] do inc(Tail) ; dec(Tail) end { ComputeTail } ;There are a few things to be pointed out about

For each arrangement constructed,
the variables `t`, `BestArr`, `BestTail`
are updated by procedure `CheckArrangemant`:

procedure CheckArrangement; begin ComputeTail ; if Tail > BestTail then begin { improved arrangement } BestCount := 1 ; BestArr[BestCount] := Arr ; BestTail := Tail end { then } else if Tail = BestTail then begin { another arrangement with same tail } inc(BestCount) ; BestArr[BestCount] := Arr end { then } end { CheckArrangement } ;We would like to write

procedure FillRemainder(i: integer); { Fill remaining sectors Arr[i..n] in all possible ways } { pre: i > 1 } var j, u: integer; begin if i > n then { all sectors filled, check whether arrangement is useful } CheckArrangement else begin { fill sector i in all possible ways } if Trace then begin for j := 1 to pred(i) do write(Arr[j]:3) ; writeln end { if } ; u := m+(n-1)*n ; { naive upper bound on numbers to try } for j := Arr[1] to u do begin { N.B. Arr[1] is smallest number } Arr[i] := j ; FillRemainder(succ(i)) end { for j } end { then } end { FillRemainder } ;The for-loop tries all possible numbers

Procedure `FillRemainder` is called by procedure
`ComputeAnswer` that also provides the outermost for-loop:

procedure ComputeAnswer; { pre: k <= m } var j: integer; begin BestCount := 0 ; BestTail := m+n-1 ; for j := k to m do begin Arr[1] := j ; { N.B. this is the smallest number in the circle } FillRemainder(2) ; end { for j } end { ComputeAnswer } ;The only numbers to try in sector 1 are from

All of this is put together into Program 1. This program solves test cases 1, 2, and 4 within the time limit; for the others that is doubtful.

Another remark about Program 1 is that
if `BestTail` would be initialized to 0 instead of `m+n-1`,
then the input combination `n,m,k = 5,17,5` would cause an
overflow of the list of (intermediate) best arrangements:
the program would have to skip 1261 arrangements with tail 20,
before finding the first arrangement with (maximum) tail 21
(of which there are only 24).
It is hard to give an upper bound of the number of (intermediate)
best arrangements.
In the next program we will just start writing the best arrangements
to the output file, and overwrite it if we find an improvement.

It is difficult to improve the speed by avoiding duplicate
computations when determining tails of arrangements.
The main reason for this is that `(n-1)*n+1` segment sums
can only be computed when the *last* sector has been filled in.
For `n=6` there are 31 segment sums to be computed,
of which 16 involve on the last sector.

At the expensive of some overhead we can determine a tighter upper bound,
though this is a bit complicated.
Let us take the case `n,m,k = 5,3,1` as an example.
Consider a state where the first three sectors have been filled as follows:

i | 1 2 3 4 5 -------|------------------- Arr[i] | 3 5 7The call

The three sectors that have been filled in already determine 6 segment sums. Here is a table indicating the creatable numbers:

Creatable | 3 5 7 8 12 15 --------------------|----------------------------------- not (yet) Creatable | 4 6 9 10 11 13 14 16Filling in sector 4 with number

Assume we try `j >= 12`
then all 11 segment sums involving `Arr[4]` will at least 12,
and the 4 remaining segment sums involving `Arr[5]`
can then at best create the number 4, 6, 9, and 10.
This would leave 11 uncreatable, yielding a tail of at most 10.
Apparently, a good upper bound for `j` is 11
(quite a bit less than 23).

More in general, a better upper bound is obtained by determining
which numbers are already creatable, and by calculating the
number `q` of segment sums that involve `Arr[i+1..n]` and
*not* `Arr[i]`.
The segment sums involving `Arr[i]` are all at least `Arr[i]`,
and there will be at most `q` smaller segment sums created
from `Arr[i+1..n]`.
The (`q+1`)th number that is not yet creatable is a suitable
upper bound for `Arr[i]` because beyond that point the tail
can no longer grow.

Here is procedure `ComputeUpperBound` that computes
the improved upper bound:

procedure ComputeUpperBound(i: integer; var ub: integer); { post: ub = upper bound for Arr[i] based on Arr[1..i-1] } var a, b, s, u: integer ; Creatable: array[1..51] of boolean ; { Creatable[p] = p is creatable } begin u := 1 + m + (n-1)*n ; { 1 + upper bound on maximum tail } for a := 1 to u do Creatable[a] := false ; for a := 1 to pred(i) do begin s := 0 ; { s = sum of Arr[a..b] } for b := a to pred(i) do begin s := s + Arr[b] ; if s <= u then Creatable[s] := true end { for b } ; a := n - i ; { a = # unfilled sectors besides Arr[i] } a := n*a - (a*succ(a)) div 2 + 1 ; { a = 1 + # segment sums involving Arr[i+1..n] and not Arr[i] } ub := m ; while a <> 0 do begin while Creatable[ub] do inc(ub) ; inc(ub) ; dec(a) end { while } end { ComputeUpperBound } ;This is incorporated into a Program 2. For the case

Given `n,m,k` find the tail of `m` with the most arrangements.
Each arrangement yields a tail of `m`.
We are now interested in maximimizing the number of arrangements
that yield the same tail (instead of maximizing the tail).

Find all triples `n,m,k` such that
for the maximum tail of `m` there is at least one arrangement
whose smallest number is less than `m`.

Find all triples `n,m,k` such that their maximum tails
have a maximum number of arrangements.
I noticed that `n,m,k = 6,19,6` has maximum tail 24
for which there are 150 arrangements.
Can you find triples with more arrangements for their maximum tail?

To help you on your way, the file all.txt lists for each case its maximum tail and the number of corresponding arrangements.

Tom Verhoeff

Eindhoven University of Technology