TurtleShip's blog

A website to share solutions to coding competitions.
By TurtleShip, history, 9 years ago, In English

Hello, folks.

I built a website to share solutions to coding competitions, including Codeforces, TopCoder, and UVa Online Judge.

The site is http://codingyard.com/

I've been working on it as a side project, and it is completely free to use. I pay the bills and will continue to pay it.

If people can pay a visit, sign up, and leave some feedback, I would much appreciate it!

Even though Codeforces already provide a way to view past solutions, I built the website for below reasons

1) A centralized place to store solutions to multiple contests.

I think many people who do competitive programming participate in multiple compeititons — Codeforces, TopCoder, Google Code Jam, etc. I plan to support uploading solutions as many different competitions as possible. I eventually want to turn my website into a community where people can come to share solutions to any competitions.

2) Some competition sites don't show previously submitted solutions. One example is UVa Online Judge. Sometimes I would get stuck on a problem and I really wish I could see other people's solutions so that I see other possible approaches.

Full text and comments »

  • Vote: I like it
  • +19
  • Vote: I do not like it

My solutions to CROC Qualification Round
By TurtleShip, 13 years ago, In English

Hi,

I posted my solutions to all 5 problems with explanations in my blog http://sk765.blogspot.com/2012/04/croc-champ-2012-qualification-round.html

I tried to upload the content in codeforces blog, but I failed.

I wrote the editorial so that I can better understand problems I solved and possibly receive feedbacks on my approach. And it would be great if anybody could benefit from my blog.

Please feel free to give me feedbacks.

Have an awesome day :-)

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

Editorial Round #106
By TurtleShip, 13 years ago, In English

This was my first time to participated in Codeforces (http://www.codeforces.com/)  , an online programming contest site.

This is a link explaining rules about the contest : http://mirror.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://mirror.codeforces.com/contest/149

And here is the link to my blog : : http://sk765.blogspot.com/

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;
}


Problem B — Martian Clock


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;
}


Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it