THESAV - Editorial

PROBLEM LINK:

Contest

Practice

Author: Drishti Sharma

Tester: Shivani Srivastava

Editorialist: Kaushambi Gujral

DIFFICULTY:

EASY

PREREQUISITES:

Stack

PROBLEM:

Considering that one food package can feed two houses, and given the way each package is dropped, you have to tell whether or not each house is fed.
Only the next two houses from the position where the package is dropped can feed on that package.
Note that, the basic motive is to feed all the houses.

QUICK EXPLANATION:

Use a stack. For every ‘0’, push it in the stack. For each ‘*’, pop two elements out of the stack.

EXPLANATION:

The problem can easily be solved using the concept of a stack. Let us take a stack that accepts char type of input. We will feed out entire string to the stack.
If the character is a ‘0’, it means that it is an indication of the presence of a house. We will push this element into the stack. We know that each package can feed 2 homes.
So, if a ‘*’ occurs, it indicates a dropped package for which we will pop(feed) 2 elements(houses/‘0’).

In the end, simply check if your stack is empty or not. If empty, it means that all the houses were fed. Otherwise, they weren’t.

AUTHOR’S AND TESTER’S SOLUTIONS:

The solution can be found here.

Could you clear my doubt?
The question mentions “only the next two houses from the position where the package is dropped can feed on that package”

According to the logic that you specified won’t even “00*” give YES when according to the question it should’t have?

Please correct me if I am wrong.

//