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.
Below are the links to the solution:-
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.
Thank You!!
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.
Check Discussions on Perfect divisors | Basics of Combinatorics & Math Practice Problems | HackerEarth for an explanation why their solutions are wrong.
Great work bro. Please keep on making video tutorials for HackerEarth rated monthly challenges as HackerEarth problem videos are not available on YouTube.Thanks|
Thank you so much for making time to look into the issue.
Yes, my answer is the same for test case 4.
So, my approach was correct and so the implementation. Thank you 
Can you provide me the input data for the test case 4?
It will be. Thanks
No suman , u read i think question wrong …u think given x is prime right ? …but that’s not the case-
may be input is
2 34
4 34
so we have to convert 4 = 22
2 34
2 34*2 = > 2 68
after that do as u wanna do , also while increasing the frequency of each factor
count[temp] = count[temp] + c * y; this is wrong
u have to mod also
count[temp] = (count[temp] + c * y)%mod
after that your answer will be correct.
see my code - " ujh7XX - Online C++0x Compiler & Debugging Tool - Ideone.com "
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.
I can’t upload the file here, but I believe you can check the input file from details of your submission.
this is for me ?
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.
am i right or wrong tell me -
ab % m = a(b%m )%m if m is prime
$$a^b\mod p\equiv a^{b\mod p-1} \mod p$$ because of Fermat’s Little Theorem.
It appears that LaTeX doesn’t work here. Text version:
ab % p = ab % (p-1) % p
oh yes … u r correct
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.
Yes, your solution is correct.
Thanks for your solution of vertex set, I was not able to think how can I use dp approach in the tree.