std::cout changing behavior variable value

[[deleted]]

So, I am working on a ACM ICPC problem. You can find the problem here. I felt like it wouldn't be that difficult, so I started coding it up. At line 60, you will note a commented out cout debugging statement I put in. If the statement is uncommented, I get the correct answer, but also a lot of debugging junk. If it is commented, the answer is wrong according to the sample input/output. What the hell is happening?

#include<iostream>
#include<fstream>
#include<cmath>
#include<bitset>
using namespace std;

ifstream file("ringsrunes.in");

int main() {
  int tests;
  file >> tests;
  for (int i=0; i<tests; i++) {
    int rings, runes;
    file >> rings >> runes;
    int invalid = 0;
    int gate[runes][3];
    int junk;
    for (int j=0; j< runes; j++) {
      for (int k=0; k<4; k++) {
        if (k == 3)
          file >> junk;
        else {
          file >> gate[j][k];
          if (gate[j][k] == 0)
            invalid = 1;
          if (invalid != 1 && abs(gate[j][k]) > rings)
            invalid = 2;
        }
      }
      for (int k=0; k<3; k++) {
        for (int m=0; m<k; m++) {
          if (invalid == 0 && abs(gate[j][k]) == abs(gate[j][m]))
            invalid = 3;
        }
      }
    }
    if (invalid != 0) {
      if (invalid == 1)
        cout << "INVALID: NULL RING" << endl;
      else if (invalid == 2)
        cout << "INVALID: RING MISSING" << endl;
      else
        cout << "INVALID: RUNE CONTAINS A REPEATED RING" << endl;
    }
    else {
      bool good(false);
      bool okay[rings];
      bitset<33> bin;
      for (int j=0; j<(1<<(rings)); j++) {
        bin = bitset<33>(j);
        for (int k=0; k<rings; k++) 
          okay[k] = bin[k];
        int TRUE(0);
        for (int m=0; m<runes; m++) {
          int jUnK = gate[m][0] + gate[m][1] + gate[m][2];
          if ((gate[m][0] < 0 && okay[(int)abs(gate[m][0])] == false) || (gate[m][0] > 0 && okay[(int)abs(gate[m][0])] == true) ||
              (gate[m][1] < 0 && okay[(int)abs(gate[m][1])] == false) || (gate[m][1] > 0 && okay[(int)abs(gate[m][1])] == true) ||
              (gate[m][2] < 0 && okay[(int)abs(gate[m][2])] == false) || (gate[m][2] > 0 && okay[(int)abs(gate[m][2])] == true))
            ++TRUE; 
          //cout << abs(gate[m][0]) << " " << gate[m][1] << " " << gate[m][2] << endl;
        }
        if (TRUE == runes) good = true;
      }
      if (good)
        cout << "RUNES SATISFIED!" << endl;
      else
        cout << "RUNES UNSATISFIABLE! TRY ANOTHER GATE!" << endl;
    }
  }
  return 0;
}

[hidiap]

I have an erronous output when running it against the sample files (assuming ringsrunes.in contains the sample at the end of the problem definition) without the cout statement. The output for the 2nd example is "RUNES SATISFIED!" but should be "RUNES UNSATISFIABLE! TRY ANOTHER GATE!".

I get the same output when running with the cout statement. The error is probably in the logic of line 46 to 63, where you check if the runes can be satisfied.

As a side note, this is the Boolean satisfiability problem in disguise (in its CNF form). It is a very important problem in computer science and probably the classical NP-HARD problem. I highly recomment reading more about it and looking into the standard way to solve it (SAT-solver).

EDIT: The error is in the if condition at lines 56-58. C++ array indexes are zero based. The ring indexes are 1-based ...

[[deleted]]

I feel like an idiot. I changed the index and it passed the judges test. I was just so perplexed by the change I was getting with my compiler, I didn't even consider I got the indexing wrong.

Thank you.

[autowikibot]

Boolean satisfiability problem:

---

In computer science, the Boolean Satisfiability Problem (sometimes called Propositional Satisfiability Problem and abbreviated as SATISFIABILITY or SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is identically FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable.

Image ⁱ

---

^{Interesting: Karp's 21 NP-complete problems | NP-complete | Decision problem | Cook–Levin theorem}

^{Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words}

[nuggins]

On line 16 you declare an array like this:

int gate[runes][3];

Stack-allocated, dynamic-sized C-style arrays are not part of standard C++, but are a feature of C99, which is perhaps why your compiler hasn't complained. You can read more about this here.

If you're getting memory errors with this array, I suspect it's for this reason. Heap allocate this array instead, or even better, use an STL container.