problem statement
If you read the problem statement carefully, It's obvious that you have to check whether an undirected graph has an Eulerian tour or not, necessary and sufficient conditions for and undirected graph :
An undirected graph has a closed Euler tour if it is connected and each vertex has an even degree.
I do this using a simple dfs to count the number of components.
Thursday, December 15, 2011
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.
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.
Thursday, December 8, 2011
TopCoder - SRM 515 DIV 2 - RotatedClock - getEarliest
After I read the problem statement, I didn't find out what's going on :-D. I think the most important part of the problem for me was these two sentences : "The clock has a scale marked in 30 degree increments ... She measured the angles of hands from a certain mark". Before I pay attention to these two sentences, I was confused of test case 3, I was thinking why 19 19 is impossible? Then I found that measured degrees are from a certain mark, so both of them can not be 19 19, but of course both of them can be 0 0, 30 30, 60 60, 90 90 ...
At first I was trying to solve the problem in this way : Which mark has she chosen to measure the degrees? 0? 30? 60? 90? 120? 150? 180? 210? 240? 270? 300? 330? I thought that I could map one of the degrees to one of these 12 origins, then map the other one, and check whether the resulted degrees show a true time? then I figured out that it's a little hard to implement. I tried to reverse my approach. I iterated h = 0 to 12 and m = 0 to 60 and each time I made mDegree and hDegree, at this moment I have to verify whether mDegree and hDegree is an answer or not? So I shifted both of them 0 degrees, 30 degrees, 90 degrees, 120 degrees, ... 330 degrees and checked whether they matched input or not, if yes I had found the answer. But at this time I checked though my approach seems true but test case 2 gave me time 07:01 that's 210 degrees and 6 degrees that if I add 30 to both of them it becomes 240 and 36 that matches test case 2, I read the problem statement again and I found that her measurement device supports integer degrees not real numbers, because 07:01 is not 210 degrees and 6 degrees, it is 210.5 and 6. So I added another condition to my program that if minute was odd it is not my answer. And Finally Accepted :-).
At first I was trying to solve the problem in this way : Which mark has she chosen to measure the degrees? 0? 30? 60? 90? 120? 150? 180? 210? 240? 270? 300? 330? I thought that I could map one of the degrees to one of these 12 origins, then map the other one, and check whether the resulted degrees show a true time? then I figured out that it's a little hard to implement. I tried to reverse my approach. I iterated h = 0 to 12 and m = 0 to 60 and each time I made mDegree and hDegree, at this moment I have to verify whether mDegree and hDegree is an answer or not? So I shifted both of them 0 degrees, 30 degrees, 90 degrees, 120 degrees, ... 330 degrees and checked whether they matched input or not, if yes I had found the answer. But at this time I checked though my approach seems true but test case 2 gave me time 07:01 that's 210 degrees and 6 degrees that if I add 30 to both of them it becomes 240 and 36 that matches test case 2, I read the problem statement again and I found that her measurement device supports integer degrees not real numbers, because 07:01 is not 210 degrees and 6 degrees, it is 210.5 and 6. So I added another condition to my program that if minute was odd it is not my answer. And Finally Accepted :-).
TopCoder - SRM 515 DIV 2 - FortunateNumbers - getFortunate
As you can see in the problem statement just a simple brute force is enough to pass the time limit. I produce all combinations of a[i] + b[j] + c[k] for all i, j, k and check whether it is a fortunate number or not, if yes I insert the number in a set and finally I return the size of the set.
Sunday, December 4, 2011
TopCoder - SRM 144 DIV 1 - Lottery - sortByOdds
If you read the problem statement carefully, you'll find out that we are facing 'blanks' spots that in each spot we can put [1, 'choices'], for simplicity n = blanks, up = choices
I categorize this problem as a counting problem in Combinatorics.
We can break this problem to 4 independent subproblems :
Case 1 : if sorted = false and unique = false, there is no condition, we want to fill each spot, and each spot has up candidates, so the answer is :
(up * up * ... * up)[n times] = up^n
Case 2 : if sorted = false && unique = true, what we put in n spots have to be unique, we have to choose n numbers out of up numbers and put all of the permutations of these numbers in the n spots so the answer is :
combination(up, n) * n! = ( (up!) / ((up-n)! * n!) )* n! = up! / (up-n)! = permutation(up, n)
Case 3 : if sorted = true && unique = true, what we put in spots have to be unique and sorted, so we have to choose n numbers out of up numbers and put the sorted version of this combination in the n spots, so the answer is :
combination(up, n) = up! / ((up-n)! * n!)
Case 4 : if sorted = true && unique = false, at this case suppose we have an array of size n and we want to fill the spots with numbers in range [1, up] and they have to be non-decreasing. e. g. n = 3 & up = 5 then [1, 2, 3], [1, 1, 1], [1, 2, 2], [5, 5, 5] and .... have to be counted in this case.
So we want the number of sorted arrays that are filled with numbers in range [1, up]. I tried to find a recurrent formula for this, think of the array like this that from left to right the indices decrease from n to 1, a[n], a[n-1], a[n-2] ... a[2], a[1]
mem(k, low) is the number of sorted arrays that start from index k and what we can put in this spot is at least low and at most up, what can we do to break the problem? Each time we can put a number at spot k and invoke mem(k-1, something), but what is 'something'? Yes, each time we put T = low...up and call mem(k-1, T), in this way we fix spot number k to T and tell the next index that you can be at least as T because I have fixed previous spot T, so mem(k, low) = mem(k-1, low) + mem(k-1, low+1) + mem(k-1, low+2) + ... + mem(k-1, up-1) + mem(k-1, up)
What is the trivial case? if k is 1(when we have just 1 spot) how many ways can we fill this spot? There are (up-low+1) ways to fill this spot. So the answer is :
mem(n, 1)
At this case we have to memoize the answer to prevent from a "Time Limit Exceeded" verdict.
To calculate combination(n, k) we have a recurrent formula that says combination(n, k) = combination(n-1, k-1) + combination(n-1, k), I also memoized this.
n! = n * (n-1)! -->> I memoized this too.
To calculate p^n, I wrote a function to calculate it in O(logn) with the fact that p^n = p^(n/2) * p^(n/2)
:-D But the problem wants something more than what I described. We have to parse the input and produce output. We need a struct like pair or something like that.
I described a struct by myself :
struct str
{
int p;
string name;
str(int _p = 0, string _name = "")
{
p = _p, name = name;
}
bool operator<(const str &two) const
{
return p < two.p && (p == two.p && name < two.name);
}
};
I parsed input like this
string &s = rules[i];
string name = s.substr(0, s.find(':'));
string rest = s.substr(s.find(':')+1, 1000);
then I stringstream 'rest' and token up, n, sorted, unique.
then calculate probability, sort and produce output.
I categorize this problem as a counting problem in Combinatorics.
We can break this problem to 4 independent subproblems :
Case 1 : if sorted = false and unique = false, there is no condition, we want to fill each spot, and each spot has up candidates, so the answer is :
(up * up * ... * up)[n times] = up^n
Case 2 : if sorted = false && unique = true, what we put in n spots have to be unique, we have to choose n numbers out of up numbers and put all of the permutations of these numbers in the n spots so the answer is :
combination(up, n) * n! = ( (up!) / ((up-n)! * n!) )* n! = up! / (up-n)! = permutation(up, n)
Case 3 : if sorted = true && unique = true, what we put in spots have to be unique and sorted, so we have to choose n numbers out of up numbers and put the sorted version of this combination in the n spots, so the answer is :
combination(up, n) = up! / ((up-n)! * n!)
Case 4 : if sorted = true && unique = false, at this case suppose we have an array of size n and we want to fill the spots with numbers in range [1, up] and they have to be non-decreasing. e. g. n = 3 & up = 5 then [1, 2, 3], [1, 1, 1], [1, 2, 2], [5, 5, 5] and .... have to be counted in this case.
So we want the number of sorted arrays that are filled with numbers in range [1, up]. I tried to find a recurrent formula for this, think of the array like this that from left to right the indices decrease from n to 1, a[n], a[n-1], a[n-2] ... a[2], a[1]
mem(k, low) is the number of sorted arrays that start from index k and what we can put in this spot is at least low and at most up, what can we do to break the problem? Each time we can put a number at spot k and invoke mem(k-1, something), but what is 'something'? Yes, each time we put T = low...up and call mem(k-1, T), in this way we fix spot number k to T and tell the next index that you can be at least as T because I have fixed previous spot T, so mem(k, low) = mem(k-1, low) + mem(k-1, low+1) + mem(k-1, low+2) + ... + mem(k-1, up-1) + mem(k-1, up)
What is the trivial case? if k is 1(when we have just 1 spot) how many ways can we fill this spot? There are (up-low+1) ways to fill this spot. So the answer is :
mem(n, 1)
At this case we have to memoize the answer to prevent from a "Time Limit Exceeded" verdict.
To calculate combination(n, k) we have a recurrent formula that says combination(n, k) = combination(n-1, k-1) + combination(n-1, k), I also memoized this.
n! = n * (n-1)! -->> I memoized this too.
To calculate p^n, I wrote a function to calculate it in O(logn) with the fact that p^n = p^(n/2) * p^(n/2)
:-D But the problem wants something more than what I described. We have to parse the input and produce output. We need a struct like pair
I described a struct by myself :
struct str
{
int p;
string name;
str(int _p = 0, string _name = "")
{
p = _p, name = name;
}
bool operator<(const str &two) const
{
return p < two.p && (p == two.p && name < two.name);
}
};
I parsed input like this
string &s = rules[i];
string name = s.substr(0, s.find(':'));
string rest = s.substr(s.find(':')+1, 1000);
then I stringstream 'rest' and token up, n, sorted, unique.
then calculate probability, sort and produce output.
Subscribe to:
Posts (Atom)