Mehedi33's blog

Need some hints for LightOj 1189 — Sum of Factorials

By Mehedi33, 12 years ago, In English

http://lightoj.com/volume_showproblem.php?problem=1189

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
12 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

the input size if small (the largest factorial you will need is 20!) so here you can generate all the possible factorials and use bitmasking (or recursion) to pre-calculate all possible values and cache them ... then for every case you just output the answer

→ Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I pre-calculate all the value upto 20. But now i cant understand how can i find my desired number .

    I have no idea about bitmasking. Is there any other way ?

    → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Use brute-force. For each number there are two cases — to use or not to use :)

      → Reply
      • »
        »
        »
        »
        12 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        If i use brute-force, at some stage summation of fact(num) may exceed my desired n , at that case i may avoid that fact(num) . But can i surely say that at any stage summation of fact(num) will be equal to my desired n ?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          I think that this approach will result in TLE since the limit is 0.5 :) I think it is better to read Caraz96's idea and ask if you misunderstood something in it.

          → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +3 Vote: I do not like it

      It is possible to use a greedy approach: since fact(n) > fact(0)+fact(1)+...+fact(n-1) (this is true for each n > 2) you can iterate from the greatest factorial(20!) to the smallest one, if fact[i] is less than or equal to N you must take it, decrease N by fact[i] and proceed with the next factorial. At the end, if N is 0 you found the solution, otherwise it is impossible to obtain N adding factorials.

      → Reply