ZOMOCAV - RunTime Error

help
, , , ,
1

I have been solving the questionZOMOCAV.
My Code is running on my local machine correctly for simple test cases. But it gives runtime error(SIGABRT) on CodeChef and on GeeksForGeeks IDE.

I am not able to figure out the error in my Code.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void updateDiff(std::vector<int> &Diff, const std::vector<int> &C, int N)
{	
	for (int i = 1; i <=N; ++i)
	{
		Diff[max(1,i-C[i])]+=1;
		Diff[min(N,i+C[i])+1]-=1;
	}
}

void finalArr(std::vector<int> &Diff, int N)
{
	for (int i = 2; i <=N; ++i)
		Diff[i]=Diff[i-1]+Diff[i];
}

string issufficient(const std::vector<int> &Diff, const std::vector<int> &H, int N)
{
	for (int i = 1; i <=N; ++i)
	{
		if(Diff[i]!=H[i])
			return "NO";
	}

	return "YES";
}

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

	int test_cases; scanf("%d",&test_cases);
	int N;
	std::vector<int> C(1000,0); std::vector<int> H(1000,0);
	std::vector<int> Diff(1000,0);

	for (int i = 0; i < test_cases; ++i)
	{

		scanf("%d",&N);

		for (int j = 1; j <=N; ++j)
			scanf("%d",&C[j]);
		for (int j = 1; j <=N; ++j)
			scanf("%d",&H[j]);

		updateDiff(Diff,C, N);
		finalArr(Diff,N);
		sort(Diff.begin(), Diff.begin()+N+1);
		sort(H.begin(),H.begin()+N+1);

		cout<<issufficient(Diff,H,N)<<endl;

		//Changed Diff vector back to original having 0's everywhere
		std::fill(Diff.begin(),Diff.end(),0);
			
	}
}
2

This is wrong: it should be

std::fill(Diff.begin(),Diff.end(),0);

(you are filling past the end of the vector, otherwise! :))

3

Corrected!
It’s still giving runtime error upon submission on CodeChef. :sweat_smile:

4

It will still break, presumably, if N > 1000.

5

But it’s not giving correct results even for Subtask #1 where N<1000.

6

Sorry, I meant N >= 1000. Subtask 1 allows N to be 1000. I’ll generate some testcases of that size locally and see what happens :slight_smile:

Edit:

With the line:

   for (int i = 2; i <=N; ++i)
        Diff[i]=Diff[i-1]+Diff[i];

the vector Diff needs to have size at least N + 1. Since you’re initialising it with 1000, and N can be 1000, this will break.

The line Diff[min(N,i+C[i])+1]-=1; requires Diff to be even larger :slight_smile:

2 Likes
7

Awesome! Thanks :smiley:

1 Like
8

For anyone interested: I used this (which I wrote during the Contest for debugging):

// Simon St James (ssjgz) - 2019-08-03
#include <iostream>
#include <vector>
#include <algorithm>

#include <cassert>

#include <sys/time.h>

using namespace std;

int main(int argc, char* argv[])
{
    struct timeval time;
    gettimeofday(&time,NULL);
    srand((time.tv_sec * 1000) + (time.tv_usec / 1000));
    const int numCaves = 1000;
    const int maxHealth = rand() % 100 + 1;
    const int maxRadiationPower = rand() % numCaves + 1;
    
    cout << 1 << endl;
    cout << numCaves << endl;
    
    vector<int64_t> radiationPower;
    for (int i = 0; i < numCaves; i++)
    {
        radiationPower.push_back((rand() % maxRadiationPower) + 1);
    }
    for (const auto& x : radiationPower)
    {
        cout << x << " ";
    }
    cout << endl;
    
    
    const bool generateYES = ((rand() % 4) == 0);
    if (generateYES)
    {
        vector<int64_t> radiationLevel(numCaves, 0);
        for (int i = 0; i < numCaves; i++)
        {
            const int radiationRange = radiationPower[i];
            const int radiationRangeLeft = max(0, i - radiationRange);
            const int radiationRangeRight = min(numCaves - 1, i + radiationRange);
            
            for (int j = radiationRangeLeft; j <= radiationRangeRight; j++)
            {
                radiationLevel[j]++;
            }
        }
        auto zombieHealth = radiationLevel;
        random_shuffle(zombieHealth.begin(), zombieHealth.end());
        for (const auto& x : zombieHealth)
        {
            cout << x << " ";
        }
        cout << endl;
    }
    else
    {
        for (int i = 0; i < numCaves; i++)
        {
            cout << ((rand() % maxHealth) + 1) << " ";
        }
        cout << endl;
    }
    return 0;
}

to generate random testcases, and then compiled mskhan’s code using clang and it’s STL debugging mode:

clang++ -std=c++14 -stdlib=libc++ mskhan-zombie-and-caves.cpp -g3 -D_LIBCPP_DEBUG=1

which flushes out errors pretty quickly :slight_smile:

1 Like
9

Do you have any source, where I can read more about generating test cases ? It seems to be pretty great and useful.

10

There’ve been a couple of recent threads:

https://discuss.codechef.com/t/test-your-solution/34422/3

… and another one which I can’t find at the moment :slight_smile:

It’s an absolutely invaluable technique - I use it as a matter of course :slight_smile:

ZOMCAV was an unusual one as a completely randomly generated testcase is practically always a NO, which I why I needed that generateYES in there :slight_smile: