This is a link explaining rules about the contest : http://codeforces.com/blog/entry/456
During the contest, I made a newbie mistake of resubmitting the same solution twice because I didn't understand what "judgement failed." meant. I thought it was something like "compilation error." Only after resubmitting my solution did I learn that "judgement failed" meant "there is something wrong with our server. Please wait a while we fix this issue." I lost about 100 points for that mistake.
But other than that, things went okay.
I solved three problems out of five - A , B, and C.
Here is the link to problem statement : http://codeforces.com/contest/149
Problem A - A Business trip
Algorithm
Our main character, Petya, wants to water her plant as few time as possible while still achieving the goal of making her plant grow more than or equal to k centimeters.
We can use a greedy approach. Follow below steps
1. Sort month by how many centimeters they can make a flower grow in ascending order.
2. Pick the month with the largest growth value, and add it to variable named "sum".
3. Repeat procedure 2 until value of "sum" >= k
Source code
int main()
{
int k;
vector<int> water;
cin>>k;
for(int i=0; i < 12; i++)
{
int temp;
cin>>temp;
water.push_back(temp);
}
int N = water.size();
sort(water.begin(), water.end());
int sum = 0;
int month = 0;
bool found = false;
if(k == 0){
cout<<0<<endl;
found = true;
}
for(int i=N-1; i >= 0 && !found; i--)
{
sum += water[i];
month++;
if(sum >= k)
{
cout<<month<<endl;
found = true;
break;
}
}
if(!found)
cout<<-1<<endl;
return 0;
}
Algorithm
1. Determine whether the given input has infinite number of bases or not. If it does, output -1. If it has a finite number of valid base, move to step 2.
2. Starting from a minimum valid base, keep increasing base by one until you reach a base that is not valid.
Explanation
Q1 : How do I determine whether the given input has an infinite number of bases or not?
Let's first observe the obvious : the first digit of a number is not affected by base.
To illustrate, let's take a look at number 4.
4 in base 5 is 4.
4 in base 6 is 4.
4 in base 7 is 4.
...
4 in base 58 is 4.
....
More formally,
x in base y
= x * y^0
= x * 1
= x where x is a single integer.
So if both hour and minute are single characters, the given input has infinite number of bases IF they are valid time.
For example, B:9 is a valid time in any base, because it will be 12:09 in any base above base 13.
However, Z:9 is not a valid time in any base because it will be 35:09 in any valid base.
Note that once we verify that both hour and minute are single characters, we only have to check the validity of hour because maximum number a single character can represent in 'Z', or 35, which is a valid number for minute.
Q2 : Once we determine that the given input has a finite number of bases, how do we find the minimum valid base?
Note that in base x , the highest number you can have at each digit is (x-1).
For example, in base 10, the highest number you can have at each digit is 9.
If you reverse the above statement, you can find out that if the highest number you have at each digit is x-1, the minimum valid base is x.
So go through each character in the input, find the highest single character x, and the minimum valid base is x+1.
Source code
int toInt(char ch)
{
if('0' <= ch && ch <= '9')
return (ch - '0');
return (ch - 'A' + 10);
}
int toDecimal(string num, int b)
{
int result = 0;
int mult = 1;
for(int i=(num.size() - 1); i >= 0; i--)
{
result += toInt(num[i]) * mult;
mult *= b;
}
return result;
}
int main()
{
string input;
cin>>input;
bool found = false;
int hourSt = -1;
int mid = 0;
int minSt = -1;
for(int i=0; i < input.size(); i++)
{
if(input[i] == ':')
{
mid = i;
break;
}
}
for(int i=0; i < mid; i++)
{
if(input[i] != '0')
{
hourSt = i;
break;
}
}
for(int i=mid+1; i < input.size(); i++)
{
if(input[i] != '0')
{
minSt = i;
break;
}
}
string HH = (hourSt == -1) ? "0" : input.substr(hourSt,(mid-hourSt));
string MM = (minSt == -1) ? "0" : input.substr(minSt);
/*
infinite case is when both number are single digit.
*/
bool isValid = true;
if( HH.size() == 1 && MM.size() == 1)
{
if(toInt(HH[0]) >= 24)
cout<<0;
else
cout<<-1;
isValid = false;
}
int base = 0;
for(int i=0; i < HH.size(); i++)
{
base = max(base, toInt(HH[i]));
}
for(int i=0; i < MM.size(); i++)
{
base = max(base, toInt(MM[i]));
}
base++;
int count = 0;
if(toDecimal(HH, base) < 24 && toDecimal(MM,base) < 60 && isValid)
{
count++;
cout<<base;
}
base++;
while(true && isValid)
{
if(toDecimal(HH, base) < 24 && toDecimal(MM,base) < 60)
{
cout<<" "<<base;
base++;
count++;
}
else break;
}
if(count==0 && isValid)
cout<<"0";
return 0;
}
Problem C - Division into Teams
The problem statement states that it is guaranteed that a fair division into two teams always exists.
This means there is always an optimal solution, and we can start by how the optimal solution looks like.
There are three conditions that the optimal solution meets
- #1 Each boy plays for exactly one team (x + y = n).
- #2 The sizes of teams differ in no more than one (|x - y| ≤ 1).
- #3 The total football playing skills for two teams differ in no more than by the value of skill the best player in the yard has. More formally:
#1 and #2 tell us that each team took turns picking a player.
#3 tells that after picking players, the team who went first (who picked the best player and possibly one more player than the other player) gave one or two players away to the other team to balance each team's skills. Since there is always an optimal solution, we don't have to worry about giving too many players away.
Algorithm
Let there be team X and team Y.
1. Sort all players by their skills in descending order.
2. Each team picks player. Team X goes first. Each team will obviously pick the best available player.
3. After picking all players, team X will give the worst player that is has away to team Y until formula in #3 is met.
Source Code
int main()
{
int n;
cin>>n;
vector< pair<int,int> > boys;
for(int i=1; i <= n; i++)
{
int temp;
cin>>temp;
boys.push_back(make_pair(temp,i));
}
sort(boys.begin(), boys.end());
vector< pair<int,int> > x;
vector< pair<int,int> > y;
long long xSum = 0;
long long ySum = 0;
long long maxP = boys[n-1].first;
for(int i=(n-1); i >= 0; i--)
{
if(i%2 == 0)
{
x.push_back( boys[i] );
xSum += boys[i].first;
}
else
{
y.push_back( boys[i] );
ySum += boys[i].first;
}
}
while( (xSum - ySum) > maxP && abs( int(x.size() - y.size()) ) <= 1)
{
int point = x[0].first;
int num = x[0].second;
x.erase(x.begin());
xSum -= point;
ySum += point;
y.push_back( make_pair(point,num));
}
cout<<x.size()<<endl;
for(int i=0; i < x.size(); i++)
{
cout<<x[i].second<<" ";
}
cout<<endl;
cout<<y.size()<<endl;
for(int i=0; i < y.size(); i++)
{
cout<<y[i].second<<" ";
}
cout<<endl;
return 0;
}
No comments:
Post a Comment