Beta

Pharaoh's pyramid of sum

10Rei_00
Description
Loading description...
Mathematics
Performance
View
AllIssues5QuestionsSuggestionsShow Resolved
  • Please sign in or sign up to leave a comment.
  • dfhwze Avatar

    As mentioned in an earlier comment, you should explain the concept a bit better. At least the job of a forerunner must be explained.

  • lachesism Avatar

    In random test, p is not always a prime number.

  • Mednoob Avatar

    The tests should run the ref sol first or copy the array first before executing user solution.

    • Mednoob Avatar

      What I meant is not flip the ref sol result with user sol in the assertion, because that will give Expected <ref sol> to equal <user sol> on error. That will be confusing for users of course.

      Run the ref sol first and put the ref sol result into a variable. And then, run the user sol and match it with the ref sol result variable.

    • Rei_00 Avatar

      Thanks! Me like klutz)
      Fixed it

      Issue marked resolved by Rei_00 13 months ago
  • Voile Avatar

    n - the count of levels in pyramid : 0 < n < 10^9

    Actual tests only go up to 2500000. Since any solution must be at least linear it's just impossible to not time out with this constraint.

    (If you're reducing this constraint, you should turn f into an actual array too: an array of 2500000 elements is certainly possible)

    Besides, the time taken for the tests are too volatile: even the author solution sometimes time out.

    • Rei_00 Avatar

      Thanks a lot for the comments!

      Now the answer is searched modulo a prime number.
      So I can remove restriction for k < 30 and sift out the naive solution without volatile test.
      And now the implementation of the module is an significant part of this kata

      Issue marked resolved by Rei_00 13 months ago
    • dfhwze Avatar

      My linear solution times out. What is the expected time complexity?

    • lachesism Avatar

      FYI, my O(nlog⁡p)O(n\log p) solution passes in 6 to 9 seconds.

      Multiplication and division of large integers is not O(1)O(1) so your solution is not really linear. :)

  • Voile Avatar

    Tests should not use assert_approx_equals: it is reserved for comparing floating point numbers where calculations are not exact.

    In this case the answer is exact, only the tests choose to use floating point numbers for some reasons.

  • TheLittlePixiesFriend Avatar

    I think this needs much clearer instructions.

    • What is a forerunner?
    • What is a dynasty?
    • What is the function for?