You are not logged in. Please login at www.codechef.com to post your questions!

×

CODE1601-Editorial

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 + (2median - 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.

This question is marked "community wiki".

asked 24 Mar '16, 16:48

se_aashish's gravatar image

0★se_aashish
32
accept rate: 0%

edited 28 Mar '16, 14:10

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,851
×3,820
×354
×38
×17
×10
×1

question asked: 24 Mar '16, 16:48

question was seen: 609 times

last updated: 28 Mar '16, 14:10