Weird Program Crash

[zero-impact]

Hi everybody.

I was working on a DWITE question from last year http://dwite.org/questions/time_for_change.html
and I believe I have a correct solution.

On the full test case it gets the first 2 correct answer then crashes.

Can anyone help me discover the error I have made?

c++:

#include <iostream> #include <fstream> #include <vector> using namespace std; int main (void) {         ifstream fin ("coins.txt");         for (int abc = 0; abc < 5; abc++) {                 int sum,N;                                                                     fin >> sum >> N;                                        vector <int> state(sum + 1, 99999);                                                                                                         vector <int> coin (N);                                   for (int i=0; i < N; i++)                        fin >> coin [i];                                                 state[0] = 0;                                                   for (int i = 0; i < N; i++) {                             for (int j = 0; j <= sum; j++) {                                                int t = j + coin [i];                                             if (state[j] + 1 < state[t]) {                                          state[t] = state[j] + 1;                                                }                                                                                        }                 }                 cout << endl  << state [sum];         }         getchar();         return 0; }

The test case is attached.

[DemonWasp]

Without compiling, running or debugging your program (I don't have a C++ compiler available at the moment; I'm posting from work while waiting on another machine), I'd guess that the issue has to do with invalid access to your vector. Try replacing the state[foo] accesses with state.at ( foo ) and then try running it.

[zero-impact]

Thanks DemonWasp, I figured thats what it was but couldn't find it for the life of me.

What happened was that I didn't take into account that int t = j + coin [i]; could be larger than the target value, which is also the size of my vector. DOH!

[DemonWasp]

I'm a little surprised that I got it in one.

Regardless, you should probably be using at() whenever possible. It does just the same thing as [], except that it does bounds-checking. Since correctness is more important than programming for speed, I'd use at() until you're dead certain that it will never exceed its bounds AND that it needs to be faster.

[zero-impact]

Thanks for the tip, but thats not actually how I found it. When I replaced it all with at() vista just gave me a message saying the program closed in an unusual fashion or something along those lines. I ended up just doing another careful read through to find it. Oh how I wish linux had better power saving performance on my laptop.

[DemonWasp]

Ah, right. The reason it terminated abnormally is because vector::at() will throw an exception if you index it outside the array bounds; if you put a try-catch around your access blocks, you can catch that exception and do something useful with the information (generally logging or similar).

[zero-impact]

ooooook, that makes more sense. Thanks for the tip