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
@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
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!
I tried implementing your logic but it didn’t worked. Can you plz see into the code to figure out where I’m going wrong. Code