Video Editorial - FEB17 - GERMANDE

Hi Everyone!

I have made two video editorials for the Feb Long Challenge. Its on ‘Gerrymander’ and ‘Most Frequent Element’.

FEB17 - GERMANDE

FEB17 - MFREQ

FEB17 - EUGENE

FEB17 - INTERVAL

alt text

I am in the process of making more FEB17 editorials!

I would love to hear your feedback and suggestions. :slight_smile:

EDIT: Uploaded the tutorial for Interval now!

19 Likes

Thanks for giving your time and making the video editorial. Can you also do the editorial videos on problems INTERVAL and DISTNUM3. Thanks in advance.

2 Likes

It’s very nice and unique initiative. Just moving on. And keep uploading such a nice editorial.

Nice man . keep up the good work! @gkcs

@gkcs, Great work!! It would be awesome if you could do this for every Long Contest, CookOff and Lunchtime from now on. If it is not possible to do it for all the three types of contests, then Long Contest at least would really help a lot of people. Again, awesome work, keep at it!!

Great!!! Please make one for chefyoda and interval also.

I have been watching your videos and they are really helpful. It would be too good if you post some tutorials on Dynamic Programming techniques, through questions. This would be too helpful.

Thanks!! :slight_smile:

1 Like

CodeChef Long Challenge - FEB17 - MFREQ - YouTube.

CodeChef Long Challenge - FEB17 - GERMANDE - YouTube.

thanks for this.

please upload more video editorial specialy problem releated with advanced data structure and algo. i sometime couldnot understand the editorial. and give up, if there is video editorial it will really helps.

Hi @gkcs … Nice job Gaurav. Thank you so much. I would really be happy if you could make a video on how to solve challenge problems. Yes, I have already come across your page on how to solve them ( I actually Book marked it :smiley: ). Maybe after the March Long, you could take up the same problem and walk us through. It would really be nice to see the thought process of people when it comes to solving these kind of problems (Disclaimer : I am total clueless of how to solve them. I can only manage 2 or 3 points at max.) Not only @gkcs, it would be great if many people can share their views. It would help a lot of people.
Thanks a lot…!!

2 Likes

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

1 Like

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:

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

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

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:

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

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:

Hi @only4
I am working on those two problems especially! To be honest, I can’t find a clear explanation on the board for these problems, so it will take some time. Will get the video out as soon as possible though.

3 Likes

Working on it INTERVAL right now :smiley:

1 Like

Trying my best. Balancing between work and editorials is quite stressful.
But I have a long weekend ahead, so I should be able to roll out some videos soon :slight_smile:

1 Like