Saturday, March 31, 2012

Topcoder Open 2012 round 1A

This is what I wrote for the official TCO blog: http://community.topcoder.com/tco12/algorithm-track-round-1a/.

More things to say:
• Cute codes for 250 and 500:
#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct EllysJuice
{
vector <string> getWinners(vector <string> players)
{
if (players.size() == 1) {
//special case with one turn, the only player wins.
return vector<string>(1, players );
}
// Count how many times a player exists:
map<string,int> cnt;
for_each(p, players) {
cnt[*p]++;
}
// Add those guys with more than 2 instances to the result:
vector<string> res;
for_each(x, cnt) {
if (x->second >= 2) {
res.push_back(x->first);
}
}
sort(res.begin(), res.end());
return res;
}
};

// long long once killed a kitten.
typedef long long int64;
#define long int64
#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
struct EllysFractions
{

long getCount(int N)
{
long pn = 0;
long res = 0;
set<int> primes;
for (int x=2; x<=N; x++) {
// is x prime?
bool isprime = true;
for_each(p, primes) {
isprime &= ( (x % (*p) ) != 0);
}
// Yes. Yes, it is...
if (isprime) {
pn++;
primes.insert(x);
}
// (2 raised to the pn-th) / 2 is the number
// of fractions for x!
res += (1LL << pn)/2;
}
return res;
}
};
#undef long

• The problem in which you have to split numbers from 1-N in two parts and one must be denominator and one numerator is a interesting problem by itself. That's the problem I actually solved during the match. It took me 10 minutes to solve this problem and 100 minutes to figure out it was the wrong problem, so I spent most of the match trying to find out why was my solution returning such wrong value for N=100 (By the way, I see no reason at all not to allow a smaller number like 6 but larger than 5, in the example cases other than make people go wrong with this).

• Once I got desperate and it seemed like I was not going to solve the 500, I switched to 1000. And it seemed like I had solved the problem before and in TopCoder. But I had no idea how to solve it anymore and I could not find the old problem. So far the main suspect is round 306's div1 medium but it is actually a bit different. Maybe it was just a bugged Dejavu.

In my attempts to find the solution to it through google I found this: http://www.ripon.edu/academics/macs/summation/2010/articles/M.%20Madsen%20-%20Lights%20Out.pdf. Interesting.

• Blogger has updated its interface and: BOY IT SUCKS ARGGGGGGGGGHHH IT SUCKS IT SUCKS IT SUCKS. Thanks I needed to get it out of my system.

Seriously, what is Google's problem? This is starting to look like I wasn't exaggerating when I said google was starting a war on color. Worse, google is going backwards now and blogger's interface is actually worse in small screens (buttons don't show up when you edit an entry) than before.