Wednesday, December 14, 2011

UVA - 11099 - Next Same-Factored

problem statement
After I read the problem statement, I tried to code the first solution that came to my mind, please do not laugh at me for my bad solution :-D, this solution is because I misunderstood the problem statement, my first approach was this : I tried to find the smallest prime factor of n, and output n*smallest factor, but very soon I found that output of 12 is not 12*2 but it's 18, cause 12 = 2^2*3, 24 = 2^3*3 and 18 = 2*3^2, So after I was disappointed for a moment, I tried to think of a new algorithm, and after some nonsense approaches I found that I have to precalculate a list for each number in range 1-10^6 that shows it's factors, and sort them, then whenever I read a number I can check next number in the sorted list, and check whether it's list is equal to the input list or not, if yes print that, and if not print "Not Exist!", I did this, at first run it took 12 seconds to run, and I know what the problem was, that was because of sorting a list which has vectors, I was sure this solution is gonna end with accepted, but don't know how, thinking and  thinking..., I found that I have to remove vector, and put something else instead to reduce running time, at this time I remembered hashing :-D the key to solve the problem in my approach came along, and I was happy ;-).
I have a hash function like this :
int hash(string &s)
{
int res = 0;
for(int i = 0; i < s.size(); i ++)
res = res*127 + s[i];
return res;
}
e.g. hash("abcd") = a*127^3 + b*127^2 + c*127^1 + d
and hash("abc") = a*127^2 + b*127^1 + c
6 => 2-3
12 => 2-3
18 => 2-3
24 => 2-3
36 => 2-3
.....
if look at their list like a string and produce their hash, all of them will have the same hash value and when I sort them they will be neighbor, hashValue( 6 ) = 2*127^2 + 3 = hashValue( 12 ) = hashValue( 18 ) = ...
I tried to build these hash values in a bottom-up manner, like this :
#define ll long long
for(ll i = 0; i < prime.size(); i ++)
{
ll curP = prime[i];
for(ll j = curP; j < SIZE; j += curP)
all[j].hash = all[j].hash*1046527 + curP;
}

but at first 1046527 was 127 and I got wrong answer, that was because some numbers hash value was a prime number and that would produce a problem, after I changed 127 I got accepted and running time was about 1 second.