SRM 493, div1 450 : AmoebaCode

Problem statement

It seems that the key observation and the one I missed during the match is to find an upper bound for the result.

The maximum minimum distance between two equal digits is actually K. I think that intuition is necessary to suspect so and afterwards, you can prove by using the following logic:

We have two indexes i<j, the digits code[i] and code[j] are equal. And we would like to assume that there are no other equal digits between them, so the distance is j-i, and we would like to say that j-i is also the minimum distance. To ensure this, all the digits between them must be unique. That is because if two of the digits between i and j were equal, let us say two indexes a,b such that i < a < b < j and code[a]=code[b], then the minimum distance would actually be b-a , because b-a < j-i .

So, assume that the minimum distance in a code is K+1 . Then we would have two digits code[i],code[j] that are equal such that j-i = K+1 .This implies there are K digits between them. We know that the digits must be unique, and that the digits must be different to code[i]. Then we have K-1 available digits that must be put in K slots, one of the slots would forcefully have to use a repeated digit. For higher values of the minimum distance, K+2, K+3, etc, it is even harder because there are even more slots to fill. But if we tried exactly K, then there would be exactly K-1 slots to fill with K-1 which is possible. We can conclude that the maximum possible minimum distance for a given K is equal to K.

If we know that the result is at most K, then for each digit in the code, we only need to check the previous K-1 digits and the next K-1 digits. If none of those digits is equal to the digit we are checking, then we can conclude that either the distance between the digit and a duplicate is at least K, or maybe the digit has no duplicates. However, due to the previous demonstration, at least one pair of digits will have a distance of K or less. So, we can just ignore digits that do not have a pair with K-1 digits of distance.

Now, imagine we are putting digits in the code in order from 0 to n-1. When thinking of what digit to place in an index i, we do not need the list of all the digits we put before i, we only need the previous K-1 digits. This list of K-1 digits, is much smaller than one of potentially n-1 digits, with K<=7, the total of such lists would be 7^7-1=117649 (for each of the K-1 slots, pick a number between 1 and K).

So, consider the following recursion: We have a list of K-1 digits that come before our current index p. Say we pick a digit D. If D is in position x of the list of K-1 digits, then the current minimum distance that we know of is dist=K-1-x. If the digit is not in the list, we can assume the distance is dist=K, if the distance was higher than K, it would not matter, this distance will be canceled by a smaller distance anyway (we only care about the minimum). We have to generate a new list of digits that includes D and disposes of the first digit of the list. We can call the recursion again with (newlist, p+1) , the result of this recursion will be the maximum minimum distance for the remaining indexes. The minimum between (dist, the called recursion's result) is the maximum distance we can get by using digit D in position p. If we try all possible digits D, and pick the maximum distance that can be acquired by any of the digits, we have the result.

If we are out of indexes, we can just return K, again, in case K is not the minimum distance, it will be canceled later.

Since there are only at most 117649 lists, at most 50 positions and in each step of the recursion we may need to try K possible digits, we can use dynamic programming or memoization to implement this recursion and it should take O(K^K-1* n * K) or O(K^K* n). This is fast enough to run in C++ but not that fast. I think there should be improvements available or a faster solution.

Implementation details such as how to make the list as an argument remain. I just encoded the list in a number from 0 to K^K-1 , so it is basically a base K number. To quickly access its indexes I use a powK array that contains all the necessary powers of K.

Some C++ code:

using namespace std;
int mem[51][117649];

struct AmoebaCode
{
    string code;
    int k;
    int powk[10];
    int rec(int last, int p) {
        int&res=mem[p][last];
        if(res==-1) {
            if(p==code.size() ) {
                //The end, return K, if the result is smaller, it will
                //be cancelled in a top call.
                res = k;
            } else {
                //find the distances between digits and the values in
                //the list, if the digit is not in the list, assume
                //the distance is K.
                int dis[k];
                fill(dis,dis+k, k);
                for (int i= std::max(p-(k-1),0); i<p; i++) {
                    int x = (last/powk[i-p+k-1])%k;
                    dis[x] = p-i;
                }
                //Try all values i for a digit, keep the maximum minimum distance
                res = 0;
                for (int i=0; i<k; i++) {
                    if( (code[p]=='0') || (code[p]-'1'==i) ) {
                        int nlast = last/k + i*powk[k-2];
                        res = std::max( res, std::min(dis[i], rec( nlast, p+1) ) );
                    }
                }
            }
        }
        return res;
    }
    int find(string code, int K)
    {
        if(K==1) {
            return 1;
        }
        //initiallize arrays and variables.
        memset(mem,-1, sizeof(mem));
        powk[0] = 1;
        for (int i=1; i<10; i++) {
            powk[i] = K*powk[i-1];
        }
        this->code = code;
        this->k = K;
        
        //call the recursion.
        return rec(0,0);
    }
};

This turned out to be a interesting problem. I think the reason it was so difficult during the match and turned out harder than the admins expected is that it is not actually as easy to see the K boundary for the result. I could not notice it during the 22 minutes I gave to this problem during the match, and it did not occur to me until today in the afternoon.