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[0] ); 
          } 
          // 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.