MTRICK - Editorial

editorial
, , , ,
21

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

22

@shangjingbo Its still giving WA, i dont know whats getting wrong!!!

23

thanks for pointing out the problem in my code.

24

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: http://www.codechef.com/viewsolution/3173590 (Java) , http://www.codechef.com/viewsolution/3173373 (Python) :slight_smile:

3 Likes
25

Yes, from the theoretical complexity, it should work. But, you should also consider the implementations. If your implementation uses the mod operations too many times, or some other reasons lead to a big constant in time complexity, it may get TLE.

26

Please calm down and look your codes line by line, sentence by sentence carefully. I think you can figure out the bugs. :slight_smile:

27

And I have tested your code locally. It even failed by the sample cases! After I fixed the problem, I found your code TLE. There are too many unnecessary mod operations. And also, you can read the editorial to find a faster solution. Only O(N log C) for each case.

28

Can You Plz See My Solution…Unable to find Any Mistake…http://www.codechef.com/viewsolution/3214607
THANKS…

29

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;
 }
30

@shangjingbo can you explain what is happening in this fast multiplication or give me some link

31

in the first approach what are the initial values of K[0] and D[0] ?

32

what is ‘y’ here in the expression “if((z =z+ y) >= c)”???

33

it was a typo , corrected now

34

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.

35

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
}
36

Initially, K[0] = 1 and D[0] = 0, because L0[i] = 1 * L[i] + 0

37

@sud210 we can use write b in binary, and prepare a, 2 * a, 4 * a, 8 * a, …, 2^k * a. 2^k <= b < 2^(k+1). Then, we can get the b * a in logb times of addition.

38

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

39

@shangjingbo why is it log©in the complexity? . shouldnt the multiplication step be log(B)?

40

Can anyone tell what is worong with that multiply_hack here??