This soln deserves a green tick over here as well. xD
1 Like
I too had a hard time figuring out, just started by folding paper and marked the distance on paper it was 1/2, 1/4, 3/8, 5/16, 11/32 now You have to just find the pattern
arr = 1, 1, 3, 5, 11
ans = (2*arr[n-2] + arr[n-1]) / 2^n
Just providing an alternate solution.
Simply the sum of the GP series 1/2 - 1/4 + 1/8 - 1/16… needs to be calculated.
The sum of GP series can be manually calculated in terms of n as sum = a(1 - r^n)/(1-r), where a = 1/2 and r = -1/2.
Since r is negative there will be two different cases for n = odd and n = even.
From the formula you can get the numerator and denominator, reduce them to their simplest form (using gcd) and that will be your answer.
In case you need a reference
nth term of the series was simply the average of (n-1)th and (n-2)th term. Since denominator was always even and numerator always come out to be odd giving us irreducible fraction everytime.
Here’s my solution: https://www.codechef.com/viewsolution/21455028
Hahaha, really funny stuff.
Fun fact: The current world record for folding paper in half is thirteen times. So you can only solve the first subtask by actually folding paper.
1 Like
That’s not just “brute force” - that’s a 100-ton steamroller used for ironing handkerchiefs. Ogre force.
For any n, the values are (2^n+1)//3 and 2^n (where // rounds the division down to integer).
I worked this out by converting the entire Amazon rainforest into paper. Hope no-one noticed.
1 Like
Do you deserve a mention in here?:
1 Like
it is not that difficult also.
T(1)=1/2,
T(2)=1/2-1/4,
T(3)=1/2-1/4+1/8,
.
.
.
, T(n)=1/2-1/4+1/8-1/16+1/32…+(-1^(n+1))*(1/2)^n.
Just solve this G.P and you will get the answer
Even simple, A[i] = (A[i-1]+A[i-2)/2, with A[1] = 1/2 and A[2] = 1/4.
took some time… but was exciting to find values for n=4,5 and based on the sequence obtained …drawing conclusions…
Please go through my code… check at bottom for explanation… i used “-” dash rather than paper to solve this stuff 
I found a cool pattern too.
I compute numerator and denominator separately. Kind of DP style, where numerator value for n foldings depends on the numerator value for n-1 foldings.
Two arrays num[] and den[] are used for numerator and denominator.
Set base case num[1], den[1], num[2], den[2] as 1, 2, 1, 4 respectively.(for 1/2, 1/4)
for i = 3 to i = N (here N = 25 max constraint):
den[i] = 2^i
if i is odd: num[i] = 2 * num[i-1] + 1
if i is even: num[i] = 2 * num[i-1] - 1
So we have precomputed till N.
We just need to display num[n] and den[n] for any given value of n (no. of foldings) now.
My Solution: https://www.codechef.com/viewsolution/21481878
I posted it in the PRDRG - Editorial topic but I’ll post it here too cuz why not?
The first ridge is at distance \frac12, the second is at \frac{1}{2}-\frac{1}{4}, the third ridge at \frac{1}{2}-\frac{1}{4}+\frac{1}{8}, the fourth ridge is at \frac{1}{2}-\frac{1}{4}+\frac{1}{8}-\frac{1}{16}…
Notice a pattern?
The n^{\text{th}} ridge is at a distance of
\sum_{i=1}^{n} -(-2)^{-i} = \frac{2^n-(-1)^n}{3\times 2^n}.
Now 2 clearly does not divide 2^n-(-1)^n and 3 does.
So, the numerator is \frac{2^n-(-1)^n}{3} while the denominator is 2^n.
Time complexity: O(1)
I had the same problem when one of my senior told me that I interpreted it wrong. Only the top layer needs to be folded each time that makes it 1/2 1/4 3/8 and so on. I have done it by adding the fractions. Have attached the link to the code. For any further queries, feel free to ask any question.