Chef and Ridges

help
, ,
11

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: CodeChef: Practical coding for everyone

12

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
13

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

14

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 :stuck_out_tongue:

https://www.codechef.com/viewsolution/21554147

15

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: CodeChef: Practical coding for everyone

16

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.

My solution

Time complexity: O(1)

17

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.

Link to the code

18

I surely won’t leave this unsolved.

1 Like
19

Feedback Forwarded to setting panel XD

4 Likes
20

C’mon… find another wife who will help you to solve this problem!! 18 hrs left…

7 Likes
21

@mgch - That amounts to cheating if his wife is also taking part in long :stuck_out_tongue:

2 Likes
22

@vijju123 “God has abandoned me.”

23

@mgch God may abandon him, but MOSS and penalty wont. >_<

2 Likes
24

Since MOSS penalty guarantees nonnegative rating. So technically speaking MOSS penalty should not have any effect on unrated users.

1 Like
25

Hopefully, you leave enough trees for coming generations.

As for the problem, I sincerely wish you manage to solve this problem during the contest (with or without wife), and if not, I have written Editorial for this problem which may help you. :slight_smile:

Lastly, for god, I hope God will find in his heart to accept you back. :slight_smile:

Anything else?

2 Likes
26

@taran_1407 - Statistics feel theres at least one more person eagerly awaiting your editorials. :p. Or…perhaps not XD

1 Like
27

Yeah, if they had an example for n=3, that would’ve been great

28

Holy Moly Brute Force xD

1 Like
29

LOL =)))))

1 Like
30

This soln deserves a green tick over here as well. xD

1 Like