During the November Lunchtime contest I misread the Perfection task. Here is how I misread it:
then choose an integer x<A_l and for each i (l\leq i\leq r) replace A_i by x
I read as
then choose an integer x<l and for each i (l\leq i \leq r) replace A_i by A_x.
This however gives rise to an interesting problem. I have found a \mathcal{O}(n^2) solution for this adapted problem. I would like to challenge others to find a solution to this adapted problem. I am curious if anyone can find a more efficient solution.
I think that would give the same problem as how I misread it. There would be no benefit in changing a range to a value that isn’t somewhere left of it.
I present my solution below, it is however hidden because I don’t want to spoil the solution for anyone who want’s to think about it themselves.
Solution
It is obvious that at most n-1 replacements are needed: replace everything by A_1.
Let’s now look at the following case: 1,0,0,1, This can be solved by one replacement: 1,0,0,1\implies 1,1,1,1. This was because the zeroes were surrounded by the same value, and this meant one fewer replacement was needed.
We want to take advantage of as many such “surroundings” as we can. For this we find all potential surroundings, ranges (i,j) such that A_i=A_j and A_i\neq A_k for all i<k<j. This can be done in \mathcal{O}(n) time
Finding all surroundings
Convert the input array into one that also has the indeces of each element. For example [5,3,5] goes to [(5,0),(3,1),(5,2)]. Then sort this array: [(3,1),(5,0),(5,2)]. In the sorted array we look at adjacent elements who’s value is the same and take the indeces as a surrounding.
Now the question becomes when we can use surroundings together. I will present three examples:
0,0,1,1
1,0,0,1
1,0,1,0
When surroundings can be used together
Example 1 and 2 can be done in 1 replacements, while 2 are needed for the last example. All these examples do have the same number of “surroundings”. Two surroundings can be used together in two cases:
one surrounding comes entirely before the other: surroundings (a,b),(c,d) can work if b<c or d<a
one surrounding is in the other surrounding: (a,b),(c,d) can work if a<c,d<b or c<a,b<d
Next we will need to find the maximum number of surroundings that can be used together. This is the hardest part. To simplify we will first only look at the first case.
Maximum non-nested surroundings
First sort all ranges [(a_i,b_i)] in increasing a_i and when there are ties decreasing b_i. Then we go trough the ranges in order and keep track of the last range we can use. It’s hard to explain the algorithm so instead I’m going to give an illustrative example: [(1,5),(2,3),(4,6)]
First take (1,5), it’s the only one we’ve considered so far so we rember it.
Then it’s (2,3)'s turn. It’s end comes before the end of (1,5)\implies remember (2,3) instead
Next is (4,6). This one is entirely after (2,3) so we use (2,3) and remember (4,6)
Now we’ve seen all ranges. We still have (4,6) in our memory so we also use that one.
As we only loop trough all ranges once this algorithm is \mathcal{O}(n). It can be adapted, using DP to also take into account ranges with some weight and we want the maximum weight compatible ranges.
And then the algorithm for when we include nested surroundings into the mix:
Maximum nested surroundings
We first assign each range we found a value of 1. Then we go trough all ranges in the order small to large and compute how many compatible surroundings would fit in it. This is essentially the previous segment: the weighted compatible segments problem. Then we update the weight of this range as the calculated value + 1 (the +1 for the range itself).
We compute small to large as a large segment will never be able to fit into a smaller one.
As we apply an \mathcal{O}(n) algorithm n times the entire algorithm has efficiency \mathcal{O}(n^2)
Given the maximum number of surroundings k our answer will be n-1-k