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 ↵
↵
<spoiler summary="Constraints">↵
|s|, x, y <= 1e5↵
</spoiler>↵
↵
↵
<spoiler summary="Testcase:">↵
Input:↵
S = 101? , x = 2, y = 2↵
↵
Ans = 6↵
↵
Why ?↵
↵
We can make these two strings:↵
↵
1. 1010 and subsequences for 01:1, 10:3 and answer is 1*2 + 3*2 = 8↵
↵
2. 1011 and subsequences for 01:2, 10:1 and answer is 2*2 + 1*2 = 6↵
↵
So , ans is min(8,6) = 6↵
</spoiler>↵
↵
<spoiler summary="Possible approaches">↵
1. 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. ↵
↵
2. 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. ↵
↵
3. Greedy which I think is wrong, for every '?' encountered find whether 0 or 1 gives the right answer. This is even not passing. ↵
</spoiler>↵
↵
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?↵
↵
