< Back to forum

Help in understanding editorial.

Hii, I had been reading the editorial to this problem, and I find it difficult for me to understand the concept of out comments 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.


Comment-1

Anonymous last updated on Jan. 12, 2021, 8:35 p.m.

Comment-2

Anonymous last updated on Jan. 12, 2021, 8:53 p.m.

Test Ignore this

Shjgfe last updated on April 24, 2021, 8:41 a.m.

Enter your answer details below:


Preview

Enter your comment details below:

Preview




1 Answer(s)

avatar

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)

ashnove last updated on Jan. 4, 2021, 1:22 a.m. 2    Reply    Upvote   

avatar

.

Sourav last updated on Jan. 12, 2021, 4:48 p.m.

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.