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

×

EARTSEQ - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Evgeniy Artemov
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Sieve of Eratosthenes, Number-Theory and Constructive Algorithms.

PROBLEM:

Given an integer $N \geq 3$, find $N$ distinct numbers such that every pair of consecutive numbers have a common factor $ > 1$ and all possible consecutive three elements have no common factor $ > 1$. Also, all numbers found should be between $1$ and $10^9$. First and Last elements are also considered adjacent here.

SUPER QUICK EXPLANATION

  • A simple way to generate $N$ such distinct numbers is to take a prime and multiply two consecutive elements by this number. This way, the condition of co-primes is handled, but the numbers generated go beyond $10^9$.
  • A better way would be to reuse smaller primes while ensuring all the generated numbers are distinct.

EXPLANATION

This is a constructive problem, and hence, have multiple solutions. Feel free to share your solution in comments.

Note: If we represent a number as the product of prime numbers, Prime factorization of a common factor of the pair of numbers is the common part of prime factorization. If we consider prime values or product of few primes, they have relatively lesser factors as compared to composite numbers. So, for most of the problems involving prime factors/factorization/divisibility, prime numbers bear special importance.

Let us try similar problems first.

Try solving the same problem assuming there's no upper bound on maximum values. Now, we can just multiply a distinct prime number to every pair of consecutive numbers. This way, every two consecutive numbers are not co-prime while every three consecutive numbers are coprime.

The above solution is sufficient to solve the first subtask, but in the second subtask, the values exceed $10^9$, so we need something better.

Try solving the same problem, assuming we are allowed repeated values. Here, we can choose prime numbers and multiplying each position by exactly two primes such that every two consecutive positions share prime factor while every three consecutive numbers do not share any prime factor, taking special care to choose a different prime number when reaching the end of the array.

Now, let us solve the original problem.

Think up and try to mix the above solutions so as to reduce the magnitude of generated numbers while keeping each number distinct.

The construction used in my solution is to reserve the first few primes and then multiply the first two positions by a non-reserved prime, next two positions by another prime and so on. Now, We can multiply Last and first position by a reserved prime, second and third position by different reserved prime, and so on. This way, we are guaranteed to have every pair of consecutive positions divisible by that particular prime number, and every three consecutive positions are coprime since no prime is multiplied to three consecutive positions.

Implementation

For this problem, we can preprocess and calculate a list of primes beforehand using the sieve of Eratosthenes and then for every test case, use primes from the list instead of recomputing.

Interesting Fact

This problem can also be approached as a challenge problem where we need to minimize the maximum value generated in sequence. Can you minimize? Say for $N = 50000$

Time Complexity

Time complexity is $O(MX*log(log(MX)) + \sum N)$ per test case where $MX$ is the upper limit till primes are found. Finding primes up to $10^6$ suffices for this problem.

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

This question is marked "community wiki".

asked 14 Jan, 16:08

taran_1407's gravatar image

6★taran_1407
3.9k2791
accept rate: 22%

edited 14 Jan, 19:34

admin's gravatar image

0★admin ♦♦
19.8k350498541


I did by finding Euler Circuit of a complete graph of odd degree, and then adjusting it by removing the last edge and adding path of required length.

link

answered 14 Jan, 20:33

fluffy_x's gravatar image

3★fluffy_x
211
accept rate: 0%

(14 Jan, 22:51) fluffy_x3★

What I did was...
Three case :

1) $n \mod 3 == 0$

6, 10, 15, 6*p1, 10*p2, 15*p3, 6*p4, 10*p5, ... so on

2) $n \mod 3 == 1$

21, 14, 10, 15, 6*p1, 10*p2, 15*p3, 6*p4, 10*p5, ... so on

3) $n \mod 3 == 2$

33, 77, 14, 10, 15, 6*p1, 10*p2, 15*p3, 6*p4, 10*p5, ... so on

Where p1,p2,p3,... are primes greater than 11...

(as I used primes till 11 in these case to make sequence N%3==0)

link

answered 14 Jan, 22:06

l_returns's gravatar image

5★l_returns
1.4k19
accept rate: 24%

edited 14 Jan, 22:08

basic idea is keep repeating 6,10,15 keeping all number different by multiplying with different primes...
We don't need more than N+5 primes for any case...
so 50005 primes in worst case... (akaik there are 78,498 primes upto value 10^6)

(14 Jan, 22:10) l_returns5★

HERE is my solution

(14 Jan, 22:24) l_returns5★

One interesting property which I found was that "No three consecutive odd numbers have a common divisor" starting from 3. So, I tried multiplying 3 to the first 2 elements, then multiplied 5 to the second and third elements, then multiplied 7 to the third and fourth elements and so on... (completing the cycle with a prime number for the last and the first elements just in case if the first element and the second last element don't have a common divisor). This passed subtask-1, but didn't pass subtask-2. Maybe it was because of generating numbers > 10^9. Is there a modification I could do to this approach to get it ACed?

link

answered 16 Jan, 11:01

tejkiran_v's gravatar image

4★tejkiran_v
102
accept rate: 0%

edited 16 Jan, 11:06

I am a bit disappointed that the property of coprimes weren't considered in the editorial. In fact, it is not necessary at all to generate prime numbers.

If we consider each positive integer as a multiset of its prime factors, then the problem could be reduced to:

Find N ordered multisets of integers that for every 2 consecutive sets, the intersection is not empty, but the each intersection of 2 consecutive intersections is an empty set, i.e. coprime to each other.

Therefore if we find a list of consecutive coprimes, the result would be product of 2 consecutive elements of that list.

Implementation in Python:

from math import gcd
from itertools import cycle, islice
from sys import stdin

CANDIDATES = cycle(range(2, 30000))

a, b, new = 30011, 30013, {}
coprimes, result = [a, b], [a * b]
for _ in range(49998):
    for i in CANDIDATES:
        if new.get(b * i, True) and gcd(a, i) == 1 == gcd(b, i):
            coprimes.append(i)
            a, b = b, i
            break
    new[a * b] = False
    result.append(a * b)

next(stdin)
for N in map(int, stdin):
    N -= 1
    print(coprimes[N] * 30011, end=' ')
    print(*islice(result, N))

Since the first 2 coprimes are hardcoded to be primes, we can reuse the list for every N in the given constraint, thus the overall complexity is drastically reduced.

link

answered 15 Jan, 09:23

mcsinyx's gravatar image

2★mcsinyx
313
accept rate: 0%

What i did was ... 1)found out out some 4000 consecutive prime numbers using seive

2)appended them to a new array under the condition that the product of two consecutive numbers does not cross 10^9.This helped me pass the first sub task.

3)For the next part I started my series from 5 and accepted primes at different intervals starting from 2 and incrementing interval by 1 and also a different starting point for every interval.

4)this helped me generate all(50000 in this case) possible combinations of products of primes and all i had to do was consider the first 550 prime numbers, and also including the previous

The time complexity was O(d^3),d=550. but since the inner loops depended on the interval it worked even faster.

link

answered 15 Jan, 16:03

portgas_d_raf's gravatar image

3★portgas_d_raf
11
accept rate: 0%

edited 15 Jan, 16:05

my solution does not use generating primes at all. we forget some facts about numbers with small difference and their common factors.Here is my solution

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

link

answered 16 Jan, 16:56

urzbeckuvayy's gravatar image

4★urzbeckuvayy
1
accept rate: 0%

Urzbeckuvayy...can u please explain ur logic a bit?

link

answered 17 Jan, 14:27

sabios's gravatar image

2★sabios
1
accept rate: 0%

in java only 12500 primes can be stored for 50000 Bytes

link

answered 17 Jan, 21:47

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

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

what is wrong in this solution?.

link

answered 18 Jan, 10:12

dhar1mesh's gravatar image

3★dhar1mesh
11
accept rate: 0%

Can you elaborate how you got this pattern @l_returns?

link

answered 24 Jan, 00:45

a_m_k_18's gravatar image

2★a_m_k_18
211
accept rate: 0%

in the setter's solution can anyone explain how and int x = 4 and if (i == n - 1) {ind = 5;} how this two constant are fixed ? I tried some other constants and some of them give right answer and some of them dont't; @eartemov

link

answered 29 Jan, 23:11

im_amartya's gravatar image

3★im_amartya
32
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:

×1,668
×649
×631
×301
×202
×109
×32

question asked: 14 Jan, 16:08

question was seen: 2,150 times

last updated: 29 Jan, 23:11