1000000007 is a prime, which makes calculating the final result much easier if you already know certain properties about your answer. It's to avoid that calculating the modulus will be a time consuming step in your solution. Why use a modulo at all? Because typing in more than 10 digits in an answer form can be really annoying.
Well, after a nice vacation with better weather than expected (but worse than hoped for) I implemented what I wrote before. However, it was trickier than I thought, and the code is also much longer than expected. But I did not write for brevity, but for ease of coding.
To illustrate the method, Lets say A = 50, B = 135, T = 12.
First T is transformed into a List of IntLists (= ArrayList<Integer>, but saves a lot of typing), and [2, 6] is one of these IntLists. This IntList is converted into a Frequencty table ('FT'), (a HashMap<Integer, Integer>, but again saves much typing).
So, for this case we have A, B and FT. What happens next depends very much on the length of these components. For A and B, this is simply the number of digits, and for FT, this is the sum of the values in the Map. An enum ('AandBandT') then characterizes the situation. In the case of the given values for A, B and FT it is CASE2: |A| = |FT| < |B|.
In the method 'permutationsCASE2' it is first calculated how many permutations of 'FT' are at least equal to A. Then, for lengths |A|+1 up to and including |B|-1, ones are added to FT'and all permutations are calculated. Finally, enough ones are added to FT to make its length equal to |B|, and the number of permutations are calculated that are at most B.
Well, that's it in essence. Special tricks were necessary when |A| = |B|, where only those permutations of FT must be calculated that are between A and B (inclusive).
Do not let the length of the code scare you off. It is Java7 code, I could have seriously shortened the code, but at the expense of making a complicated program even harder to read.
And is it all correct? I've done some testing for small values for A, B and T, and that was fine (well, after quite some repairing, that is).
Two questions remain: does anyone have a better (and hopefully shorter) solution? And is there a volunteer who wants to write a brute force method to test some bigger values for A, B and T?
Finally, I don't think there is much interest in this stuff. But if anyone has some questions or spotted some bugs, send them in.
Here's the code. All I can say to the author of this problem: you have probably a much more elegant solution, so I don't think I am spoiling this problem (I hope).
edit: there is a big bug in the 'productOfFactorials', but its repair is trivial and left to the reader.
There are three kinds of actuaries: those who can count, and those who can't.
Piet Souris wrote:Well, after a nice vacation with better weather than expected (but worse than hoped for) I implemented what I wrote before. However, it was trickier than I thought, and the code is also much longer than expected. But I did not write for brevity, but for ease of coding.
Either way, it's very impressive. I've been away from this thread for a while, so it'll probably take me a day or two to get back into the "groove", but have a cow for effort in the meantime.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here