You are not logged in. Please login at www.codechef.com to post your questions!

×

LEBOMBS - Editorial

2
1

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.

This question is marked "community wiki".

asked 11 Aug '12, 15:32

yellow_agony's gravatar image

4★yellow_agony ♦♦
1243837
accept rate: 0%


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
link

answered 09 Nov '16, 02:09

kanha95's gravatar image

2★kanha95
1
accept rate: 0%

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

(09 Nov '16, 02:42) kanha952★
 #include<iostream>
     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?

link

answered 04 Aug '17, 11:32

kaizoku876's gravatar image

2★kaizoku876
11
accept rate: 0%

edited 04 Aug '17, 11:35

Your code fails for this configuration

1 5 10101

(04 Aug '17, 12:44) vijju123 ♦5★

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

link

answered 19 Dec '17, 20:16

mohmum's gravatar image

2★mohmum
2
accept rate: 0%

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

(19 Dec '17, 20:38) beginner_11110★

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

link

answered 19 Dec '17, 20:42

llgokull_007's gravatar image

2★llgokull_007
101
accept rate: 0%

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

link

answered 11 Jan, 01:36

sharmajsr's gravatar image

2★sharmajsr
11
accept rate: 0%

edited 15 Jan, 18:29

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,795
×1,213
×805
×15

question asked: 11 Aug '12, 15:32

question was seen: 4,470 times

last updated: 15 Jan, 18:29