Project Euler #151: Paper sheets of standard sizes: an expected-value problem.

Sort by

recency

|

6 Discussions

|

  • + 0 comments

    The order of the output is determined by the value of the state which is the order of the recurence calls. The order of the output for N = 4 for the first few configuration states is:

    0 0 0 0: 0, 0 0 0 1: 1, 0 0 0 2: 1, 0 0 0 3: 1, 0 0 0 4: 1, 0 0 1 0: 2, 0 0 1 1: 500000005, 0 0 1 2: 333333337, 0 0 1 3: 250000003, 0 0 2 0: 500000005, 0 0 2 1: 388888893

    To beat all test cases memoization must be used. Moreover we can cache modulo inverse as the biggest one is mod inverse 64.

  • + 1 comment

    Test cases 0 through 3 work for me, but 4 and 5 don't. I assumed the inputs are 7 and 8, so I looked for myself what the outputs are. It turns out for inputs 3 through 6 it just gives the answer, but for 7 and 8 it gets 'truncated'. What should I do? How is it even possible that some people got it right?

    • + 1 comment

      The output for 8 is well over 200000 lines.

      • + 1 comment

        So does that mean I just cannot complete the challenge?

        • + 1 comment

          You must be close to the solution if you can solve it through test case 3. Do you run out of time or does it report incorrect answer?

          The environment is different for the "test with custom data" vs "submit solution". You can use custom data to test/debug, but the buffer for screen output is limited.

          If you submit a solution and your code is correct, and it finishes in time, you will get the green check.

  • + 1 comment

    And this is where I discovered that modular fraction are a thing and that they can be added and multiplied just like normal fractions. (they form a ring ?!)

    Woaw mind blown ^^

    • + 0 comments

      Z/nZ (integers modulo n) is always a ring. However not all integers are invertible (for the multiplication) modulo n (and the "modular fraction" P/Q only makes sense when Q is invertible), only are those that are coprime with n. They from a multiplicative group denoted as (Z/nZ)*. Z/nZ forms a field iff (Z/nZ)* = Z/nZ \ {0}, i.e. iff n is prime (and in that case any "modular fraction" makes sense). This is why large answers are often asked modulo a prime number (such as 10^9+7).

  • + 1 comment

    Can't understand the output format, why is 500000005 equal to 3/2?

    • [deleted]
      + 1 comment

      you can google modular multiplicative inverse

      • + 0 comments

        thanks for your help, now i can understand the output format.

  • [deleted]
    + 2 comments

    for N=4, is the following results correct? if my understanding of the problem statement is correct, I think the results should be correct, but it cannot pass the test case

    0 0 0 0: 0

    0 0 0 1: 1

    0 0 0 2: 1

    0 0 1 0: 2

    0 0 0 3: 1

    0 0 1 1: 500000005

    0 0 0 4: 1

    0 0 1 2: 333333337

    0 0 2 0: 500000005

    0 1 0 0: 500000006

    0 0 1 3: 250000003

    0 0 2 1: 388888893

    0 1 0 1: 916666675

    0 0 2 2: 319444448

    0 1 0 2: 694444451

    0 1 1 0: 652777784

    0 1 1 1: 555555561

    1 0 0 0: 555555562

    • [deleted]
      + 2 comments

      in double format, they are:

      0 0 0 0: 0

      0 0 0 1: 1

      0 0 0 2: 1

      0 0 1 0: 2

      0 0 0 3: 1

      0 0 1 1: 1.5

      0 0 0 4: 1

      0 0 1 2: 1.33333

      0 0 2 0: 1.5

      0 1 0 0: 2.5

      0 0 1 3: 1.25

      0 0 2 1: 1.38889

      0 1 0 1: 1.91667

      0 0 2 2: 1.31944

      0 1 0 2: 1.69444

      0 1 1 0: 1.65278

      0 1 1 1: 1.55556

      1 0 0 0: 2.55556

      • + 1 comment

        This is what I have got for N=4, but still not correct according to the checker. I hope my mistake can be pointed out since I got the same answer by hand.

        0 0 0 0: 0

        0 0 0 1: 1

        0 0 0 2: 1

        0 0 0 3: 1

        0 0 0 4: 1

        0 0 1 0: 2

        0 0 1 1: 500000005 (3/2)

        0 0 1 2: 333333337 (4/3)

        0 0 1 3: 250000003 (5/4)

        0 0 2 0: 500000006 (5/2)

        0 0 2 1: 888888897 (17/9)

        0 0 2 2: 625000006 (13/8)

        0 1 0 0: 500000006 (5/2)

        0 1 0 1: 666666673 (5/3)

        0 1 0 2: 416666671 (17/12)

        0 1 1 0: 777777786 (25/9)

        0 1 1 1: 13888891 (145/72)

        1 0 0 0: 13888892 (217/72)

    • + 2 comments

      can't understand why is 0100: 500000006? I think it should be 0100: 3, because when you got a A2 paper, it will take you 3 times to get an A4 paper.

      • + 0 comments

        I agree.I'm confused too!

      • + 0 comments

        That's not what it's asking. If the new guy opens the envelope and sees 0100, then there is one piece of paper inside. Count=1. He'll cut it up, keep the smallest one, and produce 0011. The next time he goes to the envelope, it will have two pieces of paper, so Count is unchanged at 1. With a 50-50 chance, he'll grab the larget piece (A2), split it, keep half, and put the other half back into the envelope: 0002. The next time, there are two pieces, so we still have Count=1, he'll keep one resulting in: 0001; Finally, for the last batch, he opens the envelope to find one piece of paper, so we increment Count=2. Go through all possible paths, count # of times we have a single paper, compute expected value.

        • 0100 -> 0011 -> 0002 -> 0001 -> 0000, Count=2, Prob=0.5
        • 0100 -> 0011 -> 0010 -> 0001 -> 0000, Count=3, Prob=0.5

        Expected # times he sees a single piece of paper = 0.5*2 + 0.5*3 = 5/2.