TopCoder SRM 511

I solved Easy and Meidum. But I made careless mistake in Easy and got only 75pts by resubmission. My place was 135th and my rating stayed.

Rating: 2237 -> 2237 (+-0)

Link to TopCoder(login required)

250 Zoo

Cats' answers should be {0, 1, ..., C-1} and rabbits' answers should be {0, 1, ..., R-1} if there are at least one valid configurations. Then the answer to the problem is 1<<(min(R, C)+1 + (R==C?0:1)).

My code was dirty and not good...

Solution in C++ (in the contest)

class Zoo {
public:
  long long theCount(vector <int> answers) {
    sort(answers.begin(), answers.end());
    map<int, int> cnt;
    for(int i=0; i<(int)answers.size(); ++i)
      cnt[answers[i]]++;
    int a=-1;
    for(int i=0; ; ++i) {
      if(cnt[a+1]>=1) {
        a++;
        cnt[a]--;
      } else break;
    }
    int b=-1;
    for(int i=0; ; ++i) {
      if(cnt[b+1]>=1) {
        b++;
        cnt[b]--;
      } else break;
    }
    for(map<int, int>::iterator it=cnt.begin(); it!=cnt.end(); ++it)
      if(it->second >= 1)
        return 0;
    if(a==-1 || b==-1) return 2;
    if(a-b==1 || b-a==1) return 1ll<<max(a+1,b+1);
    return 1ll<<min(a+1,b+1);
  }
};

500 FiveHundredEleven

This problem can be solved by DP. The key idea is that, if we know the current value of the memory and the number of used cards, we can figure out what cards are unused. So the state is: dp[mem][n] := whether a player can win if the player starts the game from the state that memory's value equals to mem and n cards were used.

My implementation is memoized recursion.

Solution in C++ (in the contest)

class FiveHundredEleven {
public:
  int N;
  vector<int> C;
  int dp[51][512]; // ciel ga kateruka

  int rec(int used, int mask) {
    if(mask == 511)
      return 1;
    if(dp[used][mask] >= 0)
      return dp[used][mask];
    int& ret = dp[used][mask];

    vector<int> remain;
    int muda = 0;
    for(int i=0; i<N; ++i)
      if((C[i] | mask) == mask)
        muda++;
      else
        remain.push_back(C[i]);
    muda -= used;
    for(int i=0; i<muda; ++i)
      remain.push_back(0);

    for(int i=0; i<(int)remain.size(); ++i) {
      int u = remain[i];
      if(rec(used+1, mask|u) == 0)
        return ret = 1;
    }
    return ret = 0;
  }

  string theWinner(vector <int> cards) {
    int all = 0;
    for(int i=0; i<(int)cards.size(); ++i)
      all |= cards[i];
    if(all != 511)
      return cards.size()%2 ? "Fox Ciel" : "Toastman";

    for(int i=0; i<=50; ++i)
      for(int j=0; j<512; ++j)
        dp[i][j] = -1;

    N = cards.size();
    C = cards;
    return rec(0, 0) ? "Fox Ciel" : "Toastman";
  }
};

TopCoder SRM 508

I solved Easy and Medium. Since I'm not good at geometry and flow, I wasn't able to solve Hard though I had 40 minutes to try it. Anyway, my rating increased because I've solved Medium not too slow.

Rating: 2269 -> 2318 (+49)

Link to TopCoder (login required)

250 DivideAndShift

I came up with an idea that dividing operations and shifting operations can be separated as soon as I read the statement. My solution is: trying all patterns of dividing operations and then performing shifting operations to achieve the goal.

Solution in C# (in the contest)

using System; 
using System.Text; 
using System.Text.RegularExpressions; 
using System.Collections; 
using System.Collections.Generic; 

public class DivideAndShift { 
    public int getLeast(int N, int M) { 
        int res = int.MaxValue; 
        int P = 0, T = N; 
        for (int i = 2; i * i <= T; ++i) 
        { 
            while (T % i == 0) 
            { 
                P++; 
                T /= i; 
            } 
        } 
        if (T > 1) P++; 
        M--; 
        for (int i = 1; i <= N; ++i) 
        { 
            if (N % i == 0) 
            { 
                int cnt = 0; 
                int p = 0, t = i; 
                for (int j = 2; j * j <= t; ++j) 
                { 
                    while (t % j == 0) 
                    { 
                        p++; 
                        t /= j; 
                    } 
                } 
                if (t > 1) p++; 
                cnt = P - p; 
                cnt += Math.Min(M % i, i - M % i); 
                res = Math.Min(res, cnt); 
            } 
        } 
        return res; 
    } 
} 

500 YetAnotherORProblem

This problem can be solved by bit DP. The state is: dp[u][b] = the number of sequences when we determined upper b bits of all elements of A, and A[i] might be larger than R[i] if u & (1<<i) != 0.

My implementation is memoized recursion.

Solution in C# (in the contest)

using System; 
using System.Text; 
using System.Text.RegularExpressions; 
using System.Collections; 
using System.Collections.Generic; 

public class YetAnotherORProblem 
{ 
    int N; 
    int[,] dp; 
    bool[,] done; 
    long[] R; 
    public int calc(int u, int b) 
    { 
        if (b < 0) 
            return 1; 
        if (done[u, b]) 
            return dp[u, b]; 
        dp[u, b] = 0; 
        for (int i = 0; i < N; ++i) 
        { 
            if ((u & (1 << i)) == 0 || ((ulong)R[i] & (1ul << b)) != 0) 
            { 
                int v = u; 
                for (int j = 0; j < N; ++j) 
                { 
                    if (i == j) 
                        continue; 
                    if (((ulong)R[j] & (1ul << b)) != 0) 
                        v &= ~(1 << j); 
                } 
                dp[u, b] = (dp[u, b] + calc(v, b - 1)) % 1000000009; 
            } 
        } 
        int nu = u; 
        for (int j = 0; j < N; ++j) 
        { 
            if (((ulong)R[j] & (1ul << b)) != 0) 
                nu &= ~(1 << j); 
        } 
        dp[u, b] = (dp[u, b] + calc(nu, b - 1)) % 1000000009; 
        done[u, b] = true; 
        return dp[u, b]; 
    } 

    public int countSequences(long[] R_) 
    { 
        N = R_.Length; 
        dp = new int[1 << N, 64]; 
        done = new bool[1 << N, 64]; 
        R = R_; 
        return calc((1 << N) - 1, 63); 
    } 
} 

CodeChef May Cook-off 2011

I solved 4 out of 5 problems. These 4 problems seem easy to solve and 1 remaining problem is very hard. Actually, I solved these 4 problems in an hour and I can't solve the last problem in 1.5 hours.

Rating: Not Rated -> 1170.387

Socializing Game around Pizza(BIGPIZA)

This is a problem about a simple game. It can be solved easily by using Grundy Number.

First, let G[0] and G[1] be 0, because it is impossible to make any pairs if we have 0 or 1 people around the pizza. For N >= 2, we can calculate G[N] by searching the smallest non-negative integer which doesn't appear in a set {G[i] xor G[N-2-i] | 0 <= i <= N-2}.

Time complexity of this algorithm is O(N^2).

Solution in C++ (in the contest)

#include<cstdio>

using namespace std;

int main()
{
  int grundy[10001];
  grundy[0] = 0; grundy[1] = 0;
  for(int i=2; i<=10000; ++i) {
    int a[10001] = {0};
    for(int j=0; j<=i-2; ++j)
      a[grundy[j] ^ grundy[i-j-2]] = 1;
    for(int j=0; j<=10000; ++j) {
      if(a[j] == 0) {
        grundy[i] = j;
        break;
      }
    }
  }
  int T;
  scanf("%d", &T);
  while(T--) {
    int n;
    scanf("%d", &n);
    puts(grundy[n] ? "Arjuna" : "Bhima");
  }
  return 0;
}

Preferred Cooking Schools(CKSCHOOL)

This is really hard problem. I can't solve this yet.

Distribute idlis Equally(EQIDLIS)

My solution for this problem is just simulate the redistributing process. Using multiset, one step can be done in O(log N). So the overall complexity is O(N + Result * log N).

But the result will not be so large, so I didn't use multiset. In my solution, one step is done in O(N). So the overall complexity of my solution is O(Result * N).

Solution in C++ (in the contest)

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
  int T;
  scanf("%d", &T);
  while(T--) {
    int N;
    scanf("%d", &N);
    vector<int> v(N);
    for(int i=0; i<N; ++i)
      scanf("%d", &v[i]);
    int S=0;
    for(int i=0; i<N; ++i)
      S+=v[i];
    if(S%N != 0) {
      puts("-1");
      continue;
    }
    vector<int> t;
    sort(v.begin(), v.end());
    for(int i=0; i<(int)v.size(); ++i)
      if(v[i] != S/N) t.push_back(v[i]);
    v = t;
    int cnt = 0;
    while(v.size() > 0) {
      vector<int> p;
      int R = (v.back()-v.front()+1) / 2;
      int A = v.front()+R, B = v.back()-R, K = v.size();
      if(A > B) swap(A, B);
      if(A == S/N) K--, A = -100;
      if(B == S/N) K--, B = -100;
      p.resize(K);
      int k = 0;
      for(int i=1; i<(int)v.size()-1; ++i) {
        int prev = i==1 ? -1 : p.back();
        if(prev <= A && A <= v[i]) p[k++]=A, A=-100;
        if(prev <= B && B <= v[i]) p[k++]=B, B=-100;
        p[k++]=v[i];
      }
      if(A >= 0) p[k++]=A;
      if(B >= 0) p[k++]=B;
      v = p;
      cnt++;
    }
    printf("%d\n", cnt);
  }
  return 0;
}

Packing the Golden Triangles(PACKBAND)

This problem can be solved by greedy approach. We sort the lengths of the boxes in increasing order, and sort the rubber bands in increasing order of R2. Then for each box, we search the first unused rubber bands which can be used to pack the box.

Solution in C++ (in the contest)

#include<cstdio>
#include<utility>
#include<algorithm>

using namespace std;

bool cmp(const pair<int, int> a, const pair<int, int> b)
{
  return make_pair(a.second, a.first)<make_pair(b.second, b.first);
}

int N, M, L[1024], U[1024];
pair<int, int> R[1024];
int dp[1024][1024];

inline bool ok(int i, int j)
{
  return R[j].first*11<=L[i]*7 && L[i]*7<=R[j].second*11;
}

int main()
{
  int T;
  scanf("%d", &T);
  while(T--) {
    scanf("%d", &N);
    for(int i=0; i<N; ++i)
      scanf("%d", &L[i]);
    scanf("%d", &M);
    for(int i=0; i<M; ++i)
      scanf("%d%d", &R[i].first, &R[i].second), U[i]=0;
    sort(L, L+N);
    sort(R, R+M, cmp);
    int S=0;
    for(int i=0; i<N; ++i) {
      for(int j=0; j<M; ++j) {
        if(U[j]==0 && ok(i, j)) {
          U[j]=1;
          S++;
          break;
        }
      }
    }
    printf("%d\n", S);
  }
  return 0;
}

Popular Rice Recipe(TIDRICE)

This is straight forward problem and quite easy. Just implementation.

Solution in C++ (in the contest)

#include<map>
#include<string>
#include<iostream>

using namespace std;

int main()
{
  int T;
  cin >> T;
  while(T--) {
    int N;
    cin >> N;
    map<string, int> V;
    while(N--) {
      string s, t;
      cin >> s >> t;
      if(t=="+") V[s]=1; else V[s]=-1;
    }
    int S=0;
    for(map<string, int>::iterator it=V.begin(); it!=V.end(); ++it)
      S+=it->second;
    cout << S << endl;
  }
  return 0;
}

TopCoder SRM 507

My performance was bad. Though I correctly solved Medium, it was too slow and I made a careless mistake in Easy. Moreover, I made no challenges while there are many chances to challenge. As a result, I got 192nd place in div1 and my rating fell 27. Now my rating is 2270.

Link to TopCoder (login required)

250 CubeStickers

As I mentioned above, I made a careless mistake and my solution was successfully challenged. I had to review my solution before or after submission.

500 CubePacking

Though I finally solved this problem, I wasted much time to consider wrong ways to solve this. My approach for this problem is as follows.

First, it is obvious that the lower bound of the volume is Ns+Nb*L^3. Then let's consider the upper bound. We can pack all cubes by following way: we lines up large cubes in a straight line, then we appends small cubes to it. So the result must be greater than or equal to Ns+Nb*L^3 and lower than or equal to Ns+Nb*L^3+L^2. This problem can be solved by searching all boxes whose volume is between lower and upper bounds.

Solution in C# (which I submitted in the contest)

public class CubePacking { 
    public bool ok2(int X, int Y, int Z, int S, int B, int L) 
    { 
        int x = X / L, y = Y / L, z = Z / L; 
        if (x * y * z < B) return false; 
        return true; 
    } 

    public bool ok(int V, int S, int B, int L) 
    { 
        for (int x = 1; x * x <= V; ++x) 
        { 
            if (V % x != 0) 
                continue; 
            for (int y = 1; y * y <= V / x; ++y) 
            { 
                if (V / x % y != 0) 
                    continue; 
                if (ok2(x, y, V / x / y, S, B, L)) 
                    return true; 
            } 
            for (int y = 1; y * y <= x; ++y) 
            { 
                if (x % y != 0) 
                    continue; 
                if (ok2(V / x, y, x / y, S, B, L)) 
                    return true; 
            } 
        } 
        return false; 
    } 

    public int getMinimumVolume(int Ns, int Nb, int L) 
    { 
        int V = Ns + Nb * L * L * L; 
        while (true) 
        { 
            if (ok(V, Ns, Nb, L)) 
                return V; 
            V++; 
        } 
    } 
}