AHWORK - Editorial

PROBLEM LINK

Practice

Contest

Author: Amit Pandey

Tester & Editorialist: Prateek Gupta

DIFFICULTY:

Medium Hard

PREREQUISITES:

Dynamic Programming, Strings

PROBLEM:

Given N strings each consisting of at-most 2 characters either of a or b, delete the minimum number of strings such that rest of them can be concatenated to form a palindrome.

EXPLANATION

Solution for Subtask 1:

Since, the constraints for N are as small as 16, you can use bit masking to generate all possible combinations and find the one combination which after concatenation, needs minimum deletions to form a palindromic string. For each of the N strings, you have a choice either to take it or to not take it in the final formed string. Hence, each string can be assigned a bit 1 or 0 depending on whether it is chosen or not. Having said that, there will be 2^{N} such possible combinations. Let’s have a look at the pseudo code to gather a little more detail of what we are trying to accomplish.

ans = INFINITY

for ( mask = 0 to 2^n - 1 ) {

      tmp = ""
      deletions = 0

      for ( i = 0 to n - 1 ) {
             if ( bit i is set in mask ) tmp.append(s[j])
             else deletions += 1
      }

      if ( tmp is palindrome ) ans = min(ans, deletions)
}

print(deletions)

The time complexity of the above approach will be {O}(N*2^{N})

Solution for subtask 2:

The best solution to the problem involves use of Dynamic Programming.
No matter, how much you are familiar with it! It doesn’t fail to surprise you, ain’t it!?

We can define the DP state as F(i,\ j,\ cnt1,\ cnt2) denoting the minimum number of strings to be removed in range(i,\ j) so that rest of the strings in the same range can be concatenated to form a palindrome, when cnt1 characters of i^{th} string and cnt2 characters of j^{th} string from the back, have matched already. Hence, value of the state F(0,\ N - 1,\ 0,\ 0) will give us the final result. At each state, there are a number of possibilities to consider. When you have already decided to take the i^{th} string in your final answer, you have no choice but to somehow match it from the j^{th} string where i\ <=\ j.

  • Considering the base cases.
  • F(i,\ j,\ cnt1,\ cnt2)\ =\ 0,\ \forall\ i\ >\ j,\ cnt1\ =\ 0\ and\ cnt2\ =\ 0
    F(i,\ j,\ cnt1,\ cnt2)\ =\ INF,\ \forall\ i\ >\ j,\ cnt1\ !=\ 0\ or\ cnt2\ !=\ 0

    Let us have a look at the pseudo code for case i equals j.

if ( i == j ) {
    sz = s[i].size()
    idx1 = cnt1, idx2 = sz - cnt2 - 1
    if ( idx1 > idx2 ) return INF
    ans = INF
    if ( cnt1 == 0 and cnt2 == 0 ) ans = 1 //you can always skip this ith string since you have not yet considered taking it.

    while ( idx1 < idx2 ) {
         if ( s[i][idx1] != s[i][idx2] ) return min(ans, INF)
         idx1++, idx2--
     }   
     return 0
}
  • Considering the middle cases
  • Let us look at the pseudo code below to understand better.

        ans = INF
    
        //ignore the string at index i, since it's no characters have been matched yet
    	if ( cnt1 == 0 ) ans = min(ans, 1 + f(i + 1, j, 0, cnt2))
    
        //ignore the string at index j, since it's no characters have been matched yet
    	if ( cnt2 == 0 ) ans = min(ans, 1 + f(i, j - 1, cnt1, 0))
    	
    	sz1 = s[i].size()
    	sz2 = s[j].size()
    
        //try to match string i with string j from back
    	if ( s[i][cnt1] == s[j][sz2-cnt2-1] ) {
    
               //string i and string j not yet traversed fully.
    		if ( cnt1 + 1 < sz1 && cnt2 + 1 < sz2 ) ans = min(ans, f(i, j, cnt1 + 1, cnt2 + 1))
    
                //string i not yet traversed fully, but j traversed.
    		else if ( cnt1 + 1 < sz1 ) ans = min(ans, f(i, j - 1, cnt1 + 1, 0))
    
                //string i traversed fully, but j not yet traversed completely.
    		else if ( cnt2 + 1 < sz2 ) ans = min(ans, f(i + 1, j, 0, cnt2 + 1))
    
                //both string i and string j traversed completely.
    		else ans = min(ans, f(i + 1, j - 1, 0, 0))
        }
    
        return ans
    

    For details on the implementation of any subtasks, have a look at the tester’s solutions. If you wish to read more about Dynamic Programming, you might like to go through this blog post.

    COMPLEXITY

    Overall time and space complexity for the solution remains \mathcal{O}(N^{2})

    SOLUTIONS

    Tester’s solution to Subtask 1
    Tester’s solution to Subtask 2

    I made the exact same state of dp in my code along with all the cases taken care of… Don’t know why it got WA! :-/