How to solve this algorithmic puzzle?

Question

For fixed integers $T\geq G>1$, we say a list $[a_1, a_2,\cdots, a_n]$ is normal if every consecutive sublist $[a_i, a_{i+1}, \cdots a_{i+T-1}]$ of length $T$ has less than $G$ maximal elements.

Given a list $[a_1, a_2,\cdots, a_n]$ of $N$ numbers between $1$ and $30$ inclusive, suppose that by adding one to the $i^\text{th}$ element of the list we call this an operation. If we may only operate on a particular element once, how can we find the minimal number of operations needed to make this list normal?

Some examples for illustration:

If $T=G=2$, then from the list $[1, 2, 3, 4, 5]$ we are considering the four sublists $[1,2]; [2,3]; [3,4];$ and $[4,5]$. The maximal elements of these sublists are $2,3,4,$ and $5$, respectively. Since none of these are repeated, each occurs less than twice in its respective sublist, and so it is normal.Thus ,for this case the minimum number of operations required to make the list normal are 0.

If $N=5$, $T=3$ and $G=3$, and the list is $[7,7,7,7,7]$, we are considering the sublists $[7,7,7] ; [7,7,7] ;$ and $[7,7,7]$. Initially, the list violates the property that maximum element should be less than $G=3$ times in each sublist. However, if we operate on the third element, the list becomes $[7,7,8,7,7]$, which is normal. (The sublists are $[7,7,8] ; [7,8,7];$ and $[8,7,7]$, and the maximum element of each sublist is $8$ and is present less than three times in that sublist.) Thus ,for this case the minimum number of operations required to make the list normal are 1.

http://www.careercup.com/question?id=8407365 : Might be helpful to you. — Inquisitive, Jan 03 '13 at 21:20
Why is this tagged linear programming? Or even linear algebra? You also do not define what you mean by operation. Do you partition your list 1..N into sublists all of size T? This is very unclear. — Per Alexandersson, Jan 03 '13 at 22:03
@Paxinum: for eg a list 1 2 3 4 5 with t=2 has 4 sublists 1,2 2,3 3,4 4,5 .also maximal elements of these sublists are 2,3,4,5 respectively. — user1907531, Jan 03 '13 at 22:11
@Paxinum: for G=3,N=5 and T=3 7,7,7,7,7 in this case sublists are 7,7,7 ; 7,7,7 ; 7,7,7 . this violates the property that maximum element should be less than G=3 times in each sublist,if we change third element to 8 (by performing the operation ),the required property is satisfied — user1907531, Jan 03 '13 at 22:14
@Paxinum: The property is satified because now the sublists are 7,7,8 ; 7,8,7 and 8,7,7 as G=3 ,the maximum element of each sublist is present less that 3 times in that sublist.We see the maximum elements of each element is 8 now with occurrence 1 each. However,we just need to minimize the number of operations in satisfying the given property. — user1907531, Jan 03 '13 at 22:15
Where did this problem come from? Without context it's interesting but really contrived. — Eric Stucky, Jan 03 '13 at 22:42
@EricStucky:I came across this problem in a computer algorithms book ,titled under problems solvable with a known algorithm. — user1907531, Jan 03 '13 at 23:00
@user1907531: I have substantially edited the question for readability; please make sure I have not changed the meaning. — Eric Stucky, Jan 03 '13 at 23:27
@EricStucky:I have gone through it,you have done a great job. — user1907531, Jan 03 '13 at 23:29
@user1907531: Yes, but I am working on how to show that it is a minimal solution. I'm not well-versed in algorithms :) — Eric Stucky, Jan 03 '13 at 23:41
@EricStucky:any ideas/pointers may help me think in the correct direction — user1907531, Jan 03 '13 at 23:44
Thinking about this problem recursively looks fruitful: in many cases, making $[a_1, \cdots, a_{n-1}]$ normal will automatically normalize $[a_1, \cdots, a_n]$. Consider, then, how to characterize the lists for which you must operate on $a_n$ in order to normalize them optimally. If your list is one of them, operate on $a_n$. In any event, proceed to recursively solve the problem for $[a_1, \cdots, a_{n-1}]$. The complication to deal with is when $a_n$ is a maximum and the final $T$ elements of the list are not normal. — whuber, Jan 04 '13 at 00:26

Eric Stucky · Accepted Answer · 2013-01-04T07:08:53.780

Here's an interesting algorithm that performs pretty well (and may be whuber's idea but starting with 1 instead of $N$).

Let the length-$T$ consecutive list whose first element is $a_i$ be called $A_i$. Then $A_1$ will have some number of maximal elements. If this number is less than $G$, move on. In this way, find the smallest $n\leq N-T+1$ such that $A_n$ has at least $G$ maximal elements, and operate at the last maximal element of $A_n$.

Continuing from $A_n$ will yield a normal list unless there are at least $G-1$ copies of $a_m+1$ with indices $(m-T)<i<n$. Otherwise, continuing from $A_m$ will yield a normal list unless there are at least $G-1$ copies of $a_m+1$ with indices $(n+T)\leq i< (m+T)$.

In the best case, begin again at $A_m$. In the latter case, begin again at $A_n$. In the former case, because $a_j<a_m$ for all $m<j<(n+T)$, the beginning sequence can be changed without disturbing the remaining, sequence, which adds at most $n$ operations (and probably significantly fewer).

The fact that the former case has to be considered at all is a huge drawback, however. I'm not sure I could get much further in this one, but I'll sleep on it.

(On the bright side, I'm pretty sure can only possibly occur in the first iteration, which means that these "errors" occur for lists with large $n$, which is of course where the other "errors" occur less.)

How to solve this algorithmic puzzle?

1 Answers1