Hii, I had been reading the editorial to this problem, and I find it difficult for me to understand the concept of
outcomments used here.Please help me in understanding the formula the editorialist has used in the explanation.
Asked by: mahawarvishal10 on Dec. 31, 2020, 9:57 p.m. Last updated on Dec. 31, 2020, 9:57 p.m.
Firstly the editorial asks, to select any two consecutive '?'s in a given string s , for exammple, s[L] and s[R]
Then it asks to calcuate the following two things :
1) put s[L] = 0, and s[R] = 1
where c1 being --> count of "1" in the range [ L, R ] not inclusive in s;
where c0 being --> count of "0" in the range [ L, R ] not inclusive in s;
Now what do we observe?
-->s[L] will pair up with all the 1s in the range ( L, R ) not inclusive.
which wil be c1
-->s[L] will pair up with all the 1s from [R+1, N] inclusive
Let this be OUT1
--> s[L] will pair up with all the 1s from [1, L-1] incsulive
Let this be OUT2
-->s[R] will pair up with all the 0s in the range (L,R) not inclusive.
which will be c0
-->s[R] will pair up with all the 0s from [R+1, N] inclusive
Let this be OUT3
-->s[R] will pair up with all the 0s from [1, L-1] inclusive
Let this be OUT4
--> Add 1 as we added s[L] = 0, s[R] =1, hence "01"
so the total pairs = c1 + c0 + 1 + OUT1 + OUT2 + OUT3 + OUT4
= R-L + OUT
to get the value we multiply x = (R-L)*x + OUT --> Equation I
2) put s[L] = 1 and s[R] = 0
where c1 being --> count of "1" in the range [ L, R ] in s;
where c0 being --> count of "0" in the range [ L, R ] in s;
now we just swapped the positions, so previous s[R] is now s[L]
hence has (R-L) new elements on the right with same old right side
elements from [R+1, N] which was OUT3
and if you notice for all possible pairs, you'll find it will from the same count
equation with the unchanged OUT
to get the value we multiply with y = (R-L)*y + OUT --> Equation II
if we subtract 2 equations( Equation I and II) we get
(R-L) * (x-y) <-- we need to minimize this
so it solely depends on which is smaller among two of x and y:
if x is smaller we tend to keep 10 or else 01
Now with some intuition we can come to this conlusion :
we can fill the entire '?' with 1 or 0
like in ?????? = 111111 or 000000
and greedily change every prefix to other value, like if you want to establish
01 we can change the prefixes to 0s and vice versa, and find the min of all the possibilities.
This can be done in O(n)
.
Sourav last updated on Jan. 12, 2021, 4:48 p.m.
Comment-1
Anonymous last updated on Jan. 12, 2021, 8:35 p.m.