dynamic programming reduction of brute force

Question

A emoticon consists of an arbitrary positive number of underscores between two semicolons. Hence, the shortest possible emoticon is ;_;. The strings ;__; and ;_____________; are also valid emoticons.

given a String containing only(;,_).The problem is to divide string into one or more emoticons and count how many division are possible. Each emoticon must be a subsequence of the message, and each character of the message must belong to exactly one emoticon. Note that the subsequences are not required to be contiguous. subsequence definition.

The approach I thought of is to write a recursive method as follows:

countDivision(string s){
 //base cases
 if(s.empty()) return 1;
 if(s.length()<=3){
   if(s.length()!=3) return 0;
   return s[0]==';' && s[1]=='_' && s[2]==';';
 }
  result=0;
//subproblems
  genrate all valid emocticon and remove it from s let it be w
  result+=countDivision(w);
  return result;
}

The solution above will easily timeout when n is large such as 100. What kind of approach should I use to convert this brute force solution to a dynamic programming solution?

Few examples

 1. ";_;;_____;" ans is 2
 2. ";;;___;;;" ans is 36

Example 1.

 ";_;;_____;" Returns: 2 
 There are two ways to divide this string into two emoticons. 
 One looks as follows:  ;_;|;_____; and the other looks like
 this(rembember we can pick subsequence it need not be contigous):  ;_ ;|; _____;

Could you maybe share one input and expected output so it is clearer? — Martin Gottweis
– Martin Gottweis, Commented Sep 16, 2016 at 7:54
if I understood... could you simply find and store any point like ";;" and than split the string in any possible way based on the previous computed points? — Daniele
– Daniele, Commented Sep 16, 2016 at 8:15
Does all character of the string need to be used in the division? — AnotherGeek
– AnotherGeek, Commented Sep 16, 2016 at 8:17
@Daniele the shortest possible emocticon is ;_; so ;; is not valid emocticon — Prashant Bhanarkar
– Prashant Bhanarkar, Commented Sep 16, 2016 at 8:41
This looks to be from this (long-finished) TopCoder contest: community.topcoder.com/… — j_random_hacker
– j_random_hacker, Commented Sep 16, 2016 at 17:11

j_random_hacker · Accepted Answer · 2016-09-16 17:12:36Z

I'll describe an O(n^4)-time and -space dynamic programming solution (that can easily be improved to use just O(n^3) space) that should work for up to n=100 or so.

Call a subsequence "fresh" if consists of a single ;.

Call a subsequence "finished" if it corresponds to an emoticon.

Call a subsequence "partial" if it has nonzero length and is a proper prefix of an emoticon. (So for example, ;, ;_, and ;___ are all partial subsequences, while the empty string, _, ;; and ;___;; are not.)

Finally, call a subsequence "admissible" if it is fresh, finished or partial.

Let f(i, j, k, m) be the number of ways of partitioning the first i characters of the string into exactly j+k+m admissible subsequences, of which exactly j are fresh, k are partial and m are finished. Notice that any prefix of a valid partition into emoticons determines i, j, k and m uniquely -- this means that no prefix of a valid partition will be counted by more than one tuple (i, j, k, m), so if we can guarantee that, for each tuple (i, j, k, m), the partition prefixes within that tuple are all counted once and only once, then we can add together the counts for tuples to get a valid total. Specifically, the answer to the question will then be the sum over all 1 <= j <= n of f(n, 0, j, 0).

If s[i] = "_":
  f(i, j, k, m) =
    (j+1) * f(i-1, j+1, k, m-1)    // Convert any of the j+1 fresh subsequences to partial
    + m * f(i-1, j, k, m)          // Add _ to any of the m partial subsequences

Else if s[i] = ";":
  f(i, j, k, m) =
    f(i-1, j-1, k, m)              // Start a fresh subsequence
    + (m+1) * f(i-1, j, k-1, m+1)  // Finish any of the m+1 partial subsequences

We also need the base cases

f(0, 0, 0, 0) = 1
f(0, _, _, _) = 0
f(i, j, k, m) = 0 if any of i, j, k or m are negative

My own C++ implementation gives the correct answer of 36 for ;;;___;;; in a few milliseconds, and e.g. for ;;;___;;;_;_; it gives an answer of 540 (also in a few milliseconds). For a string consisting of 66 ;s followed by 66 _s followed by 66 ;s, it takes just under 2s and reports an answer of 0 (probably due to overflow of the long long).

גלעד ברקן · Accepted Answer · 2016-09-18 03:30:41Z

1

Here's a fairly straightforward memoized recursion that returns an answer immediately for a string of 66 ;s followed by 66 _s followed by 66 ;s. The function has three parameters: i = index in the string, j = number of accumulating emoticons with only a left semi-colon, and k = number of accumulating emoticons with a left semi-colon and one or more underscores.

An array is also constructed for how many underscores and semi-colons are available to the right of each index, to help decide on the next possibilities.

Complexity is O(n^3) and the problem constrains the search space, where j is at most n/2 and k at most n/4.

Commented JavaScript code:

var s = ';_;;__;_;;';

// record the number of semi-colons and 
// underscores to the right of each index
var cs = new Array(s.length);
cs.push(0);

var us = new Array(s.length);
us.push(0);

for (var i=s.length-1; i>=0; i--){
  if (s[i] == ';'){
    cs[i] = cs[i+1] + 1;
    us[i] = us[i+1];
    
  } else {
    us[i] = us[i+1] + 1;
    cs[i] = cs[i+1];
  }
}

// memoize
var h = {};

function f(i,j,k){
  // memoization
  var key = [i,j,k].join(',');

  if (h[key] !== undefined){
    return h[key];
  }

  // base case
  if (i == s.length){
    return 1;
  }

  var a = 0,
      b = 0;
  
  if (s[i] == ';'){
    // if there are still enough colons to start an emoticon
    if (cs[i] > j + k){  
      // start a new emoticon
      a = f(i+1,j+1,k);
    }
      
    // close any of k partial emoticons
    if (k > 0){
      b = k * f(i+1,j,k-1);
    }
  } 
  
  if (s[i] == '_'){
    // if there are still extra underscores
    if (j < us[i] && k > 0){
      // apply them to partial emoticons
      a = k * f(i+1,j,k);
    }
    
    // convert started emoticons to partial
    if (j > 0){
      b = j * f(i+1,j-1,k+1);
    }
  }
  
  return h[key] = a + b;
}

console.log(f(0,0,0)); // 52

edited Sep 18, 2016 at 3:30

answered Sep 17, 2016 at 3:28

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

2 Comments

j_random_hacker Over a year ago

IIUC, you're able to shed a factor of n from the running time and space complexities by noticing that the 3 parameters i, j and k uniquely determine the number of completed emoticons in a partition (the parameter I called m in my approach), so m doesn't need to be recorded in the state explicitly. Very nice! A minor point: Your f() seem to be computing answers for the suffix starting at i, so e.g. j would be best described as "j = number of accumulating emoticons with only a right semi-colon" (and similarly for k).

גלעד ברקן Over a year ago

@j_random_hacker thank you for your comment! Regarding j and k, I think if we were to express j and k as arrays holding actual emoticons, we could see that when j is incremented, it corresponds with a new call with ";" added to the js; when k is incremented, it would correspond with k calls, each adding an underscore to one of the ks; and when k is decremented, it would mean k calls, each one with another k removed from that array. (I left out the conversion from j to k but I imagine you get the idea.)

Collectives™ on Stack Overflow

dynamic programming reduction of brute force

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related