MTRICK - Editorial

editorial
, , ,
8

What I did was this. For reverse I kept count of no.of reverse operations. If this count is odd, your ans will be the last element of array & if even it will be the first element. I stored this element in ans_to_print variable. Since we didn’t need to manipulate it further. I deleted the element from the array. So, my trick of last for odd & first for even worked better. Now, for add & multiply, I kept two variable add & mult. As we know if we add some number to another number & than multiply with some another number like (10+50)*20, it will be 10*20 + 50*20. So picking a trick from this I modified add & mult as below:

if(ch=='A')
   add=(add+a)%c;
else if(ch=='M')
   mult=(mult*b)%c;
   add=(add*b)%c;   /// This helped in maintaining the order of addition & multiplication.

So, in the end ans would simply be

ans_to_print=(ans_to_print*mult+add)%c

Link to my codes: CodeChef: Practical coding for everyone (Java) , CodeChef: Practical coding for everyone (Python) :slight_smile:

4 Likes
9

Can You Plz See My Solution…Unable to find Any Mistake…CodeChef: Practical coding for everyone
THANKS…

10

A better/time effective approach to (a*b)%c could be

long long int mult(long long int a, long long int b, long long int c)
{
   a = a % c;
   b = b % c;
   long long int z = 0;
   for (1; a; a >>= 1){
                      if(a & 1)
                      if((z =z+ b) >= c)
                         z = z- c;
                      if((b = 2 * b) >= c)
             b =b- c;
  }
 return z;
 }
1 Like
11

Why my this solution:
http://www.codechef.com/viewsolution/3206481
was giving nzec . All numbers in the listwere integers so i was just making a array out of those numbers while just making a simple list was working fine.

12

Can u please explain what this function does 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
}
13

can anyone explain me why this O(n) solution is giving TLE ??

14

Yes, brute force is feasible for this problem. But we can learn better algorithms from the editorial :stuck_out_tongue:

3 Likes
15

Have you tried to replace your multiply_hack with the multiple function mentioned in the editorial?

1 Like
16

It looks like “void add(int s)” has a bug. You should have one more mod after the +. Try to find such tiny bugs around, and thus your debug skills will be improved fast.

17

The multiplication operator in your code, although mod c, may exceed unsigned long long. Please read the editorial to find the tricky way to get the product withou any exceeding. Thanks.

1 Like
18

In this java code, i tried so many test cases, even with 10^18 but it gives Wa… please tell where m getting wrong.

19

oh, you need to mod all L[i] by c. Try System.out.print((list[i] % c)+ " ");.

20

the mod c should be applied even if the all operations are “reverse”

21

dFm38p - Online IDE & Debugging Tool - Ideone.com This code gives WA (if i use xor for reversing), and TLE if i do it using loop(done in comments).

22

However, i saw various solutions in which xor was used, but then they are not taking mod after reversing, is it such??

23

@aq1_ If you’ll see addmod function, you have done x-m+y, but if even this “x-m+y” is greater than c, we again need to take the mod. You function should have the recursive call which returns(x+y+m) when x+y-m<0.

24

oh, in your reverse, “int to=num” should be “int to=num - 1” I think. You can mod them before output.

25

“multiplicativeConstant = (multiplicativeConstant * bModC) % C;” may exceed the unsigned long long when multiplication, please look into the editorial to find the solution to avoid exceeding.

26

Thanks, although got the TLE. I have to use the continuous multiplication like mentioned in editorial.

27

i was wondering why O(n^2) was giving TLE because N<=1000 and time limit was 2sec. Wasn’t it enough ??