• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Problem: Digit Products

 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:But I meant calculating permutations...


Ah, gotcha. Personally, I think I'd just use BIs and then report the way I was told to. Saves a lot of faffing around.

However, I was interested in that 'modulo (10^9 + 7)', and wondered if it might be a clue to the solution. Otherwise, why 10^9 + 7?

Well, I hope I have time to implement what I wrote about, since from tomorrow I'll be on holidays for a week, without internet


Have a great time either way,

Winston
 
Saloon Keeper
Posts: 15491
363
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:1000000007 is a prime, which makes calculating the final result much easier if you already know certain properties about your answer.


Ah. Thanks Stephan. Still getting to grips with modular arithmetic (not least because I find the notation a bit odd); but even so, I should have thought about the possibility of a prime.

Winston
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.

Winston
 
Ranch Hand
Posts: 40
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Tak Ming Laio,

thank you for this program! I did some checks, and with A = 50, B = 100.000.000 and K = 128, both programs agreed on 4.257. So, I guess it is fine.

You earned a cow, but unfortunately I have no clue how to give one. So, patience!
 
Stephan van Hulst
Saloon Keeper
Posts: 15491
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I gave him a cow for you, Piet.
 
Piet Souris
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you, Stephan.
 
Tak Ming Laio
Ranch Hand
Posts: 40
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you Stephan and Piet, but for very large interval [A,B], this is not a fast solution. I will try another solution when have time.
 
grapes are vegan food pellets. Eat this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic