Hi, beginner here, so please don’t mind if my doubts are naive. I was doing this problem and got stuck on it since a couple of days. https://www.codechef.com/problems/CHMOD
I looked at the editorial too but I failed to understand what it meant. Tried debugging the code with few test cases, but still couldn’t understand it well. Would be really grateful if someone explained it in easy and simple manner along with the time complexity. Thank you.
l1 5 // Size of array you want. Here it is 5 , so 5 is the size of array
l2 1 2 3 4 5 // These are the 5 elements which you have to enter.
l3 4 // No. of games to be played of no. of problems to be evaluated
l4 1 2 3 // game # 1
l5 2 3 4 // game # 2
l6 1 1 1 // game # 3
l7 1 5 1000000 game # 4
**Every line of game consists of 3 things for eg. lets take line no.4 or l4 **
1 2 3
1= left integer or li
2= middle integer or mi
3= right integer or ri
All you have to do here is write a code to implement Modulus Multiplication
The formula for 3 integers is (A * B) mod C = (A mod C * B mod C) mod C
Link to MOD multiplication https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-multiplication
Hope this helped you. Comment if you have any other problem.
I had solved it on paper but my rp<60 so could’nt upload image
Could you please elaborate on this statement “pre-calculation of cumulative frequencies” ? It’s in the editorial.