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.

1 Like

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: https://www.codechef.com/viewsolution/27753095. 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::::::::