Sunday, January 27, 2008

Teaser!

Another interesting pick from Topcoder archive.

You are given 4 numbers: CountA, CountB, MaxA, MaxB. and you have to make a Beautiful string out of it. Hold on a minute to find out what is actually a Beautiful string.
CountA signifies the number of A's at your disposal,
CountB signifies the number of B's at your disposal,
MaxA signifies the maximum number of consecutive A's in any substring,
MaxB signifies the maximum number of consecutive B's in any substring,

A beautiful string is a string you can form using CountA number of A's and CountB number of B's satisfying the MaxA and MaxB constraints.

I am trying to find the link with test cases and better explanation on topcoder site, will update the post with the link as soon as i get hold of it.

Meanwhile, a sample input-output sequence would be
input 3 4 1 2 outputs 7
bababab

input 20 21 1 0 ouputs 1
a

Its a simple solution and we(srujan and myself) had cracked it pretty easily. We wanted to code it to try difficult and general cases from the site. In the process we found a code snippet that solved the problem. It was very elegantly written and more importantly taught us a new operator in GCC( works only GCC compiler and not in .NET)

a < ?= b, based on our interpretation translates to "if a < b then update value of a to b"

Any comments on the new findings are welcome..

No comments: