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

×

Array and operations : Codeforces Round 284

Problem : link text

I began by first prime-factorizing each number of the array. Given one good-pair (ik,jk) we can divide both numbers A[ik] and A[jk] by their common prime powers i.e if A[ik]=2^5 * 3^4 and A[jk]=2^3 * 3^7 then we can divid both of them by 2 a total of 3 times and divide by 3 a total number of 4 times. The number of operations increase by the minimum of the common prime powers i.e by 7.

Total number of operations can then be taken as the sum over all common prime powers for all good pair given. Here is my approach.

My code : link text

Pretest 5 contains this test data. My answer on this is 28 but the correct answer is 31.

Can anyone explain why the output is 31 and the correct approach to solve the problem?

10 9

67108864 8 2 131072 268435456 256 16384 128 8 128

4 9

5 10

6 9

9 10

1 4

3 8

8 9

1 2

4 5

asked 25 Dec '14, 18:02

ironmandhruv's gravatar image

4★ironmandhruv
333239
accept rate: 20%


editorials :- codeforces go through it

link

answered 25 Dec '14, 18:44

acodebreaker2's gravatar image

1★acodebreaker2
1.2k11
accept rate: 19%

Read that. Could not completely understand it. Hence asked here.

(25 Dec '14, 19:30) ironmandhruv4★

The problem is that you are doing is greedily, which is wrong approach. Try this test case :

4 3
8 4 32 8
1 2
2 3
1 4

Your code is giving 3 as output, while the correct output should be 5.

If we change the order of the input it gives correct answer.

Hope it helps!!

Happy Coding!!!

link

answered 25 Dec '14, 22:45

the65bit's gravatar image

4★the65bit
1.1k101328
accept rate: 13%

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,650
×36

question asked: 25 Dec '14, 18:02

question was seen: 1,536 times

last updated: 25 Dec '14, 22:45