## 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.