How to solve this problem in less than O(n^2) time?
Разница между en1 и en2, 12 символ(ов) изменены
**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 ↵

<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?↵

 

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский gagannagpal68 2024-03-16 16:09:10 12
en1 Английский gagannagpal68 2024-03-16 16:07:54 1571 Initial revision (published)