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
Constraints
Testcase:
Possible approaches
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?
Auto comment: topic has been updated by gagannagpal68 (previous revision, new revision, compare).
1411D - Grime Zoo Same problem
Sorry, I misunderstood condition, my hint is completely innapropriate for this problem(
What if we blend greedy approaches, and replace first $$$p$$$ ? with 1 and last $$$q$$$ ? with 0, then oterate once and find $$$p$$$ and $$$q=cnt_? - p$$$