Video Editorial - FEB17 - GERMANDE

editorial
, ,
21

Thank you bro.

22

Wow!
Please do this for Codeforces also, I need help in contests

1 Like
23

Thanks for the feedback @rishabh_vasani !
I will try to keep an eye on that too.

24

Really nice work @gkcs! Many times the official editorials are confusing and not understandable for beginners. This initiative of yours will surely help. Thanks a ton :slight_smile:

25

Thanks a lot for INTERVAL’s editorial!!! :slight_smile:

26

Your way of explaining is really nice, watched a couple of videos of yours about AI and they were great too. Thanks.

27

Thanks @ash_code!

28

Thanks @abdullah768! Will strive to stay that way :slight_smile:

29

Thanks @vijju123! :smiley:

1 Like
30

@gkcs
Can u help me solving MFREQ of Feb. Long challenge …I have seen your video but not getting answer when the condition is >=k.

31

Hi @adhish_kapoor,
In your code, you need to modify these statements:

left[i]=i-1; --> left[i]=left[i-1];

and

right[i]=i+1; --> right[i]=right[i+1];

If there are further doubts, I will be happy to help :slight_smile:

1 Like
32

Hey @gkcs, can you answer my query?

In the problem EUGENE and Big Number, you mentioned that, for cases where we overshoot N*len(a), “we create an array of size log(n * a)”. How did you find it?

Also, can you explain that binary exponentiation? It means that we are multiplying rem[I] with digit at binary[I]? Or is it multiplying rem[I] with full binary of n?

Because I am going by former method, and am getting wrong answer in test cases of kind-

1
1 3 2

1%2=1
11%2=1

So rem array has only 1. Then binary of 3 is 11. Going by what I understood, m getting-

(1x1+1x1)%2 = 2%2=0.

Also, How did you find that size of array should be Log(a x n) and not Log(n)? I was under impression that the size should be independent of length of A. Can you help me here? :slight_smile:

33

Hi @vijju123,

  1. The size of array is log(N*len(a)) because at each iteration, we are doubling the size of the result that we have.
    That means the size after X iterations is 2^X. The time we overshoot N x len(a) is when 2^X > N x len(a).

Hence we need X = CEIL [log(N x len(a))], iterations to hit or overshoot N x len(a). Thats why the array size will be CEIL [log(N x len(a))].

  1. Binary Exponentiation here would mean that at each binary[i] set to 1, we multiply the result with rem[i]. Result is initialized to 1 before all this.

So we have, result = 1.

Binary Array = [1, 1]

Remainders = 1%2 11%2 = [1, 1]

At index 0, we multiply result with 1 = 1. Then at index 1, we multiply result with 1 = 1. All indexes after this have binary value equal to zero, so we do nothing. That means we have final result as 1.

  1. The length of the array would depend on the length of a and the number of times we are appending it with itself. I should have been more clear with this. Every time you append a number with itself, it’s size doubles. So the initial size of the number will also matter. Be careful though, you need to go upto Log(length(a) x n), not log(a x n).

UPDATE:

For the other doubts,

  1. That code is for binary exponentiation. You can use any code which gives lets you raise a number to it’s N’th power in log(n) time there.
    A simpler code would have been:

int func(int base, int exponent, int mod) {
  if(exponent==0){
    return 1;
  }
  else {
    int halfResult=func(base, exponent/2, mod);
    if(base % 2 == 1){
      return (halfResult x halfResult) % mod;
    }
    else {
      return (((halfResult x halfResult) % mod) x base)%mod;
    }
  }
}

So we are raising 10 raised to an exponent.

  1. ‘powers’ stores all powers of 10 like 10^1, 10^2, 10^4, 10^8, etc… each with modulo mod. So the first time, the result will be result = result x 10^(length(A)) + result. Hence powers[0] is storing 10^(length(A)).

  2. At the point you mentioned, powers of 10 can be discarded. We have already used it to calculate results with N = 1, 2, 4, 8 etc…

Cheers on solving the problem! B-)

1 Like
34

Thanks a lot for the clarification dear!! I got my mistake. I was using ans = ans + (.binary exponentiation…)

And I really appreciate how you told us the trick to overcome it in exponential time. (I was also thinking in linear fashion…got TLE in ALL test cases initially.)

Thanks a ton dear!!

1 Like
35

Thanks @vijju123 :slight_smile:

1 Like
36

Hey dear! Can you tell me what you did in this line of code-

 private long power(final long[] powersOf10, final long exponent, final long m) {
        long result = 1;
        for (int i = 0; i < 64; i++) {
            if (((exponent >> i) & 1) != 0) {
                result = (powersOf10[i] * result) % m;
            }
        }
        return result;
    }

Here you compared if a position on a is 0 or 1 (in binary) and likewise did operations on result and returned it. Then you stored it in power[0]. Whats the purpose of this? I was under impression that we only had to use rem[I] = (rem[I-1] + rem[I-1]*powerTen[I-1])%m;

Also, that function takes parameter of a * length of a if I interpret correctly. I thought its n * len(a)

Your help would be appreciated!! :slight_smile:

EDIT- I solved the Q on hackerrank (FINALLY AFTER MORE THAN 30 HOURS OF GRUELSOME, CRUEL CODING)

I REALLY APPRECIATE ALL THE HELP YOU GAVE!!

I just have a small conceptual doubt in addition of doubts above. In your code, you defined answer as-

long answer=0

and-

answer = ((answer * powers[i]) m + result[i]) m;

My implementation like-

answer= (answer + rem[I]*b[I])%m; //consider this rem only if binary value of n here is 1.

Whats the role of power of tens here? That’s the last doubt, I promise. :slight_smile:

37

Thanks dear! Got it. :slight_smile:

1 Like