CODE1601-Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Ashish Ahuja

Tester: Ashish Ahuja

Editorialist: Ashish Ahuja

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

String processing

String Manipulation

PROBLEM:

The problem focuses on string manipulation,here a string of 0s and 1s.

QUICK EXPLANATION:

The problem poses a situation in front of the programmer to find out the most efficient algorithm for bringing together a specified number of 1s together.

EXPLANATION:

It is one of the simpler problems, focused for the newbie programmers. It urges a programmer to manipulate the given string of 0s and 1s in such a way all the 1s are brought together in least possible iterations, and hence in minimum possible time.
The solution to the problem has been aimed to check the positioning of each character of the string. This has been done by keepin track of the characters before and after the positions where a 1 is encountered. This is shown below -

for(int i = 0 ; i < median ; i++)
    left += position[i];
for(int i = median + 1 ; i<=m ; i++)
    right += position[i];

Then towards the information acquired from above is used to finally find out the minimum number of ways to bring the 1s together.

for(int i = m+1 , j = 1 ; i < position.size() ;j++, i++){
    left -= position[j];
    left += position[var_median];
    var_median++;
    right -= position[var_median];
    right += position[i];
    long long temp = right - left + (2*median - m - 1)*position[var_median];
     ans = min(ans , temp);
}

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.