iamstg's blog

By iamstg, history, 8 years ago, In English

I was submitting the solution for Round #362 Div2 Problem E :

http://codeforces.com/contest/697/problem/E

I got WA on Test#4 on this submission : http://codeforces.com/contest/697/submission/19150824 I had typecasted every possible places where I felt overflow could occur with long long. I submitted many times but it gave wrong answer with typecast.

Then I submitted using 1ll in multiplication instead of typecast in this submission and it got accepted: http://codeforces.com/contest/697/submission/19150943

My question is why does typecasting not work and what is the difference between typecasting and 1ll?? Also when to use which because many of the solutions I coded before used typecasts and it worked well on various judges including Codeforces until I encountered this case for the first time.

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

»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Auto comment: topic has been updated by iamstg (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You're only typecasting expressions that have been of type long long already (see http://codeforces.com/contest/697/submission/19151715). You don't need any of the casts.

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

    Thanks,majk but why did typecasting provide WA.. I just added it due to extra safety..does unnecessary typecasting have side effects??

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it

      No, it doesn't. It took me a while to spot the crucial difference. * and % have the same priority and associativity. This means that ((x%M) * (z*z)%M)%M is equivalent to (((x%M) * (z*z))%M)%M. In other words, you calculate x%M and then multiply it with z*z. Since both x and z can be up to 10^9, the result is up to 10^27, hence, overflow occurs. Proper parentheses prevented that in Your second submission.

      Keep in mind that the priority only affects the result in case of overflow, mathematically, the result is the same.