AdvertisingAgency - passing all test but fails overall [TOPCODER]

Question

I am trying to solve the AdvertisingAgency problem from TopCoder. When I submit this code aand run system tests it shows that the program failed system tests. Hovewer when I run tests from the Test Panel it passess all of them. Do you have any idea on where the problem is?

Source code:

#include<iostream>
#include<vector>
using namespace std;
class AdvertisingAgency{
public:
    int numberOfRejections(vector<int>requests){
        int rejections=0;
        bool billboards[100];
        for(int request:requests){
            if(billboards[request]){
                rejections++;
            }
            else{
                billboards[request]=true;
            }
        }
        return rejections;
    }
};

Better to spend time with some of these [C++ books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) then on some bogus _competitive programming_ site. — Ron, Oct 12 '17 at 18:59
You are accessing `billboards[request]`, which is not initialized. This is UB. What problem do you have to solve / what is the expected outcome? — Stephan Lechner, Oct 12 '17 at 19:01

Slava · Accepted Answer · 2017-10-12T19:08:57.943

First of all you used unintialized array, which is UB. And as stated in problem, billboards numbered from 1 to 100. You use that number directly as array index, but array is zero based, so you have out of range problem, which also leads to UB:

 std::vector<bool> billboards( 100 ); // unlike array vector will be properly initialized 
 for(int request:requests) {
    auto &board = billboards[request-1]; // index is zero based
    rejections += board;
    board = true;
 }

score 0 · Answer 2 · answered Oct 12 '17 at 19:13

I solved this problem thanks to you! I added 'for' that set billboards values to false at the beginning of the function and it helped :)

#include<iostream>
#include<vector>
using namespace std;
class AdvertisingAgency{
public:
    int numberOfRejections(vector<int>requests){
        int rejections=0;
        bool billboards[101];
        for(int i=0;i<101;i++){
            billboards[i]=false;
        }
        for(int request:requests){
            if(billboards[request]){
                rejections++;
            }
            else{
                billboards[request]=true;
            }
        }
        return rejections;
    }
};

You do not need a loop, `bool billboards[101] = {};` is enough. — Slava, Oct 12 '17 at 19:16

AdvertisingAgency - passing all test but fails overall [TOPCODER]

2 Answers2