Why is my solution(Square Dance - google jam problem) giving "wrong answer"?

Question

I made few archive problems from Google Jam 2020 competition. First I made 5 problems from qualfication round and it all works OK. Only last problem my algorithm is too slow so I don't get max points. But OK. I go to Round 1A and there are 3 problems. Problem 3 is called "Square Dance". It's description can be found here: https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b1355

I made a program. My program pass sample case as success. I also tested my program to few other situations and it works OK. But when I upload my solution I got "Wrong Answer" in google test case set.

For example. This situations works perfect for my solution:

1
5 5
1 1 1 1 1
1 1 1 1 1
1 1 2 1 1
1 1 1 1 1
1 1 1 1 1

It gives answer 66 because there will be 3 rounds:

1 1 1 1 1
1 1 1 1 1
1 1 2 1 1
1 1 1 1 1
1 1 1 1 1
26

1 1 1 1 1
1 1 0 1 1
1 0 2 0 1
1 1 0 1 1
1 1 1 1 1
22

1 1 0 1 1
1 1 0 1 1
0 0 2 0 0
1 1 0 1 1
1 1 0 1 1
18

So everything works OK.

But why it fails on google test.

Is there somethink that I don't understand? Or some bug in code? But it works OK for many tested cases that I test...

My source code:

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int sizeX;
int sizeY;
int** map;
bool** eliminateTable;


bool calculateWhoToEliminate()
{
    for (int y = 0; y < sizeY; ++y)
    {
        memset(eliminateTable[y], 0, sizeX);
    }

    bool toEliminate = false;

    for (int y = 0; y < sizeY; ++y)
    {
        for (int x = 0; x < sizeX; ++x)
        {
            if (map[y][x] == 0)
                continue;

            int skillOfNeightbours = 0;
            int neightboursCount = 0;

            //w lewo
            int px = x - 1;
            while (px >= 0)
            {
                if (map[y][px] != 0)
                {
                    skillOfNeightbours += map[y][px];
                    neightboursCount++;
                    break;
                }
                px--;
            }

            //w prawo
            px = x + 1;
            while (px < sizeX)
            {
                if (map[y][px] != 0)
                {
                    skillOfNeightbours += map[y][px];
                    neightboursCount++;
                    break;
                }
                px++;
            }

            //w gore
            int py = y - 1;
            while (py >= 0)
            {
                if (map[py][x] != 0)
                {
                    skillOfNeightbours += map[py][x];
                    neightboursCount++;
                    break;
                }
                py--;
            }

            //w dol
            py = y + 1;
            while (py < sizeY)
            {
                if (map[py][x] != 0)
                {
                    skillOfNeightbours += map[py][x];
                    neightboursCount++;
                    break;
                }
                py++;
            }

            if (map[y][x] * neightboursCount < skillOfNeightbours)
            {
                eliminateTable[y][x] = true;
                toEliminate = true;
            }
        }
    }

    return toEliminate;
}

void eliminate()
{
    for (int y = 0; y < sizeY; ++y)
    {
        for (int x = 0; x < sizeX; ++x)
        {
            if (eliminateTable[y][x])
            {
                map[y][x] = 0;
            }
        }
    }
}

int countScore()
{
    int score = 0;
    for (int y = 0; y < sizeY; ++y)
    {
        for (int x = 0; x < sizeX; ++x)
        {
            score += map[y][x];
        }
    }
    return score;
}

int solve()
{
    int score = 0;
    while (true)
    {
        score += countScore();
        if (calculateWhoToEliminate())
        {
            eliminate();
        }
        else
        {
            break;
        }       
    }
    return score;
}

int main()
{
    int testCasesCount;
    cin >> testCasesCount;
    for (int test = 1; test <= testCasesCount; ++test)
    {
        cin >> sizeX;
        cin >> sizeY;
        map = new int*[sizeY];
        eliminateTable = new bool*[sizeY];
        for (int y = 0; y < sizeY; ++y)
        {
            map[y] = new int[sizeX];
            eliminateTable[y] = new bool[sizeX];

            for (int x = 0; x < sizeX; ++x)
            {
                cin >> map[y][x];
            }
        }

        int r = solve();

        cout << "Case #" << test << ": " << r << endl;

        for (int y = 0; y < sizeY; ++y)
        {
            delete map[y];
            delete eliminateTable[y];
        }
        delete map;
        delete eliminateTable;
    }

    //system("pause");

    return 0;
}

`bool **`, `int **map` -- You're including ``, so why are you not using it here? There is no need for two-star pointers. — PaulMcKenzie, May 06 '20 at 16:40
"description can be found here:" - *No*! Stackoverflow questions should be self contained. Everything relevant should be *in* the question, *not* behind external links that rot over time. — Jesper Juhl, May 06 '20 at 16:46
`memset(eliminateTable[y], 0, sizeX);` -- This is not correct. This should be `memset(eliminateTable[y], 0, sizeX * sizeof(bool));`. If you had used `std::fill_n` then the syntax would work, i.e. `std::fill_n(eliminateTable[y], sizeX, 0);`. You were partially filling in the `bool` array with 0 values, thus maybe this was the issue. — PaulMcKenzie, May 06 '20 at 18:43

score 0 · Answer 1 · answered May 06 '20 at 18:50

0

Whether this fixes the problem or not, this definitely is a bug:

memset(eliminateTable[y], 0, sizeX);

This should be:

memset(eliminateTable[y], 0, sizeX * sizeof(bool));

The memset function third argument is the number of bytes, not the number of items.

Possibly that memset call you were doing was only partially filling the bool array with 0, thus you were not getting the correct results due to utilizing uninitialized portions of the bool array.

answered May 06 '20 at 18:50

PaulMcKenzie

34,698
4
24
45

No. sizeof(bool) is 1. – Marcin May 06 '20 at 20:57
[Please read](https://stackoverflow.com/questions/4897844/is-sizeofbool-defined-in-the-c-language-standard). Do not assume what it is -- actually write the correct code. – PaulMcKenzie May 06 '20 at 21:08

score 0 · Answer 2 · answered May 07 '20 at 14:03

0

OK. I found the solution.

score has to be long long
not: cin >> sizeX; cin >> sizeY; but: cin >> sizeY; cin >> sizeX;

because first is rows, then columns.

answered May 07 '20 at 14:03

Marcin

9
4

Why is my solution(Square Dance - google jam problem) giving "wrong answer"?

2 Answers2