sw1ft's blog

Judge generating different outputs than in my laptop
By sw1ft, history, 9 years ago, In English

Guys the judge is giving different answers. It's happened like 3 times now but I fixed them by removing ternary operators. Here's an example:

submission link

Any help?

Thanks!

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you sure your array size is correct?

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

Don't forget -O2 flag...

run your code with this command:

g++ 149A.cpp -o o -O2 -std=c++11 && ./o
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    It is not a bug. Compiler sees that there's a line s += a[c++];. Since accessing an element beyond array bounds is an undefined behavior, compiler is allowed to assume here that c is always less than or equals to 12. Therefore, the entire block of if (c > 12) is removed as always false, therefore the code cannot possibly return -1, and therefore it cannot pass any test that expects the value of -1.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sry but, what's this for?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It enables optimizations, level 2 (used on CF and other major judges, like TopCoder, afaik). They make your code run significantly faster (locally, of course) and also rely on some assumptions about your code. That it does not contain mistakes, e.g. like here. Again, you should not guess what kind of effects will happen. If your code is correct, it will be correct after optimizations. If it's not, anything can happen.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you are exceeding the array bounds. add c < 12 to while loops and change your codes accordingly.

→ Reply
»
9 years ago, # |
  Vote: I like it -20 Vote: I do not like it

If you don't want such things to happen, just write in Java.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey everyone I have already fixed it, here's the submission link.

I don't really know what I was doing. I changed the while loop to a for loop that stops if it needs more than 12 months (or before if the desired height was already achieved). The only thing I have to check now is if after all this months it's impossible to achieve such height which is when it returns -1.

I'm still not sure if it's 100% accurate but I don't want to spend any more time in such a simple problem (not exactly (for me) but I know it is)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Here is a very good explanation of what happened. Whenever an undefined behavior happens in C++ program (in any form), you have absolutely no guarantees anymoure. The program may crash, may produce ridiculous answer, may wipe your HDD, may call your grandmother, just whatever, even something illogical.

    If you see that your program produces different outputs on different machines, most probably it's undefined behavior: look for array out-of-bounds errors, integer overflows in signed types (e.g. int, but not unsigned int), lack of returns in function (btw, compile with -Wall to get warned about that), etc. All these errors would give you a clean runtime exception in managed languages (like Java or Python), but C++ is not the case. It assumes that programmer makes no mistakes.

    → Reply
»
9 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Maybe is because you use linux. You should try android. I use cppdroid on it and it works well.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

By the way, no need in swapping values by hand or writing sort manually:

#include <iostream>
#include <algorithm> // swap and sort lie here

using namespace std; // you don't want to use that in production, but it's OK in competitive programming

int main() {
  int a = 2, b = 3;
  swap(a, b);
  // a is now 3, b is now 2
 
  const int LEN = 6;
  int arr[LEN] = { 5, 2, 3, 1, 2, 4 };
  sort(
    arr, // pointer to the first element of range to sort
    arr + LEN // pointer to the first element not in the range to sort. No undefined behavior here, as long as one does not dereference that pointer and you don't try to get pointer to arr + 7, arr + 8...
  );
  // arr now is sorted: 1 2 2 3 4 5
  return 0;
}
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes I recently found that on the tutorial for a problem and I guessed that the arguments are the pointers [a,b). Submission link.

    Is there a way to sort in non-ascending order? I've read about a reverse method but that doesn't sounds very efficient to do.

    And tyvm for the information about the -Wall flag, it will be very useful for me. I'll try to use vectors instead of arrays for bounds checking but I don't really know when my numbers overflow because I read somewhere that in cpp integers are 16bits so I don't have the the limits very clear.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You may specify a third argument to sort — function which takes two arguments and returns true iff the first argument is strictly less than the second. You can also use lambda expressions or functors instead. There are some predefined functors, e.g.:

      sort(a, a + n, greater<int>());
// creates functor of type greater<int> and pass it as a third argument

      Vectors do not do bounds check by default. They do if you use v.at(x) instead of v[x] or compile with -D_GLIBCXX_DEBUG (which enables a hell of debug checks which can make program asymptotically worse). You can implement your own debug vector, though.

      int in C++ is not precisely defined (in contrast to Java). However, it's safe to assume that it's 32-bit on all modern judges which use GCC or Visual C++ (both 32 and 64 bit).

      → Reply