vishva1994's blog

Codechef April Challenge (HELP WATSON ESCAPE) — 3rd test case
By vishva1994, history, 9 years ago, In English

My submitted solution: https://www.codechef.com/viewsolution/9929014 I referred to the problem setters solution while solving for fast exponentiation function . The first two test cases passed . The last one — wrong answer (expected TLE) . Where am i going wrong ??

updated my solution to this but still same error:: https://www.codechef.com/viewsolution/9930909

Changed FMOD function to normal % and got AC . Does anyone know why???

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

with regards to your matrix exponentiation function.

ans = (ans * a)%1000000007;

#define M 1000000007
ans = ((ans%M)*(a%M))%M;

using Modular Arithmetic.

you missed this !

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

    changed my code to this:
    https://www.codechef.com/viewsolution/9930909 still same error

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

      i didn't read your main() . fmod(a,b) will cast a and b into floating point types and the return type is also floating point . This i think will result in loss of precision and maybe the reason why something incorrect was returned . I am not completely sure.

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

Remove fmod AC

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

    It worked . Do you know why ??

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

      Try this

      ll a=1234567899;
cout<<(a%1000000007)<<" "<<fmod(a,1000000007);

      It's maybe because of precision issue.

      The reason that you have used fmod might be because you might have got compilation error. If that was the case use LL for long long constants.

      → Reply