Блог пользователя JVirak

Автор JVirak, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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]);
»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It now works!

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        There more fast and less memory usage solution :24564535

        Note, there does not required long long.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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?

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 ??

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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