We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #109: Darts
  4. Discussions

Project Euler #109: Darts

Sort by

recency

|

8 Discussions

|

  • nohexa1773
     + 0 comments

    Ah, Project Euler #109: Darts! This intriguing problem delves into the surprisingly vast possibilities of checkout throws in the classic game. With the unique "doubles out" rule adding a strategic twist, the number of potential three-dart combinations quickly skyrockets. Cracking this challenge requires clever deduction and efficient search algorithms, rewarding the solver with a deep appreciation for the dartboard's arithmetic elegance. How to play darts Prepare for a satisfying brain-teaser that blends logic and probability into a fun, mathematical adventure!

  • phbnhien
     + 1 comment

    "There are exactly 14 distinct ways to checkout on a score of 6"... There seems to be more. For example:

    s1 s1 s1 s1 d1
s1 s1 s2 d1 
s2 s1 s1 d1
s1 s2 s1 d1
s1 s1 d1 d1
d1 s1 s1 d1
s1 d1 s1 d1

    These are not included in the list. Which rules crossed them out?

    • ptbudd
       + 0 comments

      Only three darts can be thrown in a turn

  • kitchent
     + 1 comment

    The infinite number of darts are not very friendly. I suppose dynamic programming is not applicable for larger input. My DP approach got TLE #7, #8 and MemoryError from #9 onwards. If you're interested, here is part of my code snippet:

    mod = int(1e9) + 9
darts = [1] + [0] * N
for n in xrange(N+1):
    for m in xrange(1, 61):
        if n + m > N:
            break
        darts[n+m] += darts[n] * one_dart[m]
        darts[n+m] %= mod

    EDIT: Learn about linear recurrence relation matrix (of size ), and then think about constructing the matrix (of size ) that can be feeded to a cumulative vector. Start with the vector [1] + [0] * 60. Perform matrix exponentiation (divide and conquer, very straightforward) that is . And finally, pick the double ending elements from the final vector of . Problem 114 has a relevant approach.

    • padeff
       + 2 comments

      I am curious, I believed it was A size 60 , and the formula was something like : sum(A**i,i=0..n/60)As([1]+[0]*59, As being the working checkout. I wouldbe interested to get your ideas ont he topic. all my best

      • kitchent
         + 0 comments

        It's been months ago so my memory is vague. If I remember correctly, was a crucial number. The tricky part was that we are concerned about the cumulative target score instead of just the target score. So everything in the matrix will be cumulative, and at the same time we also want access to the non-cumulative contribution from any entry. Otherwise, we would fail to add them up and tracking the cumulative results at the same time.

        How do we find when all we have is and ? You get the idea. We would not have needed a -th row if we don't want the non-cumulative results.

        For me, the first row of the recurrence relation matrix is used for:

        1. Adding up all newly obtained possibilities (which are cumulative, from column to ) contributed by those from the lower scores, based on the dart score rule.

        2. Removing all duplicate cumulative terms (using from column to ) from (1). It is already cumulative, and we don't want more duplicates.

        3. The cumulative step to add the immediately previous result. It ensures all scores lower than this are also included, and is the reason why we need (2).

        Use assignment carefully when you build the matrix. When you think add something, or remove something, you want to add or subtract (not necessarily ), instead of messing the work of other entries up with .

        I have modified this comment for a several times, only to find out that the problem is tricky enough that I was unable to understand my own solution for some time. Documentation is important!

      • kitchent
         + 1 comment

        Using a matrix of size , we won't be able to tackle the part of the problem. To do this, we want the matrix to take into account all lower scores.

        Most importantly, we have to cancel out the lower accumulation when all we want is just add the possibilities of an entry contributing to this new score. This is not immediately obvious, but when you want only the new possibilities from the score, it should not be everything , but only itself. That's when you want to learn about the term.

        • padeff
           + 1 comment

          I did the the 61th raw, with the checkout number by vector. I m pretty sure I got an index error now, but the math should checkout.

  • lnovak77
     + 1 comment

    Can please someone suggest an idea for less than O(N) solution to deal with test cases 9 and above.

    I assume that there should be analytic formula for coefficients of series expansion of generating function just can't find one.

    • khroliz
       + 1 comment

      https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form This is a basic direction to switch from O(N) to O(log(N))

      • kitchent
         + 1 comment

        Correct me if I'm wrong, but don't we still have to add every distinct ways with score ? Even if we have a linear recurrence relation matrix and figure out a method to calculate the matrix exponentiation quickly, we can't skip those results of , ... etc, or could we?

        • khroliz
           + 0 comments

          Check how you can calculate the sum based on matrix.

  • sachin8951
     + 0 comments

    what is modulo 10^9+9 how to represent answer in that format

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in