Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

shakil_AUST's blog

DP Problem Help ( Ordered Flips , Light Oj — 1351 )

By shakil_AUST, 11 years ago, In English

Can anyone please tell me the process how to solve this problem . Thanx in advance :)

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

»
11 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Solved the problem after seeing this post.

lets take dp[flip_allowed][flipped][i][j][k]=minimum number of flip needed to match x[i....j] with Y[k ..... k+j-i], 'filp_allowed' and 'flipped' are boolean values that denotes whether we are allowed to flip the current segment X[i....j] and whether the portion x[i....j] is flipped respectively. now to match x[....] to y[...], we can either flip the entire segment x[....] , or we will at least leave one character from any end of x[i....j] if that matches Y[k ........ k+j-i].

So the state transitions will look like this

if(flip_allowed) dp[filp_allowed][flipped][i][j][k] = 1 + dp[0][!flipped][i][j][k];
if(!flipped) 
{
   if(X[i]==Y[k]) dp[flip_allowed][flipped][i][j][k]=dp[1][0][i+1][j][k+1];
   if(X[j]==Y[k+j-i]) dp[flop_allowed][flipped][i][j][k]=dp[1][0][i][j-1][k];
}

else if(flipped)
{
   if(X[j]==Y[k]) dp[flip_allowed][flipped][i][j][k]=dp[1][1][i][j-1][k+1];
   if(X[i]==Y[k+j-i]) dp[flip_allowed][flipped][i][j][k]=dp[1][1][i+1][j][k];
}

Hope that helps.

→ Reply