You are not logged in. Please login at www.codechef.com to post your questions!

×

MTRICK - Editorial

19
4

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

This question is marked "community wiki".

asked 13 Jan '14, 15:12

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446376
accept rate: 0%

edited 22 Apr '15, 17:34

admin's gravatar image

0★admin ♦♦
19.8k350498541

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

(13 Jan '14, 23:09) paramvi3★

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.

(14 Jan '14, 11:38) shangjingbo ♦♦3★

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

(14 Jan '14, 16:12) sud2103★

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

(14 Jan '14, 16:21) anonymousins2★

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

(15 Jan '14, 12:11) shangjingbo ♦♦3★

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

(15 Jan '14, 12:13) shangjingbo ♦♦3★

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

(18 Jan '14, 01:53) kcahdog3★
showing 5 of 7 show all

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

link

answered 14 Jan '14, 11:04

ashish1610's gravatar image

4★ashish1610
4981716
accept rate: 22%

edited 14 Jan '14, 11:05

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

link

answered 13 Jan '14, 15:18

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

3

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

(13 Jan '14, 18:54) shangjingbo ♦♦3★

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

answered 14 Jan '14, 15:25

randomizer's gravatar image

4★randomizer
1462311
accept rate: 11%

edited 14 Jan '14, 17:08

what is 'y' here in the expression "if((z =z+ y) >= c)"???

(14 Jan '14, 16:23) sonu125724351★

it was a typo , corrected now

(14 Jan '14, 17:10) randomizer4★

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

link

answered 13 Jan '14, 16:12

leetsachin's gravatar image

3★leetsachin
1
accept rate: 0%

1

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

(13 Jan '14, 18:55) shangjingbo ♦♦3★

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

(13 Jan '14, 22:57) leetsachin3★

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

(26 Jul '14, 18:57) johncarter3★

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

link

answered 13 Jan '14, 16:17

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

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.

(13 Jan '14, 18:57) shangjingbo ♦♦3★

http://ideone.com/dFm38p In this java code, i tried so many test cases, even with 10^18 but it gives Wa.. please tell where m getting wrong.

(13 Jan '14, 19:37) damn_me3★

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

(13 Jan '14, 19:39) shangjingbo ♦♦3★

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

(13 Jan '14, 19:40) shangjingbo ♦♦3★

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

(13 Jan '14, 19:50) damn_me3★

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

(13 Jan '14, 19:51) damn_me3★

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

(13 Jan '14, 22:51) shangjingbo ♦♦3★

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

(13 Jan '14, 23:13) damn_me3★

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

(14 Jan '14, 11:42) shangjingbo ♦♦3★

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.

(14 Jan '14, 12:09) shangjingbo ♦♦3★
showing 5 of 10 show all

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.

link

answered 13 Jan '14, 17:23

sagar1pant7's gravatar image

2★sagar1pant7
1624
accept rate: 0%

edited 13 Jan '14, 17:44

1

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.

(13 Jan '14, 19:00) shangjingbo ♦♦3★

thanks for pointing out the problem in my code.

(14 Jan '14, 07:17) sagar1pant72★

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

link

answered 13 Jan '14, 20:04

aq1_'s gravatar image

3★aq1_
112
accept rate: 0%

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

(13 Jan '14, 20:09) damn_me3★

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

link

answered 13 Jan '14, 22:28

picasso's gravatar image

2★picasso
1
accept rate: 0%

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

(13 Jan '14, 22:56) shangjingbo ♦♦3★

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

link

answered 14 Jan '14, 13:41

jakesahir's gravatar image

1★jakesahir
013
accept rate: 0%

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.

link

answered 14 Jan '14, 22:45

sambit1993's gravatar image

3★sambit1993
164
accept rate: 0%

edited 14 Jan '14, 22:46

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

answered 15 Jan '14, 11:04

anonymousins's gravatar image

2★anonymousins
29682122
accept rate: 11%

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

link

answered 15 Jan '14, 23:43

paramvi's gravatar image

3★paramvi
165
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,722
×966
×281
×51

question asked: 13 Jan '14, 15:12

question was seen: 11,463 times

last updated: 22 Apr '15, 17:34