CodeChef Long Challenge - FEB17 - MFREQ - YouTube.
CodeChef Long Challenge - FEB17 - GERMANDE - YouTube.
thanks for this.
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 ). 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…!!
Wow!
Please do this for Codeforces also, I need help in contests
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
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?
Hi @vijju123,
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))].
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.
UPDATE:
For the other doubts,
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.
‘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)).
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-)
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!!
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.
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.
Working on it INTERVAL right now
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
Thanks Bansal
Thanks Ashish!
Thanks @brijwasi1995 !
The next editorial will involve DP, and I am going into detail explaining when we should use it. Should be able to post by tonight
Nice job buddy!!!
Hi @foehadsidhu
There are some videos I have made on data structures which in which I picked a SPOJ or Codeforces problem as an example. You could have a look at this playlist:
Cheers
Thanks a ton, @chari407 !
A video on challenge problems will be fun to make. Should be able to get it done soon!