LEBOMBS - Editorial

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

Cake walk

PREREQUISITES:

None

PROBLEM:

You’re given an array of houses some of which have a bomb and others don’t. These bombs will explode simultaneously and when bomb in ith house explodes, it destroys adjacent houses. Your task is to find out the number of houses which aren’t destroyed.

QUICK EXPLANATION:

For every house check if it is destroyed or not.

DETAILED EXPLANATION:

There are two almost similar ways of solving this problem. Key idea is to find out for each house if it is destroyed or not. How do we check if ith house will be destroyed or not? It will be destroyed iff at least one of i-1, i and i+1th houses have a bomb. Just beware of the boundaries as first and last houses have only one adjacent house. So final solution is :

saved_count = 0  
for i from 1 to N  
    destroyed = false  
    if( S[i] == '1') destroyed = true  
    if( i > 1 and S[i-1] == '1') destroyed = true  
    if( i < N and S[i+1] == '1') destroyed = true  
    if( not destroyed)  
        saved_count += 1  
print saved_count      

An alternative solution would be to move over houses with bombs and mark those houses that will explode.

bool will_be_destroyed [N]
fill( will_be_destroyed, false)

for i from 1 to N
    if S[i] == '1'
        will_be_destroyed[i] = true
        if(i > 1) will_be_destroyed[i-1] = true
        if(i < N) will_be_destroyed[i+1] = true

saved_count = 0 
for i from 1 to N
    if(not will_be_destroyed[i])
        saved_count += 1

print saved_count

Both of these are O(N) solutions and very comfortably fit in time limit.

SETTER’S SOLUTION:

Will be uploaded soon.

TESTER’S SOLUTION:

Can be found here.

2 Likes

Whats wrong in my code??? Why is it showing NZEC everytime. Some one please help.

enter code here

import java.io.;
import java.util.
;

class acm {

public static void main(String[] args)
{
    
  FasterScanner sc=new FasterScanner(System.in);
  int t=sc.nextInt();
while(t>0){
    int n=sc.nextInt();
    String s=sc.nextString();
    int count=0;
    for(int i=0;i<n;i++){
        
        if(s.charAt(i)=='0'){
            if(i==0){
                if(s.charAt(i+1)!='1') count++;
            }
            else if(i==n-1){
                if(s.charAt(i-1)!='1') count++;
            }else{
                if(s.charAt(i-1)!='1' && s.charAt(i+1)!='1') count++;
            }
        }
    }
    
    System.out.println(count);
    t--;
}

}

}

class FasterScanner {
private InputStream mIs;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;

public FasterScanner() {
	this(System.in);
}

public FasterScanner(InputStream is) {
	mIs = is;
}

public int read() {
	if (numChars == -1)
		throw new InputMismatchException();
	if (curChar >= numChars) {
		curChar = 0;
		try {
			numChars = mIs.read(buf);
		} catch (IOException e) {
			throw new InputMismatchException();
		}
		if (numChars <= 0)
			return -1;
	}
	return buf[curChar++];
}

public String nextLine() {
	int c = read();
	while (isSpaceChar(c))
		c = read();
	StringBuilder res = new StringBuilder();
	do {
		res.appendCodePoint(c);
		c = read();
	} while (!isEndOfLine(c));
	return res.toString();
}

public String nextString() {
	int c = read();
	while (isSpaceChar(c))
		c = read();
	StringBuilder res = new StringBuilder();
	do {
		res.appendCodePoint(c);
		c = read();
	} while (!isSpaceChar(c));
	return res.toString();
}

public long nextLong() {
	int c = read();
	while (isSpaceChar(c))
		c = read();
	int sgn = 1;
	if (c == '-') {
		sgn = -1;
		c = read();
	}
	long res = 0;
	do {
		if (c < '0' || c > '9')
			throw new InputMismatchException();
		res *= 10;
		res += c - '0';
		c = read();
	} while (!isSpaceChar(c));
	return res * sgn;
}

public int nextInt() {
	int c = read();
	while (isSpaceChar(c))
		c = read();
	int sgn = 1;
	if (c == '-') {
		sgn = -1;
		c = read();
	}
	int res = 0;
	do {
		if (c < '0' || c > '9')
			throw new InputMismatchException();
		res *= 10;
		res += c - '0';
		c = read();
	} while (!isSpaceChar(c));
	return res * sgn;
}

public boolean isSpaceChar(int c) {
	return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public boolean isEndOfLine(int c) {
	return c == '\n' || c == '\r' || c == -1;
}

}

enter code here

I got it…i missed the case when n=1…

#include
using namespace std;
main()
{
int t = 0 ;
cin>>t;
while(t–)
{
string inp;
int b = 0 ;
int u = 0 ;
int s = 0 ;
cin>>s;
cin>>inp;
for(int i = 0 ; i < s;i++)
{
if(inp.at(i) == ‘1’ )
{
b -= 2 ;
if(i == 0 || i == s-1)
{
b += 1 ;
}
}
else if (inp.at(i) == ‘0’)
{
u++;
}
}
cout<<b+u<<endl;
}
return 0 ;
}

why is this solution wrong?

Your code fails for this configuration


1
5
10101

I’m getting WA. I don’t understand on which test case its failing. Someone please help?
link to solution: https://www.codechef.com/viewsolution/16605991

@mohmum your code fails for 1 1 1 answer should be zero but your code prints 1

Somebody, please tell me where does my program fail?
https://www.codechef.com/viewsolution/16606169

whats wrong in my C code for the problem LEBOMBS

LEBOMBS

https://www.codechef.com/viewsolution/17048802

can anyone tell me on which values my code fails …
Thanks

https://www.codechef.com/viewsolution/17555048

Can anyone help me with this code, please?

whats wrong in my solution??
\

#include
using namespace std;
int main(){
int i,n,t,count;
cin>>t;
while(t–){
count=0;
cin>>n;
char c[n];
for(i=0;i<n;i++)
cin>>c[i];
if(c[0]==‘0’&&c[1]==‘0’){
count++;
}
if(c[n-1]==‘0’&&c[n-2]==‘0’){
count++;
}
for(i=1;i<(n-1);i++){
if(c[i]==‘0’){
if(c[i-1]==‘0’&&c[i+1]==‘0’)
count++;
}
}
cout<<count<<endl;
}
return 0;
}

I’m getting WA. I don’t understand on which test case it is failing. Someone, please help? link to solution:
link text