You are not logged in. Please login at www.codechef.com to post your questions!

×

AHWORK - Editorial

0
1

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

asked 19 May '16, 12:49

prateekg603's gravatar image

5★prateekg603
20421223
accept rate: 0%

edited 29 May '16, 11:41

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! :-/

(28 May '16, 22:40) akashdeep19962★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,477
×2,085
×348
×126

question asked: 19 May '16, 12:49

question was seen: 2,050 times

last updated: 29 May '16, 11:41