Problem statement: You are a given a string s , int x and int y; S consists of three characters '0', '1', and '?' You can replace '?' with either '0' or '1'. You need to minimize the following equation:
Equation is a*x + b*y.
Here a is the number of "01" subsequences and b is number of "10" subsequences after the replacement of all '?'
Constraints
Testcase:Input: S = 101? , x = 2, y = 2
Ans = 6
Why ?
We can make these two strings:
1010 and subsequences for 01:1, 10:3 and answer is 1*2 + 3*2 = 8
1011 and subsequences for 01:2, 10:1 and answer is 2*2 + 1*2 = 6
So , ans is min(8,6) = 6
Possible approaches There is n^2 DP approach which would be to keep [idx] [cnt_zeros_so_far] and we can assign 0 or 1 for every '?'. I can explain this but should be easier for cf audience.
Greedy which turned out to be wrong, assign all '?' with 0 and find ans0. Assign all '?' with 1 and find ans1 . Print min(ans1, ans0). I don't have counter-case but I can write reasoning of why this is not optimal.
Greedy which I think is wrong, for every '?' encountered find whether 0 or 1 gives the right answer. This is even not passing.
I was thinking in direction of DP and making it run in nlogn and some sort of convex hull emerges in my head but I don't have enough practice to make it work. Any idea folks?
