×

# Array and operations : Codeforces Round 284

 0 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 333●2●3●9 accept rate: 20%

 0 editorials :- codeforces go through it answered 25 Dec '14, 18:44 1.2k●11 accept rate: 19% Read that. Could not completely understand it. Hence asked here. (25 Dec '14, 19:30)
 0 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!!! answered 25 Dec '14, 22:45 4★the65bit 1.1k●10●13●28 accept rate: 13%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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