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.
- All Contests
- ProjectEuler+
- Project Euler #151: Paper sheets of standard sizes: an expected-value problem.
- Discussions
Project Euler #151: Paper sheets of standard sizes: an expected-value problem.
Project Euler #151: Paper sheets of standard sizes: an expected-value problem.
Sort by
recency
|
6 Discussions
|
Please Login in order to post a comment
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.
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?
The output for 8 is well over 200000 lines.
So does that mean I just cannot complete the challenge?
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.
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 ^^
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).
Can't understand the output format, why is 500000005 equal to 3/2?
you can google modular multiplicative inverse
thanks for your help, now i can understand the output format.
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
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
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)
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.
I agree.I'm confused too!
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.
Expected # times he sees a single piece of paper = 0.5*2 + 0.5*3 = 5/2.