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

×

PREFINVS - editorial

4
2

PROBLEM LINK

Practice
Contest

CONTEST PANEL

Author: Ildar Gainullin
Tester: Oleksandr Kulkov
Editorialist: Prateek Gupta

DIFFICULTY

EASY

PROBLEM

Given a binary string, you need to transform this into a string consisting of only zeros by applying a specific operation number of times. The operation allows you to choose a prefix of the string and flip all the bits i.e '0' to '1' and '1' to '0'.

EXPLANATION

The key is to observe that we need to reverse iterate the string and maintain the state as to how many times we have applied the given operation. When you reverse iterate the string and apply the operation on some index, it will affect the whole prefix $S[0..\ index\ -\ 1]$. Having said that, when we arrive at a particular index in the string, we already know the number of operations that have been applied till now. Based on the digit at this index and number of operations applied, we decide what is the actual digit at this position. If it is '0', we move forward, else we again flip the bits for a prefix ending at this position. Below is the simple pseudo code which will help you to understand things much better. operations = 0 for ( i = s.length() - 1 to i = 0 ) { if ( digit(i) ^ operations ) { operations ^= 1; } }

It must be clear from the above snippet, that in case the number of operations are even, the state of the current bit will remain same, otherwise (bit ^ 1). Since, we are traversing a string once, the overall complexity will be $O(N)$ where $N$ is the length of the given string. For details on the implementation, have a look at the author or tester's solution.

SOLUTIONS

Author solution can be found here.
Tester solution can be found here.

This question is marked "community wiki".

asked 28 May '17, 11:34

prateekg603's gravatar image

5★prateekg603
20421223
accept rate: 0%

edited 30 May '17, 13:02

admin's gravatar image

0★admin ♦♦
19.8k350498541


nice solution @anurag_6767 and @osama_binladen editorials could have been more easy

link

answered 03 Jan '18, 23:31

worldunique's gravatar image

3★worldunique
1297
accept rate: 0%

Please update solution links.

link

answered 31 May '17, 12:35

godslayer12's gravatar image

1★godslayer12
419210
accept rate: 7%

I am not able to understand it!! Can anyone describe it?? P.S: I passed all test cases of task #1 and got TLE in task #2!

link

answered 31 May '17, 13:53

dishant_18's gravatar image

5★dishant_18
61419
accept rate: 12%

@dishant_18 check out my solution very easy approach solution link

link

answered 31 May '17, 15:36

hemant_dhanuka's gravatar image

5★hemant_dhanuka
533112
accept rate: 3%

edited 31 May '17, 15:37

link

answered 01 Jun '17, 19:14

osama_binladen's gravatar image

3★osama_binladen
34
accept rate: 0%

edited 01 Jun '17, 19:21

Check this solution... easily understandable... https://www.codechef.com/viewsolution/14225387

link

answered 12 Jun '17, 00:03

anurag_6767's gravatar image

4★anurag_6767
1
accept rate: 0%

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:

×3,770
×834
×349
×43
×6

question asked: 28 May '17, 11:34

question was seen: 1,508 times

last updated: 03 Jan '18, 23:31