WA for Magic trick

general
, ,
1

Seeing a bit of cold response on the editorial page i am posting this as a question.

Problem:::[Magic trick][1]

Here’s my EDIT:


[2] and its giving a WA and i am unable to figure it out why...
Please help...





  [1]: http://www.codechef.com/problems/MTRICK
  [2]: http://www.codechef.com/viewsolution/3256318
2

You will get overflow here M[i+1]=pow(b,mul);
b can be as large as 10^18 and even raising it a power of 2 will cause long long (int64_t) to overflow

3

so any suggestions?

4

There are only 2 ways to solve the integer overflow problem:

  1. Simplest one. Use a language like Python or Java with inbuilt support for large numbers.

  2. Use the fast multiply method mentioned in the editorial.

Also i feel there is no need for you to reverse the array. Just maintain a start and end pointer to know the range in which you have to operate. This works because you only have to update elements from i…N so the elements from 1…i-1 have already been evaluated and no further operation will affect them in anyway as all operations are done on elements in the range i…N.This is also described in the editorial.

1 Like
5

Still getting wa :frowning: http://www.codechef.com/viewsolution/3256318 changed the code

6

got an AC :)very important to use that method :)thanks

7

but i am not able to get the working of this function. It would be really appreciable if you explain it in detail…

long long multiple(long long a, long long b, long long c) // a * b % c
{
    if (b == 0) {
        return 0
    }
    long long ret = multiple(a, b >> 1, c)
    ret = (ret + ret) % c
    if (b & 1) {
        ret = (ret + a) % c
    }
    return ret
}
8

@anonymousins I have tried to explain fast multiplication here. I think you will understand the function after reading it.