Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
careercup.com/question?id=8407365 : Might be helpful to you. –  Inquisitive Jan 3 '13 at 21:20
    
@Inquisitive:thanks,but it doesn't help me at all –  user1907531 Jan 3 '13 at 21:21
1  
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. –  Paxinum Jan 3 '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 3 '13 at 22:11
1  
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 4 '13 at 0:26
show 9 more comments

1 Answer

up vote 0 down vote accepted

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.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.