MTRICK - Editorial

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).

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

@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.

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

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

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

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

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

thanks for pointing out the problem in my code.

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.

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

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.

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

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

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

it was a typo , corrected now

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

@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.

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

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