[Community Puzzle] Factorials of primes decomposition

Hello, i pass the 3 first test cases with succes, but none in the validator cases, can i have an idea about the validators, or only one of them.

1 Like

I think no one will give here any validator.

May I suggest you to : wait to pass all the test case before submitting and, if needed, ask help directly on #world or #fr or any other channel you want.

1 Like

I’m in a similar boat, but I’m passing all the test cases and for some reason I’m failing the last validator. I think my code is pretty robust to different combinations to numerators and denominators, but apparently not.

Sorry, I’m a bit of a codingame newbie, and don’t know what this means. Is that related to IRC? I googled #world and it linked back to this forum post.

yep ask help on IRC

The way you have to tackle this is to convert your value into factors of primes, take the largest one and use it as a factorial and then work down from there, note the lowest factorials are 5 : 120, 3 : 6 and 2 :2. I am having trouble using my Python program, the compiler seems to have run out of indentation lines to allocate because I have more than 150 lines of code. How can I ensure it has enough memory or space to complete?

Have you tried your script at home?

Yes it took a long time to develop, now I think it works perfectly(perhaps). Send me some test cases I will return the solutions. I will rewrite it later in C to get it to work on Codinggames.

120
→5#1
54
→3#3 2#-2
5020
→251#1 241#-1 83#-1 79#1 61#-1 59#1 31#-1 29#1 19#-1 17#1 13#-1 11#-1 5#4 3#6 2#3
1/40320
→7#-1 2#-3
96/143
→13#-1 7#1 5#1 3#3 2#5

I get correct answers immediately for 120, 54 and 96/143, because of the geometric nature of calculating factorials and my program requires its calculation locally the solution for 5020 is correct but takes over 2 minutes. I would not attempt 40320 in terms of time because to cover all possibilities the program needs to cover all primes and their factorials upto the value.

Thats the progress so far.

Maybe you are beginning your calculations from the wrong side.

you were so right, I have to generate the factorials after I know the max prime I am to use. Now I get the answer for 5020 immediately and 1/40320 in 3s.

Give me some more to answer without giving the answers, I will send the solns.

3 s for 40320? Look at the primes involved: they are are below 11.

Hello,
I am trying to solve this puzzle ( factorial of primes decomposition)
and in fact I wrote some code which solves all the tests, but fails to solve 2 of the validators
(power of factorial and fraction)
the equivalents ( as already said :slight_smile: ) are PASSED.

Any Idea how to investigate

I checked that my program gives the right solution to the examples given in this article and it does.
I don’t think there is any performance issue since the program is quite fast for the examples I did test.
but still these 2 validators failing. Any suggestion on how to find out what is failing ( I understand why validators do not give any traces… but it’s very frustrating for finding my “bug” without knowing the input data failing :frowning:
any help on how to proceed is welcome.

Power of factorial is something like (5!)^4.
Fraction involves negative exponents.

2 Likes

Thanks a lot,
that was exactly what I was looking for :slight_smile: I found 2 bugs in my code

and now it’s 100%Pass
great puzzle and definitely great help

2 Likes

Hi Nicola,
I’m in the same boat, passing all tests but failing validators 3 and 6.
Your comments are pertinent to these two cases but, keeping in mind the constraint that 0 < N, numerator, denominator < 20,000:

  • For powers of factorials, there aren’t that many below 20,000 so I tried all of them manually and all my attempts succeed, so I don’t know why the validator fails;
  • You mention that Fraction has negative elements but isn’t that a violation of the above constraint? Suppose, there is such violation, how should I format a negative result? Should I use parentheses, such as in -(3#2 4#1) ? If you only refer to negative exponents, then this is taken care of and the negative exponents appear properly. Also, the code passes all of your above examples as well.

There are no negative inputs. Answers may contain negative powers, though.

What is your output for
a. 120?
b. 576?
c. 96/25?
None of the above are validators.

In this puzzle, you’re supposed to convert any integer or fraction within the puzzle constraints as a product of prime factorials (with positive/negative powers). I’m not sure how you tried all “powers of factorials”. So I’m randomly selecting the above three numbers and see if your answer matches mine.

Thanks for replying so quickly!!
As so often happens, posting a question leads me straight to finding the problem. It is as if the bug is waiting for me to post something.
Thanks anyway!
Regarding your question as to how I tried all powers of factorials, I should have been more clear. The example test shows 36 = 3#2. Such example with a unique factor is what I meant. In fact, the number of powers of factorials with a unique factor is very limited. For instance, 4#3 = 13,824 and 5#2 = 14,400, so below 20,000, the exponents 3 and 2 are the limits for factors 4 and 5, respectively. Of course, with factor 2, we can go up to 2#14 but the total number of possibilities below 20,000 remains very low, hence why I was able to try out all of them.

1 Like