Member SRM 501 - FoxProgression

FoxProgression problem statement.
This division 2 problem was kindly donated by wrong. Make no mistake, thinking of good problems is not easy, so giving them for free to Topcoder just so that we still get to get three SRMs a month instead of only two, is a good thing.

This problem asks us to count the number of ways we could add a new element to a sequence so that the final sequence is an arithmetic progression or a geometric progression. Perhaps the first thing to notice is that the element added is always going to be the last element. We cannot insert this element in the middle of the sequence, this means that we cannot really modify the nature of the first elements of the sequence. If the original sequence is not an arithmetic progression, then we cannot make it an arithmetic progression by adding a new element to the last position. The same happens with geometric progressions.

For now, we will focus on the arithmetic progression aspect of it. If the original sequence seq is an arithmetic progression, then for every i seq[i]-seq[i-1] = a constant. We will call this constant dif as seq[i]-seq[i-1] is a difference. How can we find dif? Simply pick any pair of consecutive elements, and subtract them. We will pick the first two elements: (dif = seq[1] - seq[0]). Now, note that we should not make assumptions, the original sequence will not necessarily have at least two elements. How can we calculate dif if the sequence only has one element?

If the sequence only has one element, it does not really matter, we could add any number to it and the result will be an arithmetic sequence. Because all sequences of two elements have a single difference between its only two elements, which are consecutive. This means that if the original sequence only had one element, there would be infinitely many numbers we could add. The problem statement specifies that this situation is possible, and it tells us to return -1 in that case. Therefore, if the sequence has one element, return -1.

Back to cases with more than one element in the sequence. We have calculated (dif = seq[1]-seq[0]) for the original sequence to be an arithmetic progression, we should verify that for every i, (seq[i]-seq[i-1] = dif). This will imply that the difference is always constant. In case we find that the difference is constant, we can claim that seq is an arithmetic progression, we can also claim that dif is the constant difference. Do not forget that we are going to add a number X to the end of this sequence, and that the new sequence must stay an arithmetic progression, because of this: (X - seq[n-1] = dif) Where seq[n-1] is the last element in the original sequence. We can conclude that if (X = seq[n-1] + dif), then we can have an arithmetic progression after adding X and only after adding X.

In the case of geometric progressions, the situation is very similar, except that we will have a constant q such that: (q * seq[i-1] = seq[i]). The value of q can be calculated by (q = seq[i] / seq[i-1] ). Note that we are doing a division so we would not want seq[i-1] to be 0, but that is not a problem because all elements of seq are going to be greater than 0 per the constraints definition. Then we can use the newly found value of q, and make sure that the sequence is geometric, that is : (q*seq[i-1] = seq[i] ) . Note that it is not convenient to use division in this case because of rounding causing issues. If the sequence is a geometric progression and the constant factor is q, then we can say that a new number Y to be added to the end of the sequence must be such that: (Y = seq[n-1]*q ).

Adding both logics together includes some challenges. There are four cases to consider:

• The sequence is both an arithmetic and a geometric progression.- This can actually happen with for example seq={4,8} (From the examples) 4+4 = 8 and also 4*2 = 8. If we follow the logics from the previous paragraphs, we will find that (X = 8+4 = 12) and (Y = 8*2 = 16) . In other words, we can add both 12 and 16 to the sequence and the new sequence will be arithmetic or geometric. In this case the result is 2, there are two different number (12 and 16) that do the job.
  
  It is actually possible that both X and Y are equal. In example 2) seq = {1,1} and (X = 1+0 = 1) and (Y = 1*1 = 1). Since both are equal, there is only one number (1) that we need to count. The result is 1.
  
  The trick is to simply say: If (X=Y) then the result is 1, else it is 2. Some coders made the mistake of assuming that only {1,1} was special like this and only handled that specific sequence. But for example, {500,500,500} and any sequence of equal numbers will have equal values of X and Y.
  


• The sequence is only an arithmetic progression.- Then the only number that can do the job is X, the result is 1.


• The sequence is only a geometric progression.- Then the only number that can do the job is Y, the result is 1. We can add these two cases together and just say that if the sequence is only arithmetic or only geometric, the result is 1.


• The sequence is neither arithmetic nor geometric.- Then we cannot do anything, we can add any number, the new sequence will not become arithmetic or geometric because we cannot change the first part of it. The result is 0.

Hey, this problem was definitely easier to solve than to explain, but it may be clearer with just some sample source code:

int theCount(vector <int> seq)
{
    int n = seq.size();
    // If there is only one element,
    // then there are infinitely many ways
    // to have this.
    if (n==1) {
        return -1;
    }
    // Arithmetic difference
    int dif = seq[1] - seq[0];
    // Geometric factor
    int q = seq[1] / seq[0];
    
    // Verify that the sequence is arithmetic/gemetric or both
    bool cangeo = true;
    bool canari = true;
    for (int i=1; i<n; i++) {
        canari &= ( seq[i]-seq[i-1] == dif );
        cangeo &= ( seq[i-1]*q == seq[i] );
    }
    // Possible values for the next element in the
    // arithmetic progression and the geometric progression
    int x = seq[n-1]*q;
    int y = seq[n-1]+dif;
    
    // If both are possible, verify that the numbers are
    // actually different, For example with {1,1} it is
    // possible to have {1,1,1} no matter if we use an
    // arithmetic progression or a geometric one. (example 2)
    if ( cangeo && canari ) {
        return ( x!=y ) ? 2 : 1;
    } else if (cangeo || canari) {
        return 1;
    } else {
        return 0;
    }
    
}

Read More

Some late SRM reports

I have not been logging things correctly into my blog, so I will try to do some recap.


SRM 498: A most horrendous rating drop. This SRM made me notice that the Hard-medium-easy strategy was not working. Case in point, due to it being justifiable for me to do badly when using this strategy, I was not taking SRMs seriously. I failed the easy problem because of not doing a O(n^5) even though everything indicated it would work fine. For some reason I thought that this time, doing ad hoc checks was going to be simpler to code than a n*n*n*n loop. Although in a way it was, it was very easy to miss a single mistake which was not caught by the example tests. Blunder: Trying clever code instead of one you know is going to work is not a good idea. It is going to take a while to recover the 145 rating points that were lost that day.

SRM 499: I decided to move to a new strategy which is similar to the one I was using until 2010. I start with the medium-difficulty problem first. However, instead of switching to the easy when there are 30 minutes left, I wait until there are only 15 minutes left. This way, I will force myself to take the medium more seriously than before, and also to be fast at solving the 250. I was tired of taking whole half hours to solve the "Easy" problem, I'd rather get 0 points...

This match's results were nice, they gave me hope about the new strategy. After trying the 500 problem for a while, I got very close to the dp solution, but I was having trouble with some of the example cases. I had to switch to the easy problem when there were only 15 minutes left. But it turned out to be a very easy problem that only took me 4 minutes to solve. When I returned to the 500, my mind was refreshed and it finally struck-me : I had cycles in the recurrence. Before doing memoization, always make sure your recurrence is cyclic, it is the basic thing to do. I managed to fix the cycle, and submit. Everything went well.

I was assigned to write the editorial for this match. I think the 1000 points problem was very nice, but that's probably because I don't usually get the chance to see Strongly-Connected-Components used in problems that are not easily simplified to them.

SRM 500: Did not like this match. I think that a harder than usual 250 was not suitable for a celebration kind of match. It became a downer. Actually there were some other old timers in my room and we were all saying basically the same during intermission. The 500-pointer was nice. I actually had something that resembled a correct solution to it but had problems debugging it. I made the mistake to switch to the other problem at a very bad time. I should have switched much earlier or not switch at all.

Member SRM 501
I open the 500 first. I was able to think of a dynamic programming solution very quickly. So much that I initially thought that the challenge in this problem was that O(n⁵) was not going to work and O(n⁴) was required. But I noticed that with memoization you can do plenty of cropping if your recurrence includes the current sum and also that the constraint for the length was 40 and not 50. Those things gave me enough of a reason to try and code the O(n⁴) solution and try it in the worst case. It turns out it solved the worst case - an array full of -1 - in less than 0.8 seconds.

The easy was a different story. At first, I noticed that it is probably never necessary not to do all the additions consecutively. So operations are always in the form BB...BAA...ABB..B , the first B operations do nothing because they are multiplied with 0. Then the other ones multiply nA * a (The result of all the additions). I unfortunately make the mistake to, after reading the examples, assume that the number of times to multiply b is either 0 (When it is not convenient to multiply at all), nB (When it is convenient to multiply as much as possible) or nB-1 (when the factor b is negative, it pays to do multiply only an even number of times). This passed the example tests, and I submitted the solution. But I had many doubts.

Blunder: nB was actually constrained to be less than or equal to 50. I could have actually just picked all possible values of t=0,1,...nB to raise b to before multiplying it to nA*a. Instead, I only picked 0, nB and nB-1, this was an unnecessary assumption.

I had my suspicions after noticing the low constraints for nA and nB. Tried to make a dynamic programming solution, but I was unfortunately having issues implementing it correctly. Blunder: I switched to the 1000 points problem before making sure the 250 was correct. Some time after, I noticed I really had no clue how to solve the 1000-pointer. So, I kept opening 500 and 250 trying to find typing errors. I eventually figured I could just code a bruteforce solution for 250, that would only work when nA+nB<=10, so I could call both of my solutions with random cases and see if they always agree. After finishing the bruteforce solution and making a program that would generate random cases for the solutions, it didn't took the random number generator much time before finding a case my original solution failed: {1, 8, -2.097, -0.883} After some inspection, I noticed that in that case we need to multiply b exactly once. This is the moment where I finally noticed that I can pick any number of times to multiply b between 0 and nB. After changing the solution to do that, I ran the random number generator again, and it was not finding any mistake. I submitted the new solution, but a long time had passed since the first submission, I ended up getting only 79 points for it.

During the challenge phase, I knew that the test case I found during the coding phase was going to make plenty of solutions to fail, but I just couldn't find the wrong solutions, and parse them well enough to notice they didn't resist that case before they were challenged. After the match I noticed that if I just used that challenge blindly on all the lower rated coders in the room I would have been able to recover all that I lost because of the resubmission. But I am not really an aggressive challenger, and I am not sure how well this sort of blind challenging strategy would work in general. What I can tell is that aggressive challenges are not my style, so I am probably not going to try it soon.

I am not sure if the 500 was too easy or if I am just too used to dynamic programming problems. I could tell many of the submissions had very long, complicated codes for some reason.

Read More

If all you have is a hammer...

I have not been commenting SRMs as usual but anyway, I did actually write two topcoder editorials since the last time I posted something. Every time I write those editorials, there is something that really, really annoys me. It is that TC wiki does not have a method like the topcoder forums to use a handle tag ([h]vexorian[/h]) and instead you will need to manually do something like <a href='http://www.topcoder.com/tc?module=MemberProfile&cr=22652965' class='coderTextYellow'>vexorian<</a>. Looking for handle codes and colors is very hard and you will need to do this for every handle name you mention in the whole editorial. It is very annoying.

it is very mechanical work, and ever since the first time I kept having fantasies about coding something that would do it for me. After Sunday's editorial, I finally decided to do it. I used python as an excuse to continue learning python. But it is just python 2.0 because I did not have python 3.0 installed in my computer. It will translate every [h]name[/h] instance into TC wiki-friendly HTML. It uses a web connection to download profile pages because I am not sure if there are data feeds for just handle names and not for whole competitions. Maybe there are... Beware that it is very noobish python. I spent most of the coding time googling python's documentation to learn about how to download stuff and use regexes.

For some reason, blogger does not allow something as simple as sharing files that are not images or video, so here is the raw python code.

Update: Oh well, it seems blogspot fails too much for code and does not even bother to add a scroll bar when it is too wide.

New update: Hey! The power of rockCSS has saved me once again...

Update: The new version has an interactive mode, just call the script without arguments, it will allow you to type handle names and will generate an anchor tag for each handle you type.


Update: Fix John Dethridge bug and it now works with the new profile pages.

# Topcoder handle tag script for HTML files you make manually. 
# it is probably a bad idea to use it in anything else because it abuses TC's 
# server to find the information. 
# 
# err let us say it is released under the zlib/libpng license 
# http://www.opensource.org/licenses/zlib-license 
# (c) Victor Hugo Soliz Kuncar, 2011  
# 
# Update August 2012, 
# Fix John Dethridge bug and make it compatible with new profile pages 
# 
import urllib, re, sys, os, time 
 
# 
# RatingName feature removed because it is no longer trivial to do it. 
# 
 
# Rudimentary proxy support 
#  For example: 
#  PROXIES = {'http': 'http://7.7.7.7:3128'} 
PROXIES = None 
 
# Style picker based on rating. Admins get -1 rating in this script. 
RATING_CLASSES = [ (-1,-1,'coderTextOrange'), (0,0,'coderTextBlack'), (1,899,'coderTextGray'), (900,1199,'coderTextGreen'), (1200,1499,'coderTextBlue'), (1500,2199,'coderTextYellow'), (2200,1e100,'coderTextRed') ]  
 
REGEX_RATING = re.compile('<span class="coderText[a-zA-Z]+">\s*(\d+)\s*</span>') 
 
REGEX_CR     = re.compile('cr=(\d+)') 
REGEX_ADMIN  = re.compile('<a\s+href="[^"]*"\s+class="coderTextOrange">\s*([^\s<]+)\s*</a>') 
 
# John Dethridge is the only topcoder that gets to have a space character in his name. Nice! 
REGEX_HTAG = re.compile('\[h\]((\S+)|(John Dethridge))\[/h\]') 
 
 
CACHE = dict() 
 
QUERY_COUNT = 0 
def getTCDataNoCache(handle): 
    # Wait 0.5 seconds between queries, and 2 seconds every 10 queries 
    # we are not DDoSing TC... 
    global QUERY_COUNT 
    if QUERY_COUNT == 10 : 
        QUERY_COUNT = 0 
        time.sleep(2.0) 
    else: 
        time.sleep(0.5) 
    QUERY_COUNT += 1 
  
    #download the profile using the search form... 
    params = urllib.urlencode({'module': 'SimpleSearch', 'ha': handle.replace('_','\\_')}) 
    f = urllib.urlopen("http://www.topcoder.com/tc?%s" % params, proxies = PROXIES) 
     
    # Extract the cr 
    m = REGEX_CR.search( f.geturl() ) 
    if m == None : 
        print 'Note: "%s" profile not found'%(handle) 
        return (0,0) 
    cr = int(m.group(1)) 
     
    html = f.read() 
     
    #admin check 
    m = REGEX_ADMIN.search(html) 
    if ( m != None and m.group(1) == handle ) : 
        print 'Note: %s is an admin.'%(handle) 
        return (cr, -1) 
     
    # extract rating (or at least try) 
    m = REGEX_RATING.search(html) 
    if m == None : 
        print 'Note: "%s" profile not understood, assuming 0 rating.'%(handle) 
        return (cr,0) 
     
    rat = m.group(1) 
     
    if rat == 'not' : 
        print 'Note: %s is not rated.'%(handle) 
        rat = 0 
    return (cr,int(rat)) 
     
 
def getTCData(handle): 
    if not handle in CACHE : 
        CACHE[handle] = getTCDataNoCache(handle) 
    return CACHE[handle] 
     
 
def makeLinkForHandle(handle): 
    (cr, rating) = getTCData(handle) 
    if cr == 0: 
        return handle 
    classname = 'error' 
    for (x,y,s) in RATING_CLASSES: 
        if x <= rating and rating <= y : 
            classname = s 
    if classname == 'error': 
        print "Unable to find classname for rating=[%d]" % rating 
    return '<a href="http://www.topcoder.com/tc?module=MemberProfile&cr=%d" class="%s">%s</a>' % (cr,classname,handle) 
     
 
def makeLink(match): 
    print 'tag:',match.group(0) 
    handle = match.group(1) 
    return makeLinkForHandle(handle) 
     
 
if len(sys.argv) == 1: 
    print 'Interactive mode, type a handle name and it will return the link. Type an empty string to quit.' 
    s = "#" 
    while(s != ''): 
        s = sys.stdin.readline() 
        if(len(s)>0): 
            print makeLinkForHandle(s[:-1]) 
    exit(0) 
 
 
if len(sys.argv) != 3: 
    print 'Usual arguments are: "origin file" "destination file"' 
    exit(0) 
 
if os.path.exists(sys.argv[2]): 
    print '"%s" Already exists. Please delete it manually before callign the script.'%sys.argv[2] 
    exit(0) 
 
 
f1 = open(sys.argv[1],'r') 
f2 = open(sys.argv[2],'w') 
 
 
 
text = f1.read() 
text,cnt = REGEX_HTAG.subn(makeLink, text) 
print "%d tags processed."%cnt 
 
if re.search('\[/?h\]',text) != None: 
    print 'Note: Found [/?h] after replace, perhaps a tag is not formatted correctly...' 
 
f2.write(text) 
 
 

Read More

Member SRM 494 - Commentary and explanation for div1 250

Second match after my decision to start with the hard problem, then try the medium (when there are 33 minutes left) and then the easy (when there are only 11 minutes left).

Div I Hard: KnightsOut
A very interesting problem. I couldn't think of much, I noticed that cases in which the minimum side is less than 2, can be solved using dp or other simple methods. So you would only need to handle the cases in which both dimensions are greater than 3. It seems Petr had a similar idea, but it is far, far away from what I could do in 44 minutes.

Div I Medium: AlternatingLane
This also seemed like a good problem. I imagined plenty of things. Noticed a dp [100000][2][50] could work as long as I figured out a way to do each state in O(high[i]). I think there is a way to do it by accumulating the results for each [previous][0,1][n] for each n. and then you can use a subtraction to get the sum, and the summation formula to get the sum of differences between the previous value and the new one. But it needs work. Something I noticed is that when the lane is already alternating after picking the heights, you are not allowed to cut down trees, even if that would yield a higher beauty. It seems like such thing would make my dp idea more complicated.

When there were around 14 minutes left to the match, I was still far from thinking of a definite solution for the 500. I was paying attention to the summaries and it seemed like it was a good idea to reserve some more time to it. And it was unlikely I would think of the solution and code it in less than three minutes. So I switched to the easy.

Div I Easy: Painting
A cool problem that was actually coding-based instead of math-based like the previous 60 Div 1 easies were... A nice change. I managed to solve it but...

Blunder: I have made many mistakes while coding the solution for this problem, so even though I started coding it right away, I still needed 12 minutes to finish debugging it. Unfortunately, I made a mistake, once I passed all the example cases, it occurred to me to try doing a timeout test "just in case". But think about it, even if I found out that the solution is too slow, I would not have had enough time to fix it (there were only two minutes left). Also, for some reason I made a lot of mistakes when trying to generate a large case with python. Fortunately, I came back to my senses and decided to compile and submit with some few seconds left for the match. This blunder cost me at least 10 points, which would translate in ~30 positions.

The result was a not-good but not-bad position, I earned 2 rating points (but I lost a lot of points last match).

So, here comes my explanation for the easy problem. I plan and hope to get explanations for the other problems seeing how member SRMs don't have editorials, and the problems seemed fun, but it depends on how much time I can manage to have.

Explaining the Div I Easy: Painting
Problem statement

We want to maximize S, the size of a SxS brush. In maximization problems, it often pays to change the option from "Maximize S" to "Is it possible to do it with a value S?". If we use the latter question, we can actually just iterate from higher values of S and keep decreasing S until it is possible to use such value. For example, try a size 50 brush, if it is possible to do it, return 50, then try a size 49 brush, and so and so until a good size is found or until the brush size becomes 1 (in which case we can be certain that the result is 1, as it is always possible to do it).

Since we now want to know if it is possible to use a SxS brush to paint the painting, how about the following algorithm? For every brush position (i,j) , if there is no white cell in the painting in the SxS area starting at (i,j), then we can paint a SxS black square in that area. If it is possible to paint such a black square, there is no reason not to paint the square, because we are allowed to paint the same cell more than once. So, how about we begin with a completely white board and then iterate through all the (i,j) cells in the board, and if it is possible to paint a SxS in each of the cells, just paint it. If at the end the board is equal to the painting, then it is possible to do it with a SxS brush.

Note that such algorithm will require O(min(W,H)) iterations for S, O(W*H) (i,j) iterations for each cell , and inside those iterations, we need to try SxS squares to check if they contain white cells or not and then to paint them. So, we can estimate the complexity to be O( min(W,H) * W*H * W*H ) . With W,H <= 50, that may appear to be too high for the two seconds limit, but in reality, it is not (In fact, the following code needs 67 ms in the worst case, I think a good complexity analysis should show it is actually very fast and the O() notation is hiding something.)

Sample code:

   1 int isPossible( vector<string> & picture, int s) {
   2     int w = picture.size(), h = picture[0].size();
   3     
   4     // An initially-white board:
   5     vector<string> board( w, string(h, 'W') );
   6     
   7     for (int i=0; i<w-s+1; i++) 
   8      for (int j=0; j<h-s+1; j++) {
   9         //pick (i,j):
  10         bool can = true;
  11         
  12         // is it possible to draw a SxS black square at (i,j) ?
  13         for (int x=i; (x<i+s) && can; x++)
  14          for (int y=j; (y<j+s) && can; y++) {
  15              can = can && (picture[x][y] != 'W' );
  16          }
  17         if( can ) {
  18             //it is possible, paint it:
  19             for (int x=i; (x<i+s) && can; x++)
  20              for (int y=j; (y<j+s) && can; y++) {
  21                 board[x][y]='B';
  22              }
  23         }
  24      }
  25     // if the board and the picture are equal,
  26     // then it was possible to use a SxS brush:
  27     return (board == picture);
  28 }
  29 
  30 int largestBrush(vector <string> picture)
  31 {
  32     int w = picture.size(), h = picture[0].size();
  33 
  34     // try all possible values of s, until finding the
  35     // largest valid one:
  36     for (int s= std::min(w,h); s>1; s--) {
  37         if( isPossible(picture, s) ) {
  38             return s;
  39         }
  40     }
  41     return 1;
  42 
  43 }

During the match , I was too cautious and didn't trust the O( min(W,H) * W*H * W*H ) solution, I instead used binary search. Note that if it is possible to use a size SxS brush to paint the painting, then all brush sizes smaller than SxS will also make it possible (You can always make a SxS square by combining smaller squares). And the opposite is also true, if it is not possible to use a SxS brush, then larger brushes will also not be usable. This means that there would be a line dividing the possible brush sizes with the impossible ones, therefore, we can use binary search to find the maximum allowed size.

Read More

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.

Read More