SRM 671, D2, 250-Pointer (BearCries)

James S. Plank

Fri Oct 16 16:11:29 EDT 2015

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh MD5 hash = f7f312742b72d92061a634527a2a0b48
answers.txt MD5 hash = c78b839f65424f287f6e3b9716f3ed32
Problem Given in Topcoder: October, 2015
Competitors who opened the problem: 551
Competitors who submitted a solution: 285
Number of correct solutions: 254
Accuracy (percentage correct vs those who opened): 46.1%
Average Correct Time: 25 minutes, 25 seconds.

In Case Topcoder's Servers are Down

Here is a summary of the problem:

There is a bear named "Limak".
He likes to use emoticons when he's on social media.
This problem concerns the "crying" emoticon, which is composed of two semi-colons with an arbitrary number of positive underscore characters in between them.
The following are examples of crying emoticons:
;_; ;__; ;_______________;
A subsequence of a string S is a string that you create by deleting characters of S.
You are given a string message, which may be partitioned into subsequences, each of which is a crying emoticon.
Return the number of ways in which you can partition message into crying emoticon subsequences.
Return your answer modulo 1,000,000,007.
The maximum size of message is 200 characters.

Examples

0: ";_;;_____;" - Answer = 2.  If you label the four semicolons a, b, c and d, then the
                               two partitionings are a_b c_____d, and a_c b_____d.

1. ";;;___;;;" - Answer = 36.  Label the semicolons a, b, c, d, e, f, and then underscores x, y, z.
                           
                 axd bye czf - axd bze cyf - ayd bxe czf  - ayd bze cxf - azd bxe cyf  - azd bye cxf
                 axd byf cze - axd bzf cye - ayd bxf cze  - ayd bzf cxe - azd bxf cye  - azd byf cxe
                 axe byd czf - axe bzd cyf - aye bxd czf  - aye bzd cxf - aze bxd cyf  - aze byd cxf
                 axe byf czd - axe bzf cyd - aye bxf czd  - aye bzf cxd - aze bxf cyd  - aze byf cxd
                 axf byd cze - axf bzd cye - ayf bxd cze  - ayf bzd cxe - azf bxd cye  - azf byd cxe
                 axf bye czd - axf bze cyd - ayf bxe czd  - ayf bze cxd - azf bxe cyd  - azf bye cxd

2. "_;__;"                                   - Answer = 0 -- Impossible to partition
3. ";_____________________________________;" - Answer = 1
4. ";__;____;"                               - Answer = 0
5. ";_;;__;_;;"                              - Answer = 52

Testing yourself

Standard tests.sh and answers.txt.

Hints

This looks, feels and smells like a Dynamic Programming problem. The hard part here is spotting the recursion. My first thought was to pick a ";_*;" substring and then make a recursive call on the remaining part of the string. I couldn't get that to work.

Instead, try the following procedure:

long long C(int index, int emoticons_with_underscore, int emoticons_without_underscore);

This procedure will return the count of emoticons given that you have already looked at the first index characters, and you have:

Started emoticons_with_underscore emoticons, and they already have at least one underscore.
Started emoticons_without_underscore emoticons, and they have no underscores.

You'll start with C(0,0,0).

Inside C, you'll break your code into three cases:

index is message.size(). In that case, if you have any started emoticons, your answer is zero. If you have no started emoticons, your answer is one. This is the base case.
message[index] is an underscore. If there are no started emoticons, then your answer is zero. However, if you have any started emoticons, then you may assign this underscore to any of them. You'll split this case in two -- first you assign the underscore to a started emoticon that already has underscores. That will result in one recursive call. Second you assign the underscore to a started emoticon that doesn't have underscores. That will result in a second recursive call. You return their sum.
message[index] is an semi-colon. This can be used to start an emoticon (without an underscore), so make that recursive call. Then, if there are emoticons with underscores, this can end one of them. Make that recursive call.

You have to memoize. I did that by converting the three parameters to a string and using a map, although you could use a vector of vectors of vectors of long long's, and simply resize the inner ones on demand. I'm not sure which would be faster.

Let's go through the calls when the string is ";;;___;;;" (Example 1):

C(0,0,0)   = C(1,0,1)                       =   36
C(1,0,1)   = C(2,0,2)                       =   36
C(2,0,2)   = C(3,0,3)                       =   36
C(3,0,3)   = 3*C(4,1,2)                     =   36
C(4,1,2)   = 1*C(5,1,2) + 2*C(5,2,1)        =   12
C(5,1,2)   = 1*C(6,1,2) + 2*C(6,2,1)        =    0
C(5,2,1)   = 2*C(6,2,1) + 1*C(6,3,0)        =    6
C(6,1,2)   = C(7,1,3) + 1*C(7,0,2)          =    0
C(6,2,1)   = C(7,2,2) + 2*C(7,1,1)          =    0
C(6,3,0)   = C(7,3,1) + 3*C(7,2,0)          =    6
C(7,0,2)   = C(8,0,3)                       =    0
C(7,1,1)   = C(8,1,2) + 1*C(8,0,1)          =    0
C(7,1,3)   = C(8,1,4) + 1*C(8,0,3)          =    0
C(7,2,0)   = C(8,2,1) + 2*C(8,1,0)          =    2
C(7,2,2)   = C(8,2,3) + 2*C(8,1,2)          =    0
C(7,3,1)   = C(8,3,2) + 3*C(8,2,1)          =    0
C(8,0,1)   = C(9,0,2)                       =    0
C(8,0,3)   = C(9,0,4)                       =    0
C(8,1,0)   = C(9,1,1) + 1*C(9,0,0)          =    1
C(8,1,2)   = C(9,1,3) + 1*C(9,0,2)          =    0
C(8,1,4)   = C(9,1,5) + 1*C(9,0,4)          =    0
C(8,2,1)   = C(9,2,2) + 2*C(9,1,1)          =    0
C(8,2,3)   = C(9,2,4) + 2*C(9,1,3)          =    0
C(8,3,2)   = C(9,3,3) + 3*C(9,2,2)          =    0
C(9,0,0)   = Base Case.                     =    1
C(9,0,2)   = Base Case.                     =    0
C(9,0,4)   = Base Case.                     =    0
C(9,1,1)   = Base Case.                     =    0
C(9,1,3)   = Base Case.                     =    0
C(9,1,5)   = Base Case.                     =    0
C(9,2,2)   = Base Case.                     =    0
C(9,2,4)   = Base Case.                     =    0
C(9,3,3)   = Base Case.                     =    0

This is fast enough for topcoder, but you could speed it up a bit, by recognizing impossible states, such as C(7,1,3), and returning instantly. That will save on a ton of recursive calls.