Getting wrong answer,

#1

I am solving this question from codeforces…
https://codeforces.com/problemset/problem/1354/B
I have tried to come up with dp solution using top-down + memoization…
This is my solution…


But it is showing wrong answer for the first test case…
I am not able to find… why it is showing wrong answer…
Please see this.

#2

hello @ashishnnnnn

whats ur approach?

#3

My approach is…
First for given index i will see if before we have selected any character if yes… then we have no option to reject it…because we want substring… so we will select it…
If before we have not selected any character… then we can select this character or… we can reject this one…
That what i am doing.
I am also checking if all three “zero”,“one” and “two” are selected then… we return zero…
and if we cover all the string and still one of “zero”,“one” and “two” is zero then we return 10000000…

#4

here u went wrong.
when u have already already selected character then u can also end it somewhere right?
which u r not cosidering

#5

When we have already selected any character… then we will end only when all three “zero”,“one” and “two” has been selected atleast once.
Or… we will search till end…so that all three… “zero”,“one” and “two” can be selected once…
If that is not possible…we return 10000000.

#6

yeah, but instead of continuing previous series, u can start new from ur current state right?
it may happen that series starting from current will give minimum.

at each i u have two options either u continue last series or u start a new series from here

#7

But for that… How will we code… Because the later selection is independent of previous one… then how could we do it recursive…

#8

do this ->
for(int i=0;i<n;i++){
solve(i) --> // where solve(i) will give minimum length string with all 3 character present and starting at index.
}
pick minimum and print

#9

Won’t it give tle…Because we iterarting over each index and for each index we are doing calculation…

#10

yeah as per constraint it will .

#11

either u can directly do it using two pointer approach .

or
u can do it using prefix array(dp bol lo ) + binary search (slowe.r than two pointer)

#12

Could you give some idea about the second one??

#13

just maintain prefix count of each character.
i.e

dp[i][1]= count of 1 when [0…i] array is considered
dp[i][2]= count of 2 when [0…i] array is considered
dp[i][3]= count of 3 when [0…i] array is considered

now use binary search on length of string to find the minimum length .

#14

Sorry… But after maintaining the prefix array which store number of ‘0’,‘1’,‘2’… I am not getting how will we use binary search on this…

#15

let say u found an L length string which contain all three character .
now update ur answer with L.
and then search for smaller string length -> [0…L-1]
let say u searched for L/2 length string .
we have two case
we get L/2 length string then update ur answer and search in range [0,L/2-1]
we didnt get L/2 length string then search in range [L/2+1 ,L-1]
it is just binary search on length.

#16

I got some of this idea…
trying to implemet this…:slight_smile: