You are not logged in. Please login at www.codechef.com to post your questions!

×

Chef and Ridges

7
2

It's my 4th day on this problem, I'm now bald and my wife left me. I literally tried everything on this problem.

Starting with the first thing that came up in my mind, to working with big numbers and finally to LITERALLY outputing the answers I MEASURED for the first 5 foldings.

I've read the problem again and again, bought all the paper my city had and tried folding them to observe the exact answer. Done this with all the paper in my country and when there was no paper left I went out in the woods, cut some trees and made my own paper and I still can't seem to find the right answer.

God has abandoned me.

asked 11 Nov '18, 20:06

bita_alexandru's gravatar image

2★bita_alexandru
6913
accept rate: 0%

edited 11 Nov '18, 21:16

4

Feedback Forwarded to setting panel XD

(11 Nov '18, 21:17) vijju123 ♦♦5★
7

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

(11 Nov '18, 21:21) mgch6★
2

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

(11 Nov '18, 21:23) vijju123 ♦♦5★

@vijju123 "God has abandoned me."

(11 Nov '18, 21:26) mgch6★
2

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

(11 Nov '18, 21:27) vijju123 ♦♦5★
1

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

(11 Nov '18, 22:31) aryanc4035★
2

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. :)

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

Anything else?

(11 Nov '18, 22:39) taran_14076★
1

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

(11 Nov '18, 22:48) vijju123 ♦♦5★
1

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.

(14 Nov '18, 00:49) the_extractor4★
showing 5 of 9 show all

Problem was super fine..and it's good that setter has provided only 2 test cases..otherwise , problem could not make any sense. it would be easier to solve if n=3 also get provided.

I have also tried many times this question..but at last i got the pattern and simply solve it..( but i also spoiled 6-7 pages to understand the question ).

Must watch my solutions , i have literally solved for all values of n..

https://www.codechef.com/NOV18B/status/PRDRG,sapjv

link

answered 13 Nov '18, 02:01

sapjv's gravatar image

2★sapjv
613
accept rate: 0%

1

Holy Moly Brute Force xD

(13 Nov '18, 02:20) pavitra_ag4★
1

LOL =)))))

(13 Nov '18, 02:33) bita_alexandru2★
1

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

(13 Nov '18, 02:42) aryanc4035★
(14 Nov '18, 01:40) pavitra_ag4★

That's not just "brute force" - that's a 100-ton steamroller used for ironing handkerchiefs. Ogre force.

(14 Nov '18, 03:46) joffan5★

Ha, nice. That's me on pretty much every contest. Well, keep at it, or come back to it later when the editorial is out.

link

answered 11 Nov '18, 20:29

jlewis200's gravatar image

5★jlewis200
222
accept rate: 0%

1

I surely won't leave this unsolved.

(11 Nov '18, 20:37) bita_alexandru2★

"I've read the problem again and again, bought all the paper my city had and tried folding them to observe the exact answer. Done this with all the paper in my country and when there was no paper left I went out in the woods, cut some trees and made my own paper and I still can't seem to find the right answer."

You are not a solitary person trying to solve PRDRG in such a manner. #Same_here. Tried (almost) all possible combinations for N<=5 but it seems that chef isn't happy with my recipe yet. :(

link

answered 11 Nov '18, 22:24

dbhatt_10's gravatar image

2★dbhatt_10
923
accept rate: 0%

edited 11 Nov '18, 22:26

problem not mentioned clearly, it took me 2 days to solve , after trying folding the paper in different ways ,I finally solved it. It was easy one to code, just find pattern how paper being folded.

link

answered 12 Nov '18, 00:02

ulti72's gravatar image

2★ulti72
92
accept rate: 0%

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.

link

answered 14 Nov '18, 04:07

joffan's gravatar image

5★joffan
9488
accept rate: 13%

1
(14 Nov '18, 09:19) arnavvarshney3★

Problem is not well explained and its vague. Test cases should be more than one at least. I commented multiple times but no response from admin. Super annoying. If somebody could help with N=3 at least I can get some idea.

link

answered 11 Nov '18, 22:00

prmondal's gravatar image

3★prmondal
512
accept rate: 0%

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

(11 Nov '18, 22:54) bita_alexandru2★

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

link

answered 13 Nov '18, 05:29

ayush4's gravatar image

3★ayush4
163
accept rate: 10%

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 https://www.codechef.com/NOV18B/status/PRDRG,charlie777

link

answered 13 Nov '18, 12:43

charlie777's gravatar image

2★charlie777
1
accept rate: 0%

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

link

answered 13 Nov '18, 17:10

yugandhar_t's gravatar image

3★yugandhar_t
111
accept rate: 0%

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

link

answered 14 Nov '18, 19:26

mt2668's gravatar image

2★mt2668
1
accept rate: 0%

Even simple, A[i] = (A[i-1]+A[i-2)/2, with A[1] = 1/2 and A[2] = 1/4.

(14 Nov '18, 20:30) taran_14076★

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

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

link

answered 15 Nov '18, 10:14

s_shero's gravatar image

2★s_shero
1
accept rate: 0%

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

link

answered 20 Nov '18, 23:09

sreeramk28's gravatar image

2★sreeramk28
1
accept rate: 0%

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)$

link

answered 21 Nov '18, 11:30

islingr's gravatar image

4★islingr
513
accept rate: 0%

edited 21 Nov '18, 11:40

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

link

answered 21 Nov '18, 21:44

namratasaun's gravatar image

2★namratasaun
1
accept rate: 0%

-1

What would be the answer for n=3 btw?

link

answered 11 Nov '18, 23:28

codingwolf's gravatar image

2★codingwolf
5
accept rate: 0%

-1

The problem is very easy to solve once you have understood it. The test cases aren't very clear in explaining the problem. In this problem you have to find the distance of the latest ridge formed after n folds(order of folding is right to left then left to right) from the initial left side. Perform this on a paper. The solution becomes pretty clear.

link

answered 12 Nov '18, 02:36

karan_2502's gravatar image

2★karan_2502
-1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,738
×154
×23

question asked: 11 Nov '18, 20:06

question was seen: 2,593 times

last updated: 21 Nov '18, 21:44