PRDRG - EDITORIAL

general
, , , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Sumegh Roychowdhury
Tester: Zhong Ziqian
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

Basic Math would be enough. Greatest Common Divisor and Simulation.

PROBLEM:

Find the position of Kth Ridge on a cardboard when the following procedure is performed Kth time, alternatively

Pick the right side of the board and fold it so that it matches with the left end. OR

Pick up the left end of the board and fold it to meet the right end of cardboard.

SUPER QUICK EXPLANATION

  • The new ridge formed is always the midpoint between the previous two ridges formed. For a start, We can see, that the first two ridges are at positions 1/2 and 1/4 respectively.

EXPLANATION

Let us first understand how ridges are being created.

alt text

alt text

alt text

alt text

We can see, that the size of cardboard gets reduced to half, and the ridge is formed at left or right end of cardboard alternatingly.

So, it is not hard to see, that at every step,

It is not hard to see, that every time we fold the cardboard, we form a new ridge, which is exactly at the midpoint of the previous two ridges.

This gives way to the solution. At every step, we can find the midpoint of the previous two ridges and use it for calculating the positions of next ridges. Since N is quite Small, we can even precompute answers for all values of N.

Now, We need to print the answer in reduced form. Basically, if two number A and B have GCD G, then (A/G)/(B/G) represent the same fraction in reduced terms.

GCD of two numbers can be easily found using Euclid’s GCD algorithm, which you may find here.

As for first two ridges, we can assume Right end and the Left end to be first and second ridge respectively, for a simpler implementation, or just see positions of first two ridges from samples.

Time Complexity

Time complexity is O(N) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

2

here,we not need to compute gcd(a,b).
after simple obgervation we get,
y=pow(2,n) and for
x form serise 1,1,3,5,11,21,…
a[i]=2*a[i-2]+a[i-1] where a[1]=a[2]=1.
so, we precompute serise for x.

This is my code: CodeChef: Practical coding for everyone

2 Likes
3

The output for the 150th fold would be:

475749230901986627019428656483165045460915541 1427247692705959881058285969449495136382746624

(thanks for large integers, Python)

To get these values without iterating through:

Click to view

The numerator n (on the right) is of course 2^{150}. The denominator d on the left is (n-1)/3. If the fold number were odd, d would be (n+1)/3

4

Video Editorial CodeChef November Long Challenge - Chef and Ridges (PRDRG) - YouTube

5

@joffan but the range of n is at most 25 for this prob

6

@savaliya_vivek how did you came to the conclusion that it formed the series 1,1,3,5,11,21,… a[i]=2*a[i-2]+a[i-1] where a[1]=a[2]=1
or if anyone can explain?

7

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)

4 Likes
8

If we notice the pattern formed by the numerator x and denominator y for a given n, it is like the numerator for n+1 is 2x+1 or 2x-1 and denominator is 2y. This 2x+1 and 2x-1 in the numerator follow an alternating pattern.

Thus, the answer for a given n can be calculated based on n-1 with simple calculation.

My Solution

9

we can see the output pattern as 1/2 1/4 3/8 4/16 11/32…going on…for the ith fold…the fraction is numerator=(denominator of i-1th)-(numerator of i-1th)…nd denominator=(2 to the power of i)

so basically for ith fold…we use a recursion function…
my code link…
https://www.codechef.com/viewsolution/21746172
cheers!!!

10

@ganesh92 - yes, I know that the fold limit is 25. This is just for fun and - if people want to try high fold numbers - a test value for them.

11

@ganesh92 yes, I know - added a comment to my answer.

12

It is basically the same. Just that I see that all terms will be odd.

See my solution for this approach. Nice

13

Using [ hide ] and [ /hide ] tags like opening and closing tags without spaces between hide and square braces.

1 Like
14

@taran_1407 Thanks, works beautifully!

1 Like
15

Why is the question’s vocabulary so bad? The question reads as “Find the last ridge”, whereas the actual solution consists of finding the Kth / Nth ridge. This is so frustrating.

2 Likes