MTRICK - Editorial

PROBLEM LINK:

Practice
Contest

Author: Nikhil Garg
Tester: Gerald Agapov
Editorialist: Jingbo Shang

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Programming Language, Simple Math.

PROBLEM:

Perform the “Ancient Algorithm” described in the problem. And output the results in all steps. Remember that all numbers and operations are modulo by C.

EXPLANATION:

As same as the title of the problem “Magic Trick”, there are some math and programming tricks in this problem.

Denote the array after i-th loop as Li[].

The first trick is a math trick – we can maintain a slope Ki and a intercept Di, such that all current numbers in Li[] equals to the original numbers Ki * L[] + Di. For each operation, we can update the K and D as the following rules:

if operation == 'R' {
     K[i + 1] = K[i]
     D[i + 1] = D[i]
} else if operation == 'A' {
     K[i + 1] = K[i]
     D[i + 1] = D[i] + A
} else if operation == 'M' {
     K[i + 1] = K[i] * B
     D[i + 1] = D[i] * B
}

The second trick is a programming trick – at any time, Li[] is an interval of L[] (may reversed). Therefore, we can record the begin, end, and direction each time such that the Li[i] equals to the L[begin]. That is,

begin = 1
end = N
direction = 1
for i = 1 to N do {
    if operation == 'R' {
        swap(begin, end)
        direction = -direction
    }
    UPDATE K and D
    print L[begin] * K + D
    begin = begin + direction
}

Beside these magic tricks, there is also a common trick of long long exceeding. That is, because C is as large as 10^18, the multiple operation may exceed the type of long long. We can use a fast multiple, similar to fast power, to solve this exceeding problem without big integer in O(logC) time.

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
}

For explanation about fast multiplication, please refer to this

In summary, we can solve this problem in O(N log C) for each test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here and here

14 Likes

Just my 2 cents:

  • constraints were so, that you can implement reverse operation in timelimit
  • in Java you can use BigInteger (this time, but I have to learn that trick with long long)

My Java solution (accepted in last minute of the contest).

1 Like

Why my solution gives wrong answer?
The algorithm is same, only i am doing modulo exponent.
http://www.codechef.com/viewsolution/3251026

Whats the mistake in these codehttp://www.codechef.com/viewsolution/3224368 , http://www.codechef.com/viewsolution/3217878.
(It uses the last method given in the editorial).

What if we use two variables instead of two arrays to store the result of the multiplication and addition operation.My solution uses the same thinking.
http://www.codechef.com/viewsolution/3248148
But the solution produces WA.Can someone aid me to bring out the mistake in it.

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

3 Likes

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

1 Like

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.

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


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

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

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

http://ideone.com/dFm38p 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??

Can you please check my solution?Unable to find the mistake.
Thanks in advance.
http://www.codechef.com/viewsolution/3240662

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

can you please check the solution…unable to find mistake…
http://www.codechef.com/viewsolution/3246455

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.