• 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
  • Knute Snortum
Sheriffs:
  • Liutauras Vilda
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Joe Ess
  • salvin francis
  • fred rosenberger

Problem: Digit Products

 
Bartender
Posts: 10777
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • 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: 11185
244
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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: 10777
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • 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: 3674
151
  • Mark post as helpful
  • send pies
  • 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: 10777
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • 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
  • Quote
  • Report post to moderator
 
Piet Souris
Bartender
Posts: 3674
151
  • Mark post as helpful
  • send pies
  • 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: 11185
244
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I gave him a cow for you, Piet.
 
Piet Souris
Bartender
Posts: 3674
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you, Stephan.
 
Tak Ming Laio
Ranch Hand
Posts: 40
1
  • Mark post as helpful
  • send pies
  • 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.
 
Let's get him boys! We'll make him read this tiny ad!
Sauce Labs - World's Largest Continuous Testing Cloud for Websites and Mobile Apps
https://coderanch.com/t/722574/Sauce-Labs-World-Largest-Continuous
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!