fuck_rating's blog

Strange Behavior on atcoder
By fuck_rating, history, 9 months ago, In English

i was solving a problem on atcoder and my submission is giving WA

although my solution is giving correct output on my computer. strange thing is that it is giving wrong answer even on sample test cases which are surely correct. can anyone mention the reason or any issue from my side

submission link — https://atcoder.jp/contests/abc194/submissions/51686326

input tc link — https://www.dropbox.com/sh/nx3tnilzqz7df8a/AADjf_qIms_cFXcQMAhArzKma/ABC194/E/in?dl=0

correct output link — https://www.dropbox.com/sh/nx3tnilzqz7df8a/AABQc4d2ofLTo0bmoMNq75C5a/ABC194/E/out?dl=0

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

»
9 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Happens with me on codeforces when I access illegal indexes. Recheck the array indices which you are accessing.

Edit - You are doing mp[a[i-m-1]]--; in your for loop. What happens when i is less than m-1 ? You are accessing negative indices. Your compiler won't give error, but online judges will. You need to correct that.

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

    Not possible as I is starting from m-1 and going till n here m<=n so no such issue It could have gave re instead of wa if it has something with wrong indexing

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      $$$i = m - 1$$$

      $$$a[i - m - 1]$$$

      $$$= a[m - 1 - m - 1]$$$

      $$$= a[- 1 - 1]$$$

      $$$= a[-2]$$$

      negative index

      Also, with UB, you won't know if it'll give you WA or RE or something else

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

Out of bound index leads to undefined behaviour. In your code, i — m — 1 is obviously not correct and could potentially get negative index. Tip: enable address sanitizer to detect such issue when compile.

→ Reply