Solution of Facebook Hacker Cup 2012 problem – Squished statusSome engineers got tired of dealing with all the different ways of encoding status messages, so they decided to invent their own. In their new scheme, an encoded status message consists of a sequence of integers representing the characters in the message, separated by spaces. Each integer is between 1 and M, inclusive. The integers do not have leading zeroes. Unfortunately they decided to compress the encoded status messages by removing all the spaces! Your task is to figure out how many different encoded status messages a given compressed status message could have originally been. Because this number can be very large, you should return the answer modulo 4207849484 (0xfaceb00c in hex). For example, if the compressed status message is “12″ it might have originally been “1 2″, or it might have originally been “12″. The compressed status messages are between 1 and 1000 characters long, inclusive. Due to database corruption, a compressed status may contain sequences of digits that could not result from removing the spaces in an encoded status message. Input The input begins with a single integer, N, the number of compressed status messages you must analyze. This will be followed by N compressed status messages, each consisting of an integer M, the highest character code for that database, then the compressed status message, which will be a string of digits each in the range ’0′ to ’9′, inclusive. All tokens in the input will be separated by some whitespace. Output For each of the test cases numbered in order from 1 to N, output “Case #i: ” followed by a single integer containing the number of different encoded status messages that could be represented by the corresponding compressed sequence modulo 4207849484. If none are possible, output a 0. Constraints 5 <= N <= 25 Example input 5 Example output Case #1: 2 Preliminaries Lets assume that there is a routine which splits input string into a sequence of the smallest valid numbers. Zero and numbers greater than max value M are invalid. Consider following examples: Input: M=2, S=101 Input: M=11, S=101 Input: M=124, S=18143 Now lets concentrate on solving the following problem. Given a sequence of numbers - L, count all possible sequences that could be constructed from original sequence by combining consecutive numbers, such that obtained number is less than maximum value M. Example, given M = 181 and L={1, 4, 3} we can construct 4 sequences:
Naïve approach An obvious solution is to perform exhaustive search and construct all such sequences. The algorithm is as simple as:
No surprise this approach will only work for small sequences ~ 15-20 numbers. But we can do better, by figuring out recurrent formula for possible number of valid sequences. Recurrent formula Let’s imagine that we calculated the number of different sequences S(L) for input of n numbers: S({x_{1}, x_{2}, …, x_{n}} ) = S_{n} What will happen if we add another number x_{n+1}? We might notice that: S({x_{1}, x_{2}, …, x_{n}, x_{n+1} } ) = S({x_{1}, x_{2}, …, x_{n}})+ S({x_{1}, x_{2}, …, (x_{n} x_{n+1})}) The structure of solutions is shown on this illustration: Links Code |