SRM319Div2

250

class SkewSymmetric {
public:
  int minChanges(vector <string> M) {
    int r = 0;
    int size = M.size();
    int m[size][size];
    for(int i=0; i<size; ++i){
      istringstream iss(M[i]);
      for(int j=0; j<size; ++j){
        iss >> m[i][j];
      }
    }
    for(int i=0; i<size; ++i){
      r += m[i][i] != 0;
      for(int j=i+1; j<size; ++j){
        r += m[i][j] != -m[j][i];
      }
    }
    return r;
  }
};

500

 class BusSeating {
public:
  pair<double ,double> pos(int i){
    double x, y;
    if(10 <= i){
      y = 2;
      i-= 10;
    }
    else y = 0;
    x = i;
    return make_pair(x, y);
  }
  double dist(int i, int j){
    pair<double, double> s = pos(i);
    pair<double, double> t = pos(j);
    double a = s.first - t.first;
    double b = s.second - t.second;
    return sqrt(a * a + b * b);
  }
  double getArrangement(string l, string r) {
    double mn = 1e256;
    string s = l + r;
    for(int i=0; i<20; ++i){
      if(s[i] == 'X')continue;
      for(int j=i+1; j<20; ++j){
        if(s[j] == 'X')continue;
        for(int k=j+1; k<20; ++k){
          if(s[k] == 'X')continue;
          mn = min(mn, dist(i, j) + dist(j, k) + dist(k, i));
        }
      }
    }
    return mn;
  }
}; 

1000

 map<int, char> node;

char get_max(int no)
{
  int left = no * 2;
  int right = no * 2 + 1;
  char mx = node[no];
  if( node.count( left ) ){
    mx = max(mx, get_max( left ));
  }
  if( node.count( right ) ){
    mx = max(mx, get_max( right ));
  }
  return mx;
}

char get_min(int no)
{
  int left = no * 2;
  int right = no * 2 + 1;
  char mn = node[no];
  if( node.count( left ) ){
    mn = min(mn, get_min( left ));
  }
  if( node.count( right ) ){
    mn = min(mn, get_min( right ));
  }
  return mn;
}

bool valid(int no)
{
  int left = no * 2;
  int right = no * 2 + 1;
  
  if( node.count( left ) ){
    if( !valid( left ) ) return false;
    if( get_max( left ) <= node[no] );
    else return false;
   
  }

  if( node.count( right ) ){
    if( !valid( right ) ) return false;
    if( node[no] < get_min( right ) );
    else return false;
  } 

  return true;
}

class IncompleteBST {
public:
  string missingValues(vector <string> tree) {
    int id = 0;
    node.clear();
    for(int i=0; i<tree.size(); ++i){
      istringstream iss( tree[i] );
      int n;
      char c;
      iss >> c >> n;
      if(c == '?')id = n;
      node[ n ] = c;
    }
   
    string r;
    for(char c='A'; c<='Z'; ++c){     
      node[ id ] = c;
      if( valid(1) ) r += c;
    }
    return r;
  }
};