Varun_Shah's blog

By Varun_Shah, history, 6 years ago, In English

I found the following problem very interesting on a recent Hackerrank contest, I don't get the intuition for what the editorialist states.It would indeed be very helpful if someone helps me understand it.

Link to the problem

What I got is as follows:

(Note:dp[x...y] means dp[x] + dp[x+1] ... + dp[y])

for number of ways of reaching a solution from either string a or string b, the recurrence may go as follows

dp[i][j][k][0] = summation of dp[i-1][j-1][k][0...2];

dp[i][j][k][1] = (if a[i] equals c[k] then summation of dp[i-1][j][k-1][0...2] else 0) + dp[i-1][j][k][0...2];

dp[i][j][k][2] = (if b[j] equals c[k] then summation of dp[i][j-1][k-1][0...2] else 0) + dp[i][j-1][k][0...2];

Here, dp[i][j][k][x] means number of ways of forming c[0...k] from a[0...i] or from b[0...j] or both.

where x = 0 if we neglect last character of both a and b

x = 1 if we consider last character of a and not b

x = 2 if we consider last character of b and not a

Please correct me if I am wrong.Thanks in advance for the help.

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Varun_Shah (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Varun_Shah (previous revision, new revision, compare).

»
6 years ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

I didn't read the editorial, but I thought of explaining what I did (it seems to be simpler than editorial). Maybe someone will find it useful.

We will use two 2D arrays dp[0] and dp[1]

dp[0] is old data, and dp[1] is the data of current character, which will be updated.

We start from the first character of string c, and traverse to the end. Counting is 1-indexed. a[0] and b[0] are empty.

In the kth iteration,
dp[0][i][j] = number of ways of having character a[i] as last character chosen in a, character b[j] as last character chosen in b and arranged to form c[1..(k-1)].
Clearly, the base case is dp[0][0][0] = 1 (1 way to satisfy empty string c using nothing from a and nothing from b).

In each iteration, we have 2 cases.

Case 1: The current character will be taken care of by a character chosen from string a.

We go through all characters in string a, and for those characters where a[y] = c[k], where k is the iteration number, we update dp[1][y][j] for all j like so:

for (int x = 0; x < y; x++)
{
    dp[1][y][j] += dp[0][x][j];
}

I wrote that for loop to just to represent what I meant. A running sum must be used instead to get rid of this O(|a|) extra time.

The reason for us doing this is — We have some solutions for c[1..(k-1)] with x as last char in a, j as last char in b. We are using yth character from a in this iteration, so we add all possible solutions that can be extended to this iteration.

Case 2: The current character will be taken care of by a character chosen from string b.

We do the same thing as Case 1 — fixing position in string a instead of b.


At the end of each iteration, we need to copy new values into old.

After all iterations, the ans will be sum of dp[0][i][j] for all 1 <= i <= |a|, 1 <= j <= |b|

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So you mean to say that for ith character match of c, first we need to fill dp[0] which stores answer of matching only i characters then update dp[1] based on dp[0]...do this for c.length() iterations...Correct me if I am wrong.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No. I meant that if we are processing the ith character of string c, then dp[0] will have the solution for the substring c[1..(i-1)]. We will use this information to find the answer for the substring c[1..i]. We store this in dp[1] and then copy it back to dp[0]. (We use dp[1] as a temporary array, as we need values in dp[0] till the end of the current iteration).

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To update dp1:

    For every k from 1 to c.size(), for all possible lengths of a & b, we find if(a[i] == c[k]) and then in the same way if(b[j] == c[k]). If condition holds true, we again iterate over entire respective string's array...

    Won't that exceed the TL as it becomes O(n^4)?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We do |c| iterations.

      In each iteration:

      In case 1, we will iterate over all possible positions for string b, and then for each of them, we will iterate over all possible positions for string a — O(|b|*|a|).

      In case 2, we will iterate over all possible positions for string a, and then for each of them, we will iterate over all possible positions for string b — O(|a|*|b|).

      Copying dp[1] to dp[0] — O(|a|*|b|).

      Overall complexity — O(|c|*|a|*|b|).

      Here's my submission for ref. — https://paste.ubuntu.com/p/k66BGsM7rQ/

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Okay got it...except for how does it take care for atleast 1 character from both string?

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          "After all iterations, the ans will be sum of dp[0][i][j] for all 1 <= i <= |a|, 1 <= j <= |b|".

          The conditions i >= 1 and j >= 1 take care of atleast 1 character from both strings. (i/j = 0 implies no character from a/b)