Disclaimer

I do not know if this technique has another name. I came up with it to solve specific types of problems but it probably has been done by many others before.

The situation

Assume we are given a sequence of numbers a₁, a₂, ..., a_n - 1, a_n and we have a function f that is well defined for all sequences of numbers with the property f(b₁, ..., b_m) = f(f(b₁, ..., b_m - 1), b_m) for any sequence b and the range of f has size K, which is relatively small. Our goal is to rearrange the numbers a₁, ..., a_n so that when the sequence is entered into f in this order the value of f is optimised (minimised or maximised).

The solution

If we try to brute force all permutations of the sequence there are n! options which is usually too slow. However what we can do is use dynamic programming and for each sequence ending in a_j with m terms store all possible values of f. Since we know the range of f is K at each step we are storing at most K terms.

Cost analysis

To calculate all possible values of f for a sequence ending in a_j with m + 1 terms given we have calculated all possible values for f with sequence with m terms we need at most (n - 1)K calculations. Doing this for each term to calculate all possible values for f with a sequence of m + 1 terms gives at most n(n - 1)K calculations. Doing it n times since we need sequences of length n gives at most n²(n - 1)K. Finally to find the optimised value requires at most nK more calculations. So at worst we have n²(n - 1)K + nK calculations.

Noticing the situation

The nature of the function is what determines whether this situation occurs. If the function is based on bitwise operations and the values of the sequence are small there is a good chance that this technique applies. Also if the function is based on arithmetic modulo N where N is small this technique might also apply.

Worked Example

I used this technique to solve the problem trysail from topcoder. https://community.topcoder.com/stat?c=problem_statement&pm=14307. The general idea of the question is you have a sequence of at most 50 numbers that are between 0 and 255 and you want to split them into three non-empty groups so that when you take the xor of each group and sum them the result is maximised.

My approach: First we note when we xor any group of elements the result will be an integer between 0 and 255 inclusive. Next xor clearly satisfies the property required for f given above. These are strong hints that we can use the function range trick. Next we need to figure out a way to deal with three groups. Since the numbers are small we can store the xor of each group in an int letting the first 8 bits store group 1, the next 8 bits store group 2 and the next 8 bits store group 3. We also note since we are only concerned with maximising the sum we can treat certain groupings as equivalent to reduce the number of cases to consider.

Now assume for the first i elements we have stored all the xors of all possible groupings and we want to add the i+1th element and get the xors of all possible groupings with first i+1 elements. Turns out for each possible grouping there are six ways to do this up to equivalence, we either add the new element to one of the existing groups or give the new element its own group and combine the three previous groups into two. This is where the function range trick comes into play. Even though it looks like we are generating a lot of new groups every time we add a new element since the range of xor is limited many of these new groupings result in the same value for xor. Implementation wise we can use a set for storage so repeated elements will only be stored once.

Code ~~~~~~

include

include

include

include

using namespace std;

class TrySail{

public:
int get(vector<int> v){
    set<int> prev; 

    //put the first three elements in a separate group
    prev.insert(v[0]+(v[1]<<8)+(v[2]<<16));

    //given all possible xors when i elements are grouped
    //store all possible xors when i+1 elements are grouped
    for(int i=3; i<v.size(); i++){
        set<int> next;

        for(int j:prev){
            next.insert(j^v[i]);
            next.insert(j^(v[i]<<8));
            next.insert(j^(v[i]<<16));

            int x=j%(1<<8);
            int y=(j>>8)%(1<<8);
            int z=j>>16;
            next.insert(v[i]+((x^y)<<8)+(z<<16));
            next.insert(v[i]+((x^z)<<8)+(y<<16));
            next.insert(v[i]+((y^z)<<8)+(x<<16));
        }
        prev=next;
    }
    int ans=0;

    //find the largest answer
    for(int i:prev){
        int x=i%(1<<8);
        int y=(i>>8)%(1<<8);
        int z=i>>16;


        int sum=x+y+z;
        ans=max(ans,sum);
    }

    return ans;
}

};

~~~~~

As a final note this code passes the system tests but it gets quite close to the time limit for certain inputs with 50 elements.