2497 - LCM Pair Sum

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
dovier
Posts: 1143
Joined: 8 years ago
Location: Havana, Cuba
Gender: Male
Cuba

2497 - LCM Pair Sum

Post by dovier » 6 years ago




User avatar
EduardoQuintana
Posts: 14
Joined: 8 years ago
Location: Universidad de Cienfuegos (UCf)
Gender: None specified

Re: 2497 - LCM Pair Sum

Post by EduardoQuintana » 6 years ago

First of all: I think few people actually read these posts, but I don't have any other choice than posting here since 'nobody' replies messages. Thanks for all people who does, and apologies.

Any number can be represented as the product of power of its prime factors.
Example: 18= 2^1 * 3^2 * 5^0, in case we are interested in factor 5 too. (5^0 == 1)

Using this representation its easy to find the LCM (least common multiple) of two numbers. Simply for all prime factors in each, find the largest power, and that will be the power of that factor for their LCM.
Example: 18=2^1 * 3^2 * 5^0, 10=2^1 * 3^0 * 5^1, then LCM(18,10)=2^max(1,1) * 3^max(2,0) * 5^max(0,1)=2^1 * 3^2 * 5^1

As the problem states, given a number BIG_ONE, we need to find the sum of all pairs P+Q, for which P<=Q and LCM(P,Q)=BIG_ONE.
In fact BIG_ONE is so big that its given only its prime factors and powers: A1, B1, A2, B2, ..., An, Bn.
So you could compute if you like to: BIG_ONE=A1^B1 * A2^B2 * ... * An^Bn

For the theory stated before it's clear that in every P and Q, the i'th prime factor Ai should be represented by a power Bi in P or Q, or both at the same time.

Another way to put it, for each P and Q:
P=A1^p1 * A2^p2 * ... * An^pn,
Q=A1^q1 * A2^q2 * ... * An^qn

where P<=Q, and B1=max(p1,q1), Bi=max(pi,qi),
so (pi==Bi || qi==Bi)

Now comes the magic part, the product of the sum of different powers for each prime factor Ai gives all possible distributions of powers:
(2^5+2^1)*(3^3+3^0)=2^5*3^3+2^5*3^0+2^1*3^3+2^1*3^0

So products of sums gives all distributions. uhm... interesting

And we wish to have in the P,Q pair always an Ai power of Bi
so from the sum (Ai^Bi+Ai^Si) where Bi>=Si>=0 we are going to get all pairs having the wanted Ai^Bi and some complementary power Ai^Si but not least important.

As we are interest in all pairs, we should compute then:
( (A1^B1+A1^0)+(A1^B1+A1^1)+...+(A1^B1+A1^B1) )*( (A2^B2+A2^0)+(A2^B2+A^1)+...+(A2^B2+A2^B2) )*...*()

But there is a problem of repeated pairs.
See the example BIG_ONE=3^2*5^1
all_sums=((3^2+3^2) + (3^2+3^1) +(3^2+3^0))*((5^1+5^1)+(5^1+5^0))=
=(3^0*5^0+3^2*5^1)+(3^1*5^0+3^2*5^1)+(3^0*5^1+3^2*5^0)+(3^1*5^1+3^2*5^0)+
+ 2*(5^1*3^2+5^1*3^2)+2*(5^1*3^2+5^1*3^1)+2*(5^1*3^2+5^1*3^0)

A bug, discovered, we are getting twice some of the pairs.
The problem is when we add (3^2+3^2) or (5^1+5^1) we are getting pairs having the full power twice.
Notice that this bug is fixed if we sum the pairs of powers from (3^2+3^0) up to (3^2+3^1) and finally (3^2+3^2)/2
or just (3^2)
thus:
all_sums=((3^2) + (3^2+3^1) +(3^2+3^0))*((5^1)+(5^1+5^0))=
=(3^0*5^0+3^2*5^1)+(3^1*5^0+3^2*5^1)+(3^0*5^1+3^2*5^0)+(3^1*5^1+3^2*5^0)+
+ (5^1*3^2)+(5^1*3^2+5^1*3^1)+(5^1*3^2+5^1*3^0)
but this time we are getting an unpaired number, that is 5^1*3^2=BIG_ONE
If P=5^1*3^2, its Q companion can be only Q=5^1*3^2

thus finally the answer is:
all_sums=((3^2) + (3^2+3^1) +(3^2+3^0))*((5^1)+(5^1+5^0)) + BIG_ONE=
=(3^0*5^0+3^2*5^1)+(3^1*5^0+3^2*5^1)+(3^0*5^1+3^2*5^0)+(3^1*5^1+3^2*5^0)+
+ (5^1*3^2+5^1*3^2)+(5^1*3^2+5^1*3^1)+(5^1*3^2+5^1*3^0)

You can check that all pairs are present this time, and this way of proceeding can be generalized to any number of prime factors and its powers.

Then given: A1,B1,A2,B2,...,An,Bn

Just compute the Sum_1,Sum_2,...,Sum_n
where Sum_i=(Ai^Bi)+(Ai^Bi+Ai^0)+(Ai^Bi+Ai^1)+(Ai^Bi+Ai^2)+...+(Ai^Bi+Ai^(Bi-1))
compute also BIG_ONE=A1^B1*A2^B2*...*An^Bn

And the answer is:
all_sums=Sum_1*Sum_2*...*Sum_n + BIG_ONE

Of course this number is too big to fit in a 64bit memory, use modular operations mod 1000000007 as the problem states.

The amount of prime factor can be up to nmax=15, and its powers up to Bmax=50,
then computing every power in linear time gives for each prime factor O(nmax*Bmax)
then, all Sum_i calculation, -> O(Bmax*nmax)
The product of Sum_i's -> O(nmax)
Computing BIG_ONE -> O(nmax)

Overall complexity for Tmax=500 cases -> O(Tmax * Bmax * nmax) aprox 375000 operations,
will easily fit in 1second time limit.

I liked this problem since I read its first line,
Problem "LCA for strings" is similar to this one.

Now, here's the controversial part of the matter.
This algorithm was judged as TLE at COJ(Time Limit Exceeded in test 1).
I don't have the slightest clue why.

I encourage every fellow whom had tried to solve this problem to visit the site http://icpc.cs.uchicago.edu/tryouts2013/pset/index.html
Where you can find full coded solutions and extreme input and output files to check your solutions (nmax=15, Bmax=50, Tmax=500)

My solution coded solved the input file in 100ms on my computer (* don't blame my Intel i3-core at 1.50Ghz ), and found the same values for all test cases.

I would post my code here if there wasn't a policy of penalty for posting ac codes. But I this case I'm not sure because COJ gave me the TLE judgement.
What should I do?
May I post my TLE code here?

Code: Select all

/*
	Eduardo Quintana Miranda
	"2497 - LCM Pair Sum"
	20-09-2013
*/

#include <iostream>
#include <time.h>
using namespace std;
typedef long long ll;

const ll MOD=1000000007;
...
...
L@grang3

User avatar
ymondelo20
Posts: 1968
Joined: 8 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 2497 - LCM Pair Sum

Post by ymondelo20 » 6 years ago

Yes, you can post your code, due to it´s not accepted.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
EduardoQuintana
Posts: 14
Joined: 8 years ago
Location: Universidad de Cienfuegos (UCf)
Gender: None specified

Re: 2497 - LCM Pair Sum

Post by EduardoQuintana » 6 years ago

Can anybody tell me please: Why this code gives TLE?
Its complexity is O(T*C*a),
T<=500
C<=15
a<=50
Last edited by EduardoQuintana on Mon Oct 07, 2013 11:55 pm, edited 1 time in total.
L@grang3

User avatar
ReynaldoGil
Posts: 38
Joined: 8 years ago
Location: Santiago de Cuba
Gender: None specified

Re: 2497 - LCM Pair Sum

Post by ReynaldoGil » 6 years ago

I'm almost sure the datatests are wrong, maybe some judge could try to get AC on this one and see what happens?

charlie
Posts: 2
Joined: 8 years ago
Gender: None specified

Re: 2497 - LCM Pair Sum

Post by charlie » 6 years ago

testdata for problem was fixed and rejudge, there are solutions AC!! :D

Post Reply

Return to “Problem set”