problem statement
In this problem you have to count the number of nonesquare rectangles in a given rectangle.
What I do is this, that I try to count all of
1*2, 1*3 ... 1*w
2*3, 2*4.... 2*w
......................
rectangles.
and I do this once for my rectangle and another time with the new rectangle with width and height swapped.
this is my code:
long long func(int w, int h)
{
long long res = 0;
for(int i = 1; i <= h; i ++)
for(int j = i+1; j <= w; j ++)
res += (wj+1) * (hi+1);
return res;
}
long long countRectangles(int w, int h)
{
return func( w, h ) + func( h, w );
}
How did I find this solution? I just tried to check it out on a piece of paper and I saw that there is a template for placing the rectangles with different width and heights in a larger rectangle.
For example if you want to place a 1*2 rectangle in a large rectangle, first you have to count how many of them are placed in a single row, (width2+1) and multiply this number in height that is the number of 1*2 rectangles that are placed horizontally in a rectangle.
There are another solutions that I'm thinking about them, using 4 and 3 loops that I think they are trivial, and using 1 loop or even no loop that I'm thinking to understand them completely, then I'm gonna add them here.
I describe my solution or give some hints about the solution for algorithmic problems used in ICPC or online sites for programming contests.
Wednesday, January 12, 2011
Tuesday, January 4, 2011
TopCoder  SRM 145 DIV 1  Bonuses  getDivision
problem statement
This is a straight forward simulation problem. As described in the problem statement you find each persons percentage amounts and then you have to distribute the left over percentage among those who have greater points and if they have equal points, give extra 1% to who comes first in input and of course keep track of this person not to give extra 1% to him again.
vector getDivision(vector p)
{
int n = p.size();
vector out( n );
int sum = accumulate( p.begin(), p.end(), 0 );
for(int i = 0; i < n; i ++)
out[i] = p[i]*100 / sum;
int sum2 = accumulate( out.begin(), out.end(), 0 );
vector mark(n, 0);
for( ; sum2 < 100; sum2 ++)
{
int mx = 1, id = 0;
for(int j = 0; j < n; j ++)
if( mx < p[j] && mark[j] == 0 )
mx = p[j], id = j;
out[id] ++, mark[id] = 1;
}
return out;
}
This is a straight forward simulation problem. As described in the problem statement you find each persons percentage amounts and then you have to distribute the left over percentage among those who have greater points and if they have equal points, give extra 1% to who comes first in input and of course keep track of this person not to give extra 1% to him again.
vector
{
int n = p.size();
vector
int sum = accumulate( p.begin(), p.end(), 0 );
for(int i = 0; i < n; i ++)
out[i] = p[i]*100 / sum;
int sum2 = accumulate( out.begin(), out.end(), 0 );
vector
for( ; sum2 < 100; sum2 ++)
{
int mx = 1, id = 0;
for(int j = 0; j < n; j ++)
if( mx < p[j] && mark[j] == 0 )
mx = p[j], id = j;
out[id] ++, mark[id] = 1;
}
return out;
}
TopCoder  SRM 145 DIV 2  DitherCounter  count
problem statement
In this problem you have to count how many of the characters of screen exist in dithered, to do this you can loop over the elements of screen and then for each element of screen search in dithered whether that character is there or not, O( n^3 ). But I do this O( n^2 ), since characters are only uppercase letters, at first I mark which characters are there in dithered, and then loop over screen and for each character it takes O( 1 ) to check whether it is in dithered or not.
In this problem you have to count how many of the characters of screen exist in dithered, to do this you can loop over the elements of screen and then for each element of screen search in dithered whether that character is there or not, O( n^3 ). But I do this O( n^2 ), since characters are only uppercase letters, at first I mark which characters are there in dithered, and then loop over screen and for each character it takes O( 1 ) to check whether it is in dithered or not.
TopCoder  SRM 144 DIV 1  BinaryCode  decode
problem statement
The problem sounds a little bit tricky at first but the test cases show you what you have to do. At first, when you assume about the first element of source to be '0' or '1', you can find the rest of them easily. But while doing this you have to take care about what you are pushing back into source, if it is some characters other than '0' or '1' the answer for this assumption is "NONE", and at the end I try to rebuild q from my result and see whether this q is equal to the given q or not? Why? Cause source[q.size()] must be equal to '0' because it's outside the string. There is one other way to do this, that while you are constructing source from given q, check whether source[q.size()] is equal to '0' or not, and there is no need to rebuild q from source.
This function returns the ith element of string s, if i is out of range returns 0
int f( string &s, int i )
{
if(i < 0  i >= s.size() )
return 0;
return s[i]'0';
}
This function checks whether the source that I've decoded is valid or not, by checking whether it has characters other than '0' and '1' or not, and checking that if I build q from s, is it equal to the given q or not?
bool valid( string &s, string &q )
{
for(int i = 0; i < s.size(); i ++)
if( s[i] != '0' && s[i] != '1' )
return false;
string t(q.size(), '0');
for(int i = 0; i < s.size(); i ++)
t[i] = f(s, i1) + f(s, i) + f(s, i+1) + '0';
if( q != t )
return false;
return true;
}
The problem sounds a little bit tricky at first but the test cases show you what you have to do. At first, when you assume about the first element of source to be '0' or '1', you can find the rest of them easily. But while doing this you have to take care about what you are pushing back into source, if it is some characters other than '0' or '1' the answer for this assumption is "NONE", and at the end I try to rebuild q from my result and see whether this q is equal to the given q or not? Why? Cause source[q.size()] must be equal to '0' because it's outside the string. There is one other way to do this, that while you are constructing source from given q, check whether source[q.size()] is equal to '0' or not, and there is no need to rebuild q from source.
This function returns the ith element of string s, if i is out of range returns 0
int f( string &s, int i )
{
if(i < 0  i >= s.size() )
return 0;
return s[i]'0';
}
This function checks whether the source that I've decoded is valid or not, by checking whether it has characters other than '0' and '1' or not, and checking that if I build q from s, is it equal to the given q or not?
bool valid( string &s, string &q )
{
for(int i = 0; i < s.size(); i ++)
if( s[i] != '0' && s[i] != '1' )
return false;
string t(q.size(), '0');
for(int i = 0; i < s.size(); i ++)
t[i] = f(s, i1) + f(s, i) + f(s, i+1) + '0';
if( q != t )
return false;
return true;
}
TopCoder  SRM 144 DIV 2  Time  whatTime
problem statement
In this problem, you have to convert a given second into it's equivalent standard time "h:m:s".
Easily I find how many 3600 are there in it, how many 60 are there left in it, and now I have h, m and s that I have to return a string not integers, so I convert each of them into a string and add them together in one string and return it.
Function f(int) just converts the given integer into a string like this:
int f( int n )
{
if( n == 0 )
return "0";
string res = "";
while( n )
{
res += n%10 + '0';
n /= 10;
}
reverse( res.begin(), res.end() );
return res;
}
In this problem, you have to convert a given second into it's equivalent standard time "h:m:s".
Easily I find how many 3600 are there in it, how many 60 are there left in it, and now I have h, m and s that I have to return a string not integers, so I convert each of them into a string and add them together in one string and return it.
int h = seconds/3600; int m = (seconds%3600)/60; int s = seconds%60;return f(h) + ":" + f(m) + ":" + f(s);
Function f(int) just converts the given integer into a string like this:
int f( int n )
{
if( n == 0 )
return "0";
string res = "";
while( n )
{
res += n%10 + '0';
n /= 10;
}
reverse( res.begin(), res.end() );
return res;
}
Subscribe to:
Posts (Atom)
USACO  Prime Palindromes
I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...

Let's think about it, Have you noticed the small boundary of N & M, What can we do with this small boundary? Isn't producing al...

Mathematics As you can see in the problem description, you have to find numbers a & b such that (a, b) = G and [a, b] = L and also it ...

I don't know why, but I had a great misunderstanding of the problem statement from this sentence "FJ pours milk from one bucket t...