gagannagpal68's blog

How to solve this problem in less than O(n^2) time?
By gagannagpal68, history, 9 months ago, In English

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?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gagannagpal68 (previous revision, new revision, compare).

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1411D - Grime Zoo Same problem

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry, I misunderstood condition, my hint is completely innapropriate for this problem(

→ Reply
»
9 months ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

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$$$

→ Reply