simp_pro's blog

HELP: Runtime error on test 2
By simp_pro, history, 2 years ago, In English

Problem link : https://mirror.codeforces.com/contest/1620/problem/C

Submission link : https://mirror.codeforces.com/contest/1620/submission/162394549

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

Comments Comments (7)
| Write comment?
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

a[i+1] out of bounds.

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

    This won't happen because before that there is an or statement i+1 == n, when this will be true the a[i+1] statement will never run.

    → Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Your code seems to have a lot of issues, I just fixed it for runtime errors.

Shadowed declaration string a; and auto mul = [&] (int a, int b).

Can be divide by 0 int t = x/prod[i];.

What if prod is empty prod.back() = 1;

Can be accessed out of bound forn(_, take[i])

Can be overflow int ans = A * b;

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for replying. This prod[i] cannot be zero. I fixed the prod.back.forn(_, take[i]) canot overflow

    I have handled overflow using the gfg method. Is not this corrrect?

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

      I am not reviewing your logic, I just pointing out some code that has a potential runtime error.

      I see you create vector here with size of vector "cnt" vi prod(sz(cnt));. If cnt is an empty vector, prod is also an empty vector.

      Example

      In this code forn(_, take[i]), I see that you increase i in the outter loop and try to access the element take[i] without checking the size which can be out of bound. A counter-example would be k = 0 -> vector take is empty -> take[i] will give an error.

      This is a submission link that I try to fix your runtime error Submission. The overflow still exists, I don't know what method you use to handled overflow but it seems not working

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        https://godbolt.org/z/7PvxGxKxK

        Notice that compiler generate just imul instruction.

        In c++ integer overflow (int ans = a * b) is UB. And because it is UB, compiler think "why b == 0 || ans / b == a would not be true?" and just not generate such instructions.

        Now its MLE:) 162639237

        → Reply