UVa 562

[oldspiderdude]

Hi, I've coded the solution to UVa 562:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=503

After debugging using UVa's debugging data, my output does not show any inconsistencies.

Could someone tell me why the judge returns wrong answer?

Here is my code

#include <iostream>

using namespace std;

int main()
{
    int numCases, numCoins, sum, halfSum;
    bool foundRow, spaceBefore=false;
    int coins[100];
    cin >> numCases;
    for (int loopp=0; loopp<numCases; loopp++) {
        bool** addSum=new bool*[100];
        for (int loop=0; loop<100; loop++) {
            addSum[loop]=new bool[25002]();
        }
        /* I added the part below just in case the initialization of the
           array did not set everything to false, but even with this part,
           it does not work.*/
        /* for (int looppp=0; looppp<100; looppp++) {
            for (int loopppp=0; loopppp<25002; loopppp++) {
                addSum[looppp][loopppp]=false;
            }
        }*/ 
        cin >> numCoins;
        if (numCoins==0) {
            if (spaceBefore) cout << endl;
            cout << 0;
            spaceBefore=true;
            continue;
        }
        sum=0;
        foundRow=false;
        for (int loop=0; loop<numCoins; loop++) {
            cin >> coins[loop];
            sum+=coins[loop];
        }
        if (numCoins==1) {
            cout << coins[0] << endl;
            continue;
        }
        halfSum=sum/2;
        for (int loopRow=0; loopRow<numCoins; loopRow++) {
            if (loopRow==0) {
                addSum[loopRow][0]=true;
                addSum[loopRow][coins[loopRow]]=true;
            }
            else {
                for (int loopCol=0; loopCol<=halfSum; loopCol++) {
                    if (loopCol-coins[loopRow]>=0) {
                        addSum[loopRow][loopCol]=addSum[loopRow-1][loopCol-coins[loopRow]]||
                        addSum[loopRow-1][loopCol];
                        if (loopCol==coins[loopRow]) {
                            addSum[loopRow][loopCol]=true;
                        }
                    }
                    else {
                        addSum[loopRow][loopCol]=addSum[loopRow-1][loopCol]||
                        (loopCol==coins[loopRow]);
                    }
                }
            }
        if (addSum[loopRow][halfSum]) {
            if (spaceBefore)cout << endl;
            cout << sum-2*halfSum;
            spaceBefore=true;
            foundRow=true;
            break;
        }
        }
    if (!foundRow) {
        for (int checkCol=halfSum-1; checkCol>=0; checkCol--) {
            for (int checkRow=numCoins-1; checkRow>=0; checkRow--) {
                if (addSum[checkRow][checkCol]) {
                    if (spaceBefore) cout << endl;
                    cout << sum-2*checkCol;
                    spaceBefore=true;
                    foundRow=true;
                    break;
                }
            }
        if (foundRow) {
            break;
        }
        }
    }
    }
    return 0;
}

[Duthomhas]

Alas, I hate that site. It is broken in too many ways and, even though I've been interested in playing with some of the problems posted here, I've decided I'm done wasting time trying to load and log-in to their site.

I suspect that there is something you are missing: check corner cases. UVa problems give you very simplistic sample inputs, but are likely checked against much more aggressive inputs, including corner cases.

Try to identify them, and test your code against them.

This looks like a variation of the classic rod-cutting dynamic programming problem.

Sorry this wasn't much of an answer.