Maximum number achievable by converting two adjacent x to one (x+1)

Question

Given a sequence of N integers where 1 <= N <= 500 and the numbers are between 1 and 50. In a step any two adjacent equal numbers x x can be replaced with a single x + 1. What is the maximum number achievable by such steps.

For example if given 2 3 1 1 2 2 then the maximum possible is 4:

2 3 1 1 2 2 ---> 2 3 2 2 2 ---> 2 3 3 2 ---> 2 4 2.

It is evident that I should try to do better than the maximum number available in the sequence. But I can't figure out a good algorithm.

Answer 1

Each substring of the input can make at most one single number (invariant: the log base two of the sum of two to the power of each entry). For every x, we can find the set of substrings that can make x. For each x, this is (1) every occurrence of x (2) the union of two contiguous substrings that can make x - 1. The resulting algorithm is O(N^2)-time.

Answer 2

An algorithm could work like this:

Convert the input to an array where every element has a frequency attribute, collapsing repeated consecutive values in the input into one single node. For example, this input:

1 2 2 4 3 3 3 3

Would be represented like this:

{val: 1, freq: 1}  {val: 2, freq: 2}  {val: 4, freq: 1}  {val: 3, freq: 4}  

Then find local minima nodes, like the node (3 3 3 3) in 1 (2 2) 4 (3 3 3 3) 4, i.e. nodes whose neighbours both have higher values. For those local minima that have an even frequency, "lift" those by applying the step. Repeat this until no such local minima (with even frequency) exist any more.

Start of the recursive part of the algorithm:

At both ends of the array, work inwards to "lift" values as long as the more inner neighbour has a higher value. With this rule, the following:

1 2 2 3 5 4 3 3 3 1 1

will completely resolve. First from the left side inward:

1 4 5 4 3 3 3 1 1

Then from the right side:

1 4 6 3 2

Note that when there is an odd frequency (like for the 3s above), there will be a "remainder" that cannot be incremented. The remainder should in this rule always be left on the outward side, so to maximise the potential towards the inner part of the array.

At this point the remaining local minima have odd frequencies. Applying the step to such a node will always leave a "remainder" (like above) with the original value. This remaining node can appear anywhere, but it only makes sense to look at solutions where this remainder is on the left side or the right side of the lift (not in the middle). So for example:

4 1 1 1 1 1 2 3 4

Can resolve to one of these:

4  2   2  1 2 3 4

Or:

4 1  2  2   2 3 4

The 1 in either second or fourth position, is the above mentioned "remainder". Obviously, the second way of resolving is more promising in this example. In general, the choice is obvious when on one side there is a value that is too high to merge with, like the left-most 4 is too high for five 1 values to get to. The 4 is like a wall.

When the frequency of the local minimum is one, there is nothing we can do with it. It actually separates the array in a left and right side that do not influence each other. The same is true for the remainder element discussed above: it separates the array into two parts that do not influence each other.

So the next step in the algorithm is to find such minima (where the choice is obvious), apply that kind of step and separate the problem into two distinct problems which should be solved recursively (from the top). So in the last example, the following two problems would be solved separately:

4
2 2 3 4

Then the best of both solutions will count as the overall solution. In this case that is 5.

The most challenging part of the algorithm is to deal with those local minima for which the choice of where to put the remainder is not obvious. For instance;

3 3 1 1 1 1 1 2 3

This can go to either:

3 3  2   2  1 2 3
3 3 1  2   2  2 3

In this example the end result is the same for both options, but in bigger arrays it would be less and less obvious. So here both options have to be investigated. In general you can have many of them, like 2 in this example:

3 1 1 1 2 3 1 1 1 1 1 3

Each of these two minima has two options. This seems like to explode into too many possibilities for larger arrays. But it is not that bad. The algorithm can take opposite choices in neighbouring minima, and go alternating like this through the whole array. This way alternating sections are favoured, and get the most possible value drawn into them, while the other sections are deprived of value. Now the algorithm turns the tables, and toggles all choices so that the sections that were previously favoured are now deprived, and vice versa. The solution of both these alternatives is derived by resolving each section recursively, and then comparing the two "grand" solutions to pick the best one.

Snippet

Here is a live JavaScript implementation of the above algorithm. Comments are provided which hopefully should make it readable.

"use strict";

function Node(val, freq) {
    // Immutable plain object
    return Object.freeze({
        val: val,
        freq: freq || 1, // Default frequency is 1.
        // Max attainable value when merged:
        reduced: val + (freq || 1).toString(2).length - 1
    });
}

function compress(a) {
    // Put repeated elements in a single node
    var result = [], i, j;
    for (i = 0; i < a.length; i = j) {
        for (j = i + 1; j < a.length && a[j] == a[i]; j++);
        result.push(Node(a[i], j - i));
    }
    return result;
}

function decompress(a) {
    // Expand nodes into separate, repeated elements
    var result = [], i, j;
    for (i = 0; i < a.length; i++) {
        for (j = 0; j < a[i].freq; j++) {
            result.push(a[i].val);
        }
    }
    return result;
}

function str(a) {
    return decompress(a).join(' ');
}

function unstr(s) {
    s = s.replace(/\D+/g, ' ').trim();
    return s.length ? compress(s.split(/\s+/).map(Number)) : [];
}

/*
 The function merge modifies an array in-place, performing a "step" on 
 the indicated element.
 The array will get an element with an incremented value
 and decreased frequency, unless a join occurs with neighboring 
 elements with the same value: then the frequencies are accumulated
 into one element. When the original frequency was odd there will 
 be a "remainder" element in the modified array as well.
*/
function merge(a, i, leftWards, stats) {
    var val = a[i].val+1,
        odd = a[i].freq % 2,
        newFreq = a[i].freq >> 1,
        last = i;
    // Merge with neighbouring nodes of same value:
    if ((!odd || !leftWards) && a[i+1] && a[i+1].val === val) {
        newFreq += a[++last].freq;
    }
    if ((!odd || leftWards) && i && a[i-1].val === val) {
        newFreq += a[--i].freq;
    }   
    // Replace nodes
    a.splice(i, last-i+1, Node(val, newFreq));
    if (odd) a.splice(i+leftWards, 0, Node(val-1));
    
    // Update statistics and trace: this is not essential to the algorithm
    if (stats) {
        stats.total_applied_merges++;
        if (stats.trace) stats.trace.push(str(a));
    }
    return i;
}

/*  Function Solve
    Parameters:
        a:  The compressed array to be reduced via merges. It is changed in-place
            and should not be relied on after the call.
        stats:  Optional plain object that will be populated with execution statistics.
    Return value:
        The array after the best merges were applied to achieve the highest
        value, which is stored in the maxValue custom property of the array.
*/
function solve(a, stats) {
    var maxValue, i, j, traceOrig, skipLeft, skipRight, sections, goLeft,
        b, choice, alternate;
    
    if (!a.length) return a;

    if (stats && stats.trace) { 
        traceOrig = stats.trace;
        traceOrig.push(stats.trace = [str(a)]);
    }

    // Look for valleys of even size, and "lift" them
    for (i = 1; i < a.length - 1; i++) {
        if (a[i-1].val > a[i].val && a[i].val < a[i+1].val && (a[i].freq % 2) < 1) {
            // Found an even valley
            i = merge(a, i, false, stats);
            if (i) i--;
        }
    }
    // Check left-side elements with always increasing values
    for (i = 0; i < a.length-1 && a[i].val < a[i+1].val; i++) {
        if (a[i].freq > 1) i = merge(a, i, false, stats) - 1;
    };
    // Check right-side elements with always increasing values, right-to-left
    for (j = a.length-1; j > 0 && a[j-1].val > a[j].val; j--) {
        if (a[j].freq > 1) j = merge(a, j, true, stats) + 1;
    };
    // All resolved?
    if (i == j) {
        while (a[i].freq > 1) merge(a, i, true, stats);
        a.maxValue = a[i].val;
    } else {
        skipLeft = i;
        skipRight = a.length - 1 - j;
        // Look for other valleys (odd sized): they will lead to a split into sections
        sections = [];
        for (i = a.length - 2 - skipRight; i > skipLeft; i--) {
            if (a[i-1].val > a[i].val && a[i].val < a[i+1].val) {
                // Odd number of elements: if more than one, there
                // are two ways to merge them, but maybe 
                // one of both possibilities can be excluded.
                goLeft = a[i+1].val > a[i].reduced;
                if (a[i-1].val > a[i].reduced || goLeft) {
                    if (a[i].freq > 1) i = merge(a, i, goLeft, stats) + goLeft;
                    // i is the index of the element which has become a 1-sized valley
                    // Split off the right part of the array, and store the solution
                    sections.push(solve(a.splice(i--), stats));
                }
            }
        }
        if (sections.length) {
            // Solve last remaining section
            sections.push(solve(a, stats));
            sections.reverse();
            // Combine the solutions of all sections into one
            maxValue = sections[0].maxValue;
            for (i = sections.length - 1; i >= 0; i--) {
                maxValue = Math.max(sections[i].maxValue, maxValue);
            }
        } else {
            // There is no more valley that can be resolved without branching into two
            // directions. Look for the remaining valleys.
            sections = [];
            b = a.slice(0); // take copy
            for (choice = 0; choice < 2; choice++) {
                if (choice) a = b; // restore from copy on second iteration
                alternate = choice;
                for (i = a.length - 2 - skipRight; i > skipLeft; i--) {
                    if (a[i-1].val > a[i].val && a[i].val < a[i+1].val) {
                        // Odd number of elements
                        alternate = !alternate
                        i = merge(a, i, alternate, stats) + alternate;
                        sections.push(solve(a.splice(i--), stats));
                    }
                }
                // Solve last remaining section
                sections.push(solve(a, stats));
            }
            sections.reverse(); // put in logical order
            // Find best section:
            maxValue = sections[0].maxValue;
            for (i = sections.length - 1; i >= 0; i--) {
                maxValue = Math.max(sections[i].maxValue, maxValue);
            }
            for (i = sections.length - 1; i >= 0 && sections[i].maxValue < maxValue; i--);
            // Which choice led to the highest value (choice = 0 or 1)?
            choice = (i >= sections.length / 2)
            // Discard the not-chosen version
            sections = sections.slice(choice * sections.length/2);
        }
        // Reconstruct the solution from the sections.
        a = [].concat.apply([], sections);
        a.maxValue = maxValue;
    }
    if (traceOrig) stats.trace = traceOrig;
    return a;
}

function randomValues(len) {
    var a = [];
    for (var i = 0; i < len; i++) {
        // 50% chance for a 1, 25% for a 2, ... etc.
        a.push(Math.min(/\.1*/.exec(Math.random().toString(2))[0].length,5));
    }
    return a;
}

// I/O
var inputEl = document.querySelector('#inp');
var randEl = document.querySelector('#rand');
var lenEl = document.querySelector('#len');
var goEl = document.querySelector('#go');
var outEl = document.querySelector('#out');

goEl.onclick = function() {
    // Get the input and structure it
    var a = unstr(inputEl.value),
        stats = {
            total_applied_merges: 0,
            trace: a.length < 100 ? [] : undefined
        };
    // Apply algorithm
    a = solve(a, stats);
    // Output results
    var output = {
        value: a.maxValue,
        compact: str(a),
        total_applied_merges: stats.total_applied_merges,
        trace: stats.trace || 'no trace produced (input too large)'
    };
    outEl.textContent = JSON.stringify(output, null, 4);
}

randEl.onclick = function() {
    // Get input (count of numbers to generate):
    len = lenEl.value;
    // Generate
    var a = randomValues(len);
    // Output
    inputEl.value = a.join(' ');
    // Simulate click to find the solution immediately.
    goEl.click();
}

// Tests
var tests = [
    ' ', '',
    '1', '1',
    '1 1', '2',
    '2 2 1 2 2', '3 1 3',
    '3 2 1 1 2 2 3', '5',
    '3 2 1 1 2 2 3 1 1 1 1 3 2 2 1 1 2', '6',
    '3 1 1 1 3', '3 2 1 3',
    '2 1 1 1 2 1 1 1 2 1 1 1 1 1 2', '3 1 2 1 4 1 2',
    '3 1 1 2 1 1 1 2 3', '4 2 1 2 3',
    '1 4 2 1 1 1 1 1 1 1', '1 5 1',
];

var res;
for (var i = 0; i < tests.length; i+=2) {
    var res = str(solve(unstr(tests[i])));
    if (res !== tests[i+1]) throw 'Test failed: ' + tests[i] + ' returned ' + res + ' instead of ' + tests[i+1];
}

Enter series (space separated):<br> 
<input id="inp" size="60" value="2 3 1 1 2 2"><button id="go">Solve</button>
<br>
<input id="len" size="4" value="30"><button id="rand">Produce random series of this size and solve</button>
<pre id="out"></pre>

As you can see the program produces a reduced array with the maximum value included. In general there can be many derived arrays that have this maximum; only one is given.

Answer 3

An O(n*m) time and space algorithm is possible, where, according to your stated limits, n <= 500 and m <= 58 (consider that even for a billion elements, m need only be about 60, representing the largest element ± log2(n)). m is representing the possible numbers 50 + floor(log2(500)):

Consider the condensed sequence, s = {[x, number of x's]}.

If M[i][j] = [num_j,start_idx] where num_j represents the maximum number of contiguous js ending at index i of the condensed sequence; start_idx, the index where the sequence starts or -1 if it cannot join earlier sequences; then we have the following relationship:

M[i][j] = [s[i][1] + M[i-1][j][0], M[i-1][j][1]]
  when j equals s[i][0]

j's greater than s[i][0] but smaller than or equal to s[i][0] + floor(log2(s[i][1])), represent converting pairs and merging with an earlier sequence if applicable, with a special case after the new count is odd:

When M[i][j][0] is odd, we do two things: first calculate the best so far by looking back in the matrix to a sequence that could merge with M[i][j] or its paired descendants, and then set a lower bound in the next applicable cells in the row (meaning a merge with an earlier sequence cannot happen via this cell). The reason this works is that:

1. if s[i + 1][0] > s[i][0], then s[i + 1] could only possibly pair with the new split section of s[i]; and
2. if s[i + 1][0] < s[i][0], then s[i + 1] might generate a lower j that would combine with the odd j from M[i], potentially making a longer sequence.

At the end, return the largest entry in the matrix, max(j + floor(log2(num_j))), for all j.

JavaScript code (counterexamples would be welcome; the limit on the answer is set at 7 for convenient visualization of the matrix):

function f(str){

  var arr = str.split(/\s+/).map(Number);

  var s = [,[arr[0],0]];

  for (var i=0; i<arr.length; i++){
    if (s[s.length - 1][0] == arr[i]){
      s[s.length - 1][1]++;
    } else {
      s.push([arr[i],1]);
    }
  }

  var M = [new Array(8).fill([0,0])], 
      best = 0;

  for (var i=1; i<s.length; i++){
    M[i] = new Array(8).fill([0,i]);

    var temp = s[i][1],
        temp_odd,
        temp_start,
        odd = false;

    for (var j=s[i][0]; temp>0; j++){
   
      var start_idx = odd ? temp_start : M[i][j-1][1];

      if (start_idx != -1 && M[start_idx - 1][j][0]){
        temp += M[start_idx - 1][j][0];
        start_idx = M[start_idx - 1][j][1];
      }

      if (!odd){
        M[i][j] = [temp,start_idx];
        temp_odd = temp;
      } else {  
        M[i][j] = [temp_odd,-1];
        temp_start = start_idx;
      }

      if (!odd && temp & 1 && temp > 1){
        odd = true;
        temp_start = start_idx;
      }

      best = Math.max(best,j + Math.floor(Math.log2(temp)));

      temp >>= 1;
      temp_odd >>= 1;
    }
  }

  return [arr, s, best, M];
}

// I/O
var button = document.querySelector('button');
var input = document.querySelector('input');
var pre = document.querySelector('pre');

button.onclick = function() {
  var val = input.value;
  var result = f(val);
  var text = '';
  for (var i=0; i<3; i++){
    text += JSON.stringify(result[i]) + '\n\n';
  }
  for (var i in result[3]){
    text += JSON.stringify(result[3][i]) + '\n';
  }
  pre.textContent = text;
}

<input value ="2 2 3 3 2 2 3 3 5">
<button>Solve</button>
<pre></pre>