WASHHAND - Editorial

PROBLEM LINK

Practice
Contest

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 :smiley:.

1 Like

Really enjoyed the question. Did this using BFS.
https://www.codechef.com/viewsolution/31030472

2 Likes

Are you sure n*d would pass :thinking:
btw I did it in n+d

Updated it in the question! The complexity was actually O(n).
Thanks @akshitm16 for pointing this out :smiley:

1 Like

Yaa, I was wondering how could n^2 can pass considering the constraints(though I didn’t read the explanation given by you as I was too lazy).
I’ll share my method in future as I am bit busy now.
for the time being, here is the link to the solution-
https://www.codechef.com/viewsolution/31402026

1 Like

Similar to a problem I did on Codeforces. Solved this using BFS.

@thepushkarp I think my approach was a bit different . I used bit manipulation to deal with the problem .It was really a nice problem .
here is my code : CodeChef: Practical coding for everyone

1 Like