Hello Codechef Community, Here are the video editorials for today’s held HackerEarth February Easy’ 21. Each and every problem along with their solutions are explained in detail.
Please do watch videos, like, comment, and subscribe to this channel. Likewise, Videos will be uploaded for most of the contest’s editorial. Any suggestions are welcome, do comment in this blog post.
For the Perfect divisors problem, I solved using formula. But only 3 out of 100 test cases are AC. I couldn’t find the bug even after trying for 2 hours. I watched the video editorial, it’s the same approach I used. Could you kindly find where I am making mistake.
Here’s my code
Thanks in advance.
It is very likely your solution is correct since you didn’t messed it up as they did. Particularly you can check your answer to test case 4. If it is 451217967 then your are correct.
The editorial solution (hence the judge) and the above solution are incorrect because in their calculation of exponent, they modulo 1e9+7 (i.e. used the modulo addition function), which will result completely wrong answer for this problem.
Great work bro. Please keep on making video tutorials for HackerEarth rated monthly challenges as HackerEarth problem videos are not available on YouTube.Thanks|
You made exactly the same mistake the editorial make.
Take mod=11 and the input
2
2 10
2 10
After modulo 11, you should get the WRONG exponent 9.
So your code will provide 0 (1+2^2+…+2^8 mod 11 =0) while correct answer is 1 (1+2^2+…+2^20 mod 11=1).
Check the link I provided above for an explanation.
Yes, because the editorial hence the judge for that problem is wrong. The only reason you got correct answer is that you made the same mistake, which is modulo 1e9+7 in the exponent.
I understood what you want to say.
Yes, you are absolutely correct, we may lose exponents if we are taking modulo with 1e9+7.
The approach of this question is correct if we reduce constraints or take modulo with a large prime number(>10^12).
I think there is some flaw in their checker!
Thanks for pointing it out otherwise no one would have noticed it.
Yup , u r correct ,in morning after i got 3 marks and just see some other solution in which by adding exponent he did mod , i think obviously it is correct and this is my mistake …but now i got it thanks.
So, my solution is correct, right?
I am aware of Fermat’s little theorem. But I didn’t reduce the exponents by taking modulo. As mentioned by @atzhh, I got the expected answer for 4th test case.
No, I didn’t consider X as prime. If I did, I would have not factored na. I factored X as product of primes raised to some powers. Then, for each power, I multiplied it with Y and added the same to global count array. Finally, calculated the result by implementing formula.