Igor.Ivanich's blog

USACO: Humble Numbers
By Igor.Ivanich, 15 years ago, In English

Hi everyone,

Well the problem which I'm going to discuss here is from USACO Chapter 3.

The problem description is given below:

For a given set of K prime numbers S = {p1, p2, ..., pK}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p1, p1p2, p1p1, and p1p2p3 (among others). This is the set of `humble numbers' for the input set S. Note: The number 1 is explicitly declared not to be a humble number.

Your job is to find the Nth humble number for a given set S. Long integers (signed 32-bit) will be adequate for all solutions.

K and N, 1 <= K <=100 and 1 <= N <= 100,000.

 I'm getting TLE due to running O(N ^ 2 * K) algorithm (Simply I'm building the humble number sequence
starting at 1 then at each iteration find the minimum number which is bigger than the last found humble number).

Am i missing something? Or is there a better algorithm for solving this problem?


Thanks in advance.


Igor.
  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
15 years ago, hide # |
 
Vote: I like it -10 Vote: I do not like it
Solutions.
→ Reply
»
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Use priority queue to optimise your solution.
→ Reply
  • »
    »
    15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    Thanks for the reply, Could u please explain more?
    → Reply
    • »
      »
      »
      15 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      Instead of searching minimum in O(N) time each step you can use priority queue (in C++ STL it is std::priority_queue, in Pascal it is not very hard to implement it) to search minimum in O(1) time and remove some element in O(lg(N)) time. The rest of solution will be almost the same as yours, I guess. If you don't know what the priority queue is.. use google for reference :)
      → Reply
      • »
        »
        »
        »
        15 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        I've tried the way u said but getting TLE on test 8
        My solution is here: http://pastebin.com/N5aFRt1g

        Am I doing right or miss something?


        → Reply
        • »
          »
          »
          »
          »
          15 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it
          Set is too slow. It is better to use priority_queue. Also, there is no need to put some element in the set/queue if it certainly will not be used. It might get AC if judge server is fast enough. Else try approach from random.johnnyh's link. O(N*K) will certainly pass.
          → Reply
»
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
http://hi.baidu.com/leokan/blog/item/1867a4ec32d4052363d09fe0.html

The algorithm described at the bottom of this link runs in O(K * N) time, and I think it can be further improved to O(NlogK) with a priority queue.
→ Reply