PROBLEM LINK:
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
