Saturday, March 03, 2012

SRM 535 : lame

The other day I decided to stop opening the medium problem first. So to open div1 500 once warmed up as opposed to 250. I think this will hurt my rating, as you can see from today's performance in which I picked a unnecessarily long solution for it. Coded it with a lot of unnecessarily steps and took a lot of time to fix many bugs. The result was a very slow submission and low score. I felt the difference when I opened the medium though because I was more active then. I have to improve my pace so that my activity level is high the whole match, but it is going to be hard.

Div 1 250: FoxAndGCDLCM
You get two numbers: L and G, both between 1 and 10^12, inclusive. Find two numbers A and B such that gcd(A,B) = G, lcm(A,B) = L and (A+B) is as small as possible.

This is the approach I took during the match: The number of distinct prime factors for a number less than 10^12 is very low (Remembering last match, this number is definitely less than 15). We can extract prime factors of a number N in O(sqrt(N)) time. So, imagine we extracted the distinct prime factors of G and L, since by definition L is a multiple of G, then G will never have a prime factor that is not a prime factor of L. (If L is not a multiple of G, return -1 instantly). In fact, since we are talking about distinct prime factors, you also need, for each distinct factor, the number of times it appears as a factor of G and L. (For example, for G=40, the factorization is 2*2*2*5, 2 appears three times and 5 one time). Note that A and B both have to be multiples of G. This means that they both have to be multiples of each of the prime factors of G raised to the number of times the factor appears in G. The number of times a factor appears in L will be greater than or equal to the number of times it appears in G. This means that the minimum number of times a factor appears in A or B is equal to the number of times it appears in G. Similarly, the maximum number of times the factor appears in A or B is equal to the number of times it appears in L. Note that a factor cannot appear a number of times different to the minimum or the maximum (else the lcm rule wouldn't work). More so, if a factor appears the minimum number of times in A, it must appear the maximum number of times in B and viceversa.

So we have less than 15 prime factors and a decision, for each of them to place in A or B. You can just try all different 215 ways to make these decisions. For each of them, calculate A and B, then pick the minimum A+B possible.

//Death to long! 
typedef long long int64;
#define long int64
#define var(q,s) typeof(s) q = s
#define for_each(q, s) for( var(q,s.begin()); q!=s.end(); q++)
struct FoxAndGCDLCM
{
//Extract each prime factor,
// and the number of times it appears in x:
map<long, int> factorize(long x)
{
var(p, 2ll);
map<long, int> res;
//no need to check for a factor larger than sqrt(p)
while (p <= x / p) {
while (x % p == 0) {
res[p]++;
x /= p;
}
p ++;
}
if (x != 1) {
res[x]++;
}
return res;
}


long get(long G, long L)
{
if (L % G != 0) {
return -1;
}
var( gfactors, factorize(G));
var( lfactors, factorize(L));

pair<int, long> res = make_pair(1, -1ll);
//t different prime factors.
int t = lfactors.size();
// try each possible combination of decisions.
// 2^t in total (same as saying 1<<t).
for (int mask=0; mask<(1<<t); mask++) {
long A = G, B = G;
int i = 0; //so we know the index of the prime factor.
for_each(q, lfactors) {
long p = 1;
for (int j=gfactors[q->first]; j < q->second; j++) {
p *= q->first;
}
//decide...
if (mask & (1<<i)) {
A *= p;
} else {
B *= p;
}
i++;
}
res =std::min(res, make_pair(0, A+B) );
}
return res.second;


}
};
#undef long




That's the code I wish I coded, compare it with this monstrousity if you wish...

Now, that solution is still quite lame. Compare it with this one: L must be a multiple of G. Ok, now consider that A and B must be multiples of G. But what if we set a = A / G and b = B / G. Then a*b would hold all the factors that are not common to A nor B. a*b is also equal to L/G (try L = A*B / G as a base). Also notice that A+B = a*G + b*G = G * (a+b) and thus minimizing a*b yields the answer. Then since a*b are factors of L/G, you can just try all pairs (a,b) of numbers such that a*b = L/G (ie: extract the divisors of L/G in O(sqrt(L/G)). However, make sure the pairs (a,b) are coprime (again, else the lcm rule wouldn't hold). Notice that these two solutions do exactly the same thing... But the new solution looks like this:

//Death to long! 
typedef long long int64;
#define long int64

//Euclid's GCD
template<class T> T gcd(T a, T b)
{
while (b != 0) {
T c = b;
b = a % b;
a = c;
}
return a;
}

struct FoxAndGCDLCM
{
long get(long G, long L)
{
if (L % G != 0) {
return -1;
}
pair<int, long> res = make_pair(1, -1);
long ab = L/G;
// divisors of ab
for(long a=2; a <= ab/a; a++) {
if (ab % a == 0) {
//try all pairs (a,b)
long b = ab / a;
if (gcd(a,b) == 1) { //pair-wise coprime?
res = std::min(res, make_pair(0, (a + b)*G ) );
}
}
}
return res.second;
}
};
#undef long



Challenge phase et all
I had some ideas for div1 500, nothing concrete I think I will post something later. I avoid any challenge during the challenge phase.

Opinions?
The problems I opened seemed good. Div1 250 was fun. I was just too slow.

5 comments :

Guest said...

Nice explanation!

Petar Minchev said...

Does opening div1 500 first help? Maybe I will try it next SRM. When I open the 250 first, my brain is still not in a mood for a SRM and I am slower than usual most of the cases.

vexorian said...

It seemed to help for exactly that reason, since I go warmed up to 250, I tend to get better scores. But that's exactly the reason I pondered changing the strategy:
- Before SRM 535, I opened medium first, but "slowed up" which means that IF I got to solve the medium it would be for a low score.
- Other contests (ie: codeforces) reward solving the easiest problem first, which forced me to open it first, and I have been doing very bad because of slow solutions to the first problem...
- The score speed in 250 is nice, but the optimal solution would be to be 100% from the beginning to end of the match, and thus get good scores on both problems. That's what I am trying right now.

At first, I used the medium first strategy, not to do well in the matches but to get used to div1 mediums. As of now, that was accomplished, so I think I at this moment need to focus on the 100% thing.

Anuj Kalia said...

Hi vexorian!

Can you think of any alternate solution to 250 (other than bitmask)? i.e. how will you partition a set P={p1,p2,p3,...,pn} into 2 sets U and V such that A is the product of elements in U, B is the product of elements in V and A+B is minimum?

vexorian said...

Well, I do mention the solution that just needs a pair of divisors of L/G, but if you mean how to solve that sub-problem specifically, that's a good question. During the match I noticed many people doing a greedy-esque approach: Sort the elements in p, set A=1, B=1, then as long as there are elements in p, pick the largest unused element, if (A < B) then do A*=largest, else B*=largest. During the match I couldn't think of a way to break this approach, but it seems it is wrong. According to systests, that approach fails p={9,7,11,13,37,101,9901}

If the product of all the numbers of p was small enough, then bitmasks would always work well. If the product is high enough, then it seems hard to come up with a polynomial solution that doesn't use a potential product as part of the state.