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.

2 Likes

By “next two houses” it means the next two house after the drop. If there’s a drop after some houses, the drop does not go to the houses that came before.

I got the question wrong and I don’t understand why. My code worked with several test cases I generated, and I got the same answers as another code that was scored as correct. Here is my code: CodeChef: Practical coding for everyone. Please point out what is causing a wrong answer.

Turns out there was nothing wrong with my logic. The errors occurred from the input. Not only did I have to strip out extra spaces, but also had to ensure that there was any input at all.

I think we are treaversing from end of the array to start.

sir my code working properly in my compiler but in codechef compiler the code is not running …what to do?

import java.util.*;

class Codechef {

public static void main(String[] args) {
	// TODO Auto-generated method stub
	Scanner sc=new Scanner(System.in);
	int t=sc.nextInt();
	for(int y=0;y<t;y++) {
	String name=sc.next();
	int n=name.length();
	boolean found=false;
	//System.out.println("name length"+name);
	//System.out.println(name.length());
	Stack<Character>st=new Stack<>();
	Stack<Character>s=new Stack<>();
	for(int i=0;i<n;i++) {
		st.push(name.charAt(i));
	}
	//System.out.println("st stack"+st);
	for(int i=0;i<n;i++) {
		s.push(st.pop());
	}
	//System.out.println("s stack"+s);
	int sz=s.size()/3;
	//System.out.println(sz);
	if(s.size()<3) {
		//System.out.println("NO");
		found=false;
	}
	else {
		
		for(int i=0;i<sz;i++) {
	if(s.peek()=='0') {
		//System.out.println("NO");
		found=false;
	}
	if(s.peek()=='*') {
	
		for(int j=0;j<3;j++) {
			s.pop();
		}
	//System.out.println("after 3 element : "+i+"iteration"+s.size());
	}
	
	
	
	if(s.size()<3 &&s.size()>0 ) {
		//System.out.println("NO");
		found=false;
	}
	
	}
	if(s.isEmpty()) {
		//System.out.println("YES");
		found=true;
	}
	}
	
	//System.out.println("last : "+s);
	if(found) {
		System.out.println("YES");
	}
	else {
		System.out.println("NO");
	}

}
}

}

this is my code::::::::

Take input differently in Python
Like this
s = ‘’
while not s:
s = input().strip()

I spend whole day thinking about the logic and it turns out it was because input

1 Like

The question can be solved without using the stack. The idea is:
Traversing from the start to end of the array, at any index i there is a house, check the str[i-1] and str[i-2] if any of the value is ‘’ then the house will get the food, but if none of the value is '’ the house will never get the food, so we return “NO”.

If the test case is *0*00*000,one house can’t feed the food .But if we pop two zeros for each ‘*’,we will get ‘Yes’ as the answer. But what we should get is ‘No’.
Could anyone please clarify how the above specified solution works for this testcase-

*0*00*000
1 Like

yeah it should not work for this case *0*000*00 according to question but according to logic in solution its giving YES for this.please feel free to correct me if i am wrong.

it doesnt work for *0*000*00