TC SRM 487 D1-500 KiwiJuice

Category: Dynamic Programming
URL: http://www.topcoder.com/stat?c=problem_statement&pm=11019

class KiwiJuice {
public:
   int theProfit(int, vector <int>, vector <int>);
};

int dp[51][1<<16];
vector<int> data;
vector<int> price;
int _C;

// f(current volume of the special bottle, bitmask of the used bottles)
int f(int i, int mask) {
   // caching mechanism
   if (dp[i][mask] != -1) return dp[i][mask];
   // base case
   if (mask+1 == (1 << (data.size()))-1) {
      return price[i];
   }
   int res = 0;
   for (int j = 1; j < data.size(); j++) {
      if (mask & (1 << j)) continue;   // already used
      // the next bottle to process
      int next = data[j];
      int d1 = 0;
      if (i + next >= _C) {
         // one of the bottles is full, the other is i+next-_C volume
         d1 = price[_C] + f(i+next-_C, mask | (1 << j));
      } else {
         // change to i + next (and used up the empty for bottle[j])
         d1 = price[0] + f(i+next, mask | (1 << j));
      }
      // don't add more to our current bottle
      // we swap with bottle j and "use" up our bottle
      int d2 = f(next, mask | (1 << j)) + price[i];
      
      // take the maximum of the decision branches
      res >?= max(d1,d2);
   }
   return dp[i][mask] = res;
}

int KiwiJuice::theProfit(int C, vector <int> bottles, vector <int> prices) {
   price = prices;
   int res = 0;
   _C = C;
   memset(dp,-1,sizeof(dp));
   data = bottles;
   return res = f(data[0],0);   // arbitrarily assign bottle 0 to be our special bottle
}

TC SRM 487 D1-250 CarrotJumping

Category: Brute Force, Mathematics
URL: http://www.topcoder.com/stat?c=problem_statement&pm=11022

class CarrotJumping {
public:
   int theJump(int);
};

long long MOD = 1000000007;

// compute 2^n (mod MOD)
long long pow(int v) {
   if (v == 0) return 1;
   if (v == 1) return 2;
   long long x = pow(v/2);
   if (v % 2 != 0) return (x * x * 2) % MOD;
   return (x * x) % MOD;
}

int CarrotJumping::theJump(int init) {
   int res = 100001;
   for (int a = 0; a <= 100000; a++) {
      for (int b = 0; b < 3; b++) {
         long long v = pow(a*3 + b*2);
         long long c = (v * init + (v - 1 + MOD) % MOD) % MOD;
         if (c == 0) {
            res <?= (a + b);
         }
      }
   }
   return res >= 100001 ? -1 : res;
}