Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @pepper,validated by @kitarotao,@SlowSnakPierre and @SkyWhait.

If you have any issues, feel free to ping them.

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @pepper,validated by @kitarotao,@SlowSnakPierre and @SkyWhait.

If you have any issues, feel free to ping them.

Hello there,

Maybe itâ€™s because I havenâ€™t solved it yet (I just have a trivial solution that works only for low numbers for now), but I donâ€™t see how itâ€™s related to the Note G?

If itâ€™s not a spoil of the solution, would someone care to explain how it is?

Thanks

Hi @Senua *Note G* is a computer algorithm written by *Ada Lovelace* that was designed to calculate Bernoulli numbers using the hypothetical analytical engine. And it is related in some way with a task. However research is the most important part of this puzzle in my view, so try figure it out

Here you can find details: Wikipedia Note G

Although my solution passed all the tests, I feel itâ€™s not the right one - itâ€™s more of a hack. Iâ€™m waiting for someone to share the correct solution. So far, no one has posted it yet.

Hello @Senua ,

I have solved this puzzle, and Note G did not help me at all.

Looking back at my code, it actually computes some values that are mentioned in the note, but only relies on:

- recursion (as mentioned in the tags)
- big integers (64-bits integers are not big enough for my approach)
- three well-known formulas/algorithms on integers (things I have already used several times on CodinGame).

And I also use a hack at the end of my code. If the modulus were a prime number (as it usually is in this kind of puzzle), this hack would not be needed and the statement would be less misleading (I canâ€™t help thinking about using double-precision floating-point numbers when I see 2^53).

I still timeout in the last IDE test in PHP, despite I donâ€™t calculate n^n^n, but use a formula with just n iterations, and in total I use O(n^2) arithmethic operations. But these arithmethic operations are slow because I had to use the quite slow bcmath library for arbitrary precision and a custom arbitrary precision BCFraction class implementation (as php has no built-in support for fractions, nor arbitrary precision fractions). I also use memoization, not repeating calculations for some required partial results.

I am not sure what additional math idea I miss here. I checked the wikipedia page of Note G, which directed me to the wiki page of Bâ€¦ number, which directed me to Fâ€¦ formula and of course there is the algorithm to calculate the Bâ€¦ coefficients.

EDIT: after replacing an accidental bcpow() call with bcpowmod() and some further optimisations my code runs faster, but I still need 29 sec locally for n=513, so only a code with hardcoded lookup values passes everything onlineâ€¦

EDIT2: After solving this with the above caveat, I checked the example solution on contribution and it is very underwhelming. Only works because of built-in fast arbitrary precision fraction libraryâ€¦ Does not even apply modulo on partial results, only on the huge end resultâ€¦

1 Like