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

×

CP1 - Editorial


PROBLEM LINK:

Practice

Contest

Author: D. Vishnu Vardhan reddy

Tester: D. Vishnu Vardhan reddy

Editorialist: D. Vishnu Vardhan reddy

DIFFICULTY:

Easy

PREREQUISITES:

DP, Math(factors).

PROBLEM:

Given an array P of prime numbers , find the Nth number that has its prime factors in P.

EXPLANATION:

We can generate the sequence by multiplying the prime factors with the numbers in the sequence itself and finding the minmum in each step. for example consider prime factors P = [2,3,5], and the quantity to find n = 5

Let k be size of given array of prime numbers. Declare a list for sequence. 1)Insert first number (which is always 1) into list.

2)Initialize array multipler[k] of size k with 0. Each element of this array is iterator for corresponding prime in primes[k] array.

3)Initialize nextMultipe[k] array with primes[k]. This array behaves like next multiple variables of each prime in given primes[k] array i.e; nextMultiple[i] = primes[i] * sequence[++multiple_of[i]].

4)Now loop until there are n elements in sequence.

a) Find minimum among current multiples of primes in nextMultiple[] array and insert it in the list of the sequence.

b) Then find this current minimum is multiple of which prime .

c) Increase iterator by 1 i.e; ++multipler[i], for next multiple of current selected prime and update nextMultiple for it.

Example tracing: p=[2,3,5], n = 5 Let for easy understanding ,multiplier[]= i2,i3,i4

initialize

sequence[] = | 1 | i2 = i3 = i5 = 0;

First iteration

sequence[1] = Min(sequence[i2]2, sequence[i3]3, sequence[i5]*5)

        = Min(2, 3, 5)

       = 2

sequence[] = | 1 | 2 |

i2 = 1, i3 = i5 = 0 (i2 got incremented )

Second iteration

sequence[2] = Min(sequence[i2]*2, sequence[i3]*3, sequence[i5]*5)

         = Min(4, 3, 5)
         = 3
sequence[] =  | 1 | 2 | 3 |

i2 = 1,  i3 =  1, i5 = 0  (i3 got incremented )

Third iteration

sequence[3] = Min(sequence[i2]*2, sequence[i3]*3, sequence[i5]*5)

         = Min(4, 6, 5)
         = 4

sequence[] =  | 1 | 2 | 3 |  4 |

i2 = 2,  i3 =  1, i5 = 0  (i2 got incremented )

Fourth iteration

sequence[4] = Min(sequence[i2]*2, sequence[i3]*3, sequence[i5]*5)

          = Min(6, 6, 5)

          = 5

sequence[] =  | 1 | 2 | 3 |  4 | 5 |

i2 = 2,  i3 =  1, i5 = 1  (i5 got incremented )

Fifth iteration

sequence[4] = Min(sequence[i2]*2, sequence[i3]*3, sequence[i5]*5)

          = Min(6, 6, 10)

          = 6

sequence[] =  | 1 | 2 | 3 |  4 | 5 | 6 |

i2 = 3,  i3 =  2, i5 = 1  (i2 and i3 got incremented )

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

asked 13 Sep, 20:53

dvvr's gravatar image

2★dvvr
112
accept rate: 0%

edited 14 Sep, 10:12

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:

×15,005
×3,393
×1,878
×6

question asked: 13 Sep, 20:53

question was seen: 44 times

last updated: 14 Sep, 10:12