PROBLEM LINK
Author: Pushkar Patel
Tester: Sumanth Nidamanuri, Souvik Mondal, Jaymeet Mehta
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Queue Data Structure
PROBLEM:
Given a binary string consisting of 0s and 1s, an operation on this string is defined as a 0 converting to 1 if it has 1 as an unisolated immediate neighbour.
An array P consisting of D integers is given where any index i in this array denotes that before performing the
i^{th} operation, the digit at index P_i in the binary string is isolated from the previous digit (indexing starts from 1).
The user has to count the number of 1s in the string after D operations.
EXPLANATION
To solve subtask 1,
For each day, maintain an array to check which person is isolated from the previous person before the start of that day and iterate over the binary string, changing the 0s with unisolated 1s immediately adjacent to it to 1s.
At the end of D^{th} day, count the number of 1s in a string.
This approach can be further improved.
Instead of iterating over the string each day, the indexes with 1s which have unisolated 0s adjacent to them can be added in a queue and after all the indexes of a particular day are added, a delimiter can be pushed to separate them from another day. For each day, change the neighbouring 0s of the front index of the queue to 1s and add those indexes to the back of the queue if they can further infect their neighbours. Pop the front element and continue till all the days are over or if there are no more elements to push.
Setter’s Code: CodeChef: Practical coding for everyone
Tester’s Code: CodeChef: Practical coding for everyone
Time Complexity: O(n)
Since each position can be added into the queue at most once.
Please feel free to share your approaches and solutions too 
.
