Hi,

I have been trying to find the recursive solution for SPOJ BORW(Black or White) problem , but none of the recursive logic seems to work.

I understood that the recursive equation will be based on the logic that any ball can be either painted black or white or none , but couldn’t turn it into logical terms .

Problem link link text

Since recurisve solution has been provided now , I was trying to convert this solution to dp solution using 3D dp array of which one of the state whould be array index. For the next two states I am little confused bcoz if I take array values as the other two indexes , then the dp size would be too large . Any suggestion what should be the other two states of dp ??

Any hints will be appreciated. Thanks

I have tried to implement the solution here : Link.

In case of any doubt feel free to ask!

1 Like

Infact I too am trying to figure out a dp solution to this since yesterday (yeah I am pretty bad at dp xD).

Have you figured out one yet? If yes please share it!

U can easily do this using 2d Dp,dp[x][y] denotes the maximum number of painted if the xth ,and yth index are the last in increasing and decreasing subsequences.

dp[x][y]=max(dp[i][y]+1)–>(for i<x and arr[i]<arr[x])

dp[x][y]=max(dp[x][i]+1)—>(for i<y and arr[i]>arr[y])

Can you explain a bit more on this and maybe provide pseudocode. I can’t get how this works!

@vivek_1998299 , thanks for your response,

i too didn’t get how this algorithm is working , although i tried to created one solution with your algo , but it is not working . Please have a look and suggest me what changes are required ??

link text

@vivek_1998299 , thanks for your response,

i too didn’t get how this algorithm is working , although i tried to created one solution with your algo , but it is not working . Please have a look and suggest me what changes are required ??

link text