The question is easy it just requires multiplication but I am getting TLE by using normal brute force method of multiplying. I read a solution : https://www.codechef.com/viewsolution/13366591 but couldn’t understand.
Can anyone explain this solution or algo?
Edit: Link to question: https://www.codechef.com/problems/IOPC17D
Assuming you already found the number of ways to distribute N elements… You should have some array A1, A2, A3, A4, …, AN with number of ways to distribute 1, 2, 3, 4, …, N elements respectively. So at this moment you only need to find a fast way to compute the multiplication of a range of this array.
A hard approach for that could be using some data structure like range-trees, or any equivalent technique like that (i.e. operate with sqrt intervals). But even this could be a quite slow for that number of cases.
So, an alternative way is using modular inverse, like in that solution which you linked. It uses cumulative multiplication (just the same as cumulative sum) to know in O(1) time, the multiplication between the first K <= N elements in the sequence. For example for K = 8 this array return the value of the multiplication between the first eight elements (A1A2A3A4A5A6A7A8) … but, modulated by M. This is (A1A2A3A4A5A6A7A8) % M.
If you want only the multiplication between A5 and A8, you need to divide previous result by (A1A2A3), this is (A1A2A3A4A5A6A7A8) / (A1A2A3) or using M, ((A1A2A3A4A5A6A7A8) M) / ((A1*A2*A3) M) using the same array A. This division will lead you to some wrong solutions due modulated values by M… for that reason you could use inverse modular and now rewrite the formula in this way: ((A1A2A3A4A5A6A7A8) M) / ((A1*A2*A3) M) = ((A1A2A3A4A5A6A7A8) M) * Modular_Inverse((A1*A2*A3) M)…
Greetings…
Thanks for the explanation.
No problem … if you do not know about Modular-Inverse operations, this could be impossible to understand … otherwise despite my answer is not totally clear, you should at least gets an idea of what is going on.
@mastana It is easy to see that for each town the number of ways of distributing is the number of ways to make the G(the number of gifts) using summation.
Ways to break down 4:
The number of ways to break down 4 is 5. This is also called partitioning.
There are many ways to find the answers for partitioning however I think the best way to pre-calculate would be using the recurrence relationship with the help of Pentagonal Number
why can’t i include images in my answer ??
Good point… it runs really faster than using DP.
Yes, DP would run in O(n^2) time, this should run in O(n*sqrt(n)) time.
Another possibility would be to store all ways to distribute directly in an array in your source code while making the code. However the creators were smart and reduced the source limit.