JVirak's blog

Different outputs on local machine and codeforces judge.
By JVirak, history, 8 years ago, In English

So I've been working through the A2OJ Div 2C ladder. For question 12 http://codeforces.net/problemset/problem/490/C my code seems to be running fine on my computer (at least for the three test cases given as examples) but it fails on the first test case (exactly the same as the first example) when I try to actually submit it http://codeforces.net/contest/490/submission/24563289.

It seems that for some reason it isn't picking up the answer in the loop (again, it does on my local machine) and is getting through the loop (which stops when an answer is found) and outputting "NO". Any help appreciated.

  • Vote: I like it
  • -18
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

There is array out of bound access it this line: A[i]=10*A[i]+(10*A[i-1]); when i == 0. This is undefined behaviour and probably it is the reason of different answers.

Try to change that line to something like this:

A[i]=10*A[i];
if (i > 0)
   A[i] += (10*A[i-1]);
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, I'm somewhat surprised that didn't break on my local machine, which I guess makes it soemthing to watch out for.

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

see fixed solution. 24563693

fixed part of code:

   A[0] = (s[0]-'0') % a; // 1. --->see  %a 
    for (ll i=1;i<n;i++){  // 2. --->see i = 1
        A[i] = s[i]-'0';
        A[i] = A[i] + (10 * A[i-1]); //3. --->see removed 10*A[i].      //computes the prefixes mod a
        A[i]=A[i]%a;
    }
    ll k=1;
    B[n-1]= (s[n-1]-'0')%b; // 4. ---> see %b
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks

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

      It now works!

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

        There more fast and less memory usage solution :24564535

        Note, there does not required long long.

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

          Thanks. I'll make a point to go through it properly soon.

          The last solution manages to get through it with the long longs changed to ints http://codeforces.net/contest/490/submission/24565799, I just default to long long out of habit.

          I figured "oh well I won't get an overflow error this way so I might as well default to it", do you think the memory constraints are harsh enough that it's a habit I should break?

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

            Do not think about memory optimization on CF, but for example in acm.timus.ru some problems have less than 4 MB memory.

            Do you solve your problem less than 2MB memory ??

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

              My solution used 13.7MB with ints, 21.5 MB with long longs. Definately over your 2 MB solution.

              → Reply