A tough Algorithmic question?

[13bSLyTq]

Hey,

Long time no posting, but regardless I was trying to do some algorithmic programming and I got stuck on this question: http://www.olympiad.org.uk/papers/2015/bio/bio15-exam.pdf (Question 1, Page 2: "Block Palindromes")

Does anyone have a idea on how to tackle this code? Perhaps the logic behind it?

[ne555]

int count_block_palindrome( string ){
	count = 1; //the whole string as one block
	n = lenght(string);
	for K=1:n/2
		if s(1:K) == s(n-K: n) //searching a substring that's the same at beginning and end
			count += count_block_palindrome( s(K+1:n-K-1) ); //recurse on the rest of the string
	return count;
}

Edit: wasn't considering the whole string as one block.

[Duthomhas]

It's actually easier than you think. :O)

[edit]
Er, I made an error in my assessment...
I'll take a look at it again later
(sorry)
[/edit]


The paper only gave you very simple examples, but here's one that makes you think a little more.

    CBBXBBC

For simplicity each letter in the example represents a entire distinct grouping -- not just a single letter. If all we have is X (which may be "HELLO", for example) then it is not a 'block palindrome'.


break down

Our first step is to break that down into its individual pieces:

    C B B X B B C

(Again, that might actually be "HI BYE BYE HELLO BYE BYE HI". Obviously, I'm not limiting it to ten letters -- that is a limitation on input, not the algorithm.)

Since we have been able to break it down into more than one grouping then we know it is definitely a 'block palindrome'.


the question

Now, pay attention to what is being asked:

[How many] different ways the input can be grouped...

A particularly important fact here is that you cannot change the palindrome-ness of the thing at this point. We are only interested in groupings.


groupings

Adjacent groupings can be paired (or concatenated) into larger groupings. This is our clue.
If you represent each potential pairing as (paired, not paired) you reduce it to a simple binary sequence:

    C B B X    000
    C B B+X    001
    C B+B X    010
    C B+B+X    011
    C+B B X    100
    C+B B+X    101
    C+B+B X    110
    C+B+B+X    111

1. Notice that the left and right sides are the same, so we can write B+X instead of B+X+B here.

2. Notice also that the all-bits-set sequence is specifically excluded from the block palindrome's list of correct groupings. So the last one must be excluded.


putting it together

Hopefully, you should now be able to both count (requires only some math) and produce (requires a loop) every possible grouping.

Part c requires a little bit of thinking as well...
Hope this helps.

[Duthomhas]

Okay, here again. I knew I should have used the simple, brute-force recursive solution... but I'm occasionally an idiot. ne555's solution is the most direct way to answer it -- it just has a couple of important fence-post errors.

My solution made a mistake by bottoming out of the recursion after one step, then assuming as "fact" that "you cannot change the palindrome-ness of the thing at this point." Clearly, you can; hence my goof.

The problem with this kind of thing is that it is a "factorial" kind of problem, recomputing sub-solutions repeatedly. If you just want the brute-force, recursive solution, it is

unsigned count_blocks( const string& s, unsigned left, unsigned right )
{
  unsigned count = 0;
  for (unsigned n = 1; n <= (right-left)/2; n++)
  {
    if (s.substr( left, n ) == s.substr( right-n, n ))
      count = count + 1 + count_blocks( s, left + n, right - n );
  }
  return count;
}

unsigned count_blocks( const string& s )
{
  return count_blocks( s, 0, s.size() );
}

Very simple, no?

(I still have a very sneaky suspicion that there's a better, more elegant way to do this.... I just don't have time to play with it.)

[ne555]

> it is a "factorial" kind of problem, recomputing sub-solutions repeatedly
You may use memorization, store in an array the values when you first compute them, and recall them when you need them later.
You may use as key the right-left distance.

if( memory[right-left] not_eq EMPTY )
   return memory[right-left];

I think that the order then becomes O(n^2)

[Duthomhas]

/s/memorization/memoization/