Saturday, March 31, 2012

Topcoder Open 2012 round 1A

This is what I wrote for the official TCO blog:

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[0] );
    // Count how many times a player exists:
    map<string,int> cnt;
    for_each(p, players) {
    // Add those guys with more than 2 instances to the result:
    vector<string> res;
    for_each(x, cnt) {
    if (x->second >= 2) {
    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) {
    // (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: 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.

No comments :