UVa 183 - Bit Maps

Accepted date: 2013-10-27
Language: C++

/*
  UVa 183 - Bit Maps

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_183_Bit_Maps.cpp
*/

#include <cstdio>

const int rows_max = 200, columns_max = 200;
int bitmap[rows_max][columns_max];
int sums[rows_max][columns_max];
  // sum[i][j] is the sum of bitmap[bi][bj] (0 <= bi <= i, 0 <= bj <= j)
const int nr_chars_max = 50;
int nr_chars;

int zeros_ones(int top, int left, int bottom, int right)
{
  int s = sums[bottom][right];
  if (top && left)
    s += sums[top - 1][left - 1] - sums[top - 1][right] - sums[bottom][left - 1];
  else if (top)
    s -= sums[top - 1][right];
  else if (left)
    s -= sums[bottom][left - 1];
  if (!s)
    return 0; // all zeros
  else if (s == (bottom - top + 1) * (right - left + 1))
    return 1; // all ones
  else
    return -1;
}

void bitmap_putchar(char c)
{
  putchar(c);
  if (++nr_chars == nr_chars_max) {
    nr_chars = 0;
    putchar('\n');
  }
}

void quarters(int top, int left, int bottom, int right)
{
  int zo = zeros_ones(top, left, bottom, right);
  if (zo >= 0) // all zeros or ones
    bitmap_putchar(static_cast<char>(zo + '0'));
  else {
    bitmap_putchar('D');
    int rows = bottom - top + 1, columns = right - left + 1;
    if (rows > 1 && columns > 1) {
      quarters(top, left, top + (rows - 1) / 2, left + (columns - 1) / 2);
      quarters(top, left + (columns + 1) / 2, top + (rows - 1) / 2,  right);
      quarters(top + (rows + 1) / 2, left, bottom, left + (columns - 1) / 2);
      quarters(top + (rows + 1) / 2, left + (columns + 1) / 2, bottom, right);
    }
    else if (rows > 1) {
      quarters(top, left, top + (rows - 1) / 2, right);
      quarters(top + (rows + 1) / 2, left, bottom, right);
    }
    else {
      quarters(top, left, bottom, left + (columns - 1) / 2);
      quarters(top, left + (columns + 1) / 2, bottom,  right);
    }
  }
}

void decomposition(int rows, int columns)
{
  for (int r = 0; r < rows; r++) {
    int ones = 0;
    for (int c = 0; c < columns; c++) {
      char zero_or_one;
      do
        zero_or_one = getchar();
      while (zero_or_one == '\n');
      bitmap[r][c] = zero_or_one - '0';
      ones += bitmap[r][c];
      sums[r][c] = ones;
      if (r)
        sums[r][c] += sums[r - 1][c];
    }
  }
#ifdef DEBUG
  for (int r = 0; r < rows; r++)
    for (int c = 0; c < columns; c++)
      fprintf(stderr, "%4d%c", bitmap[r][c], ((c == columns - 1) ? '\n' : ' '));
  for (int r = 0; r < rows; r++)
    for (int c = 0; c < columns; c++)
      fprintf(stderr, "%4d%c", sums[r][c], ((c == columns - 1) ? '\n' : ' '));
#endif
  quarters(0, 0, rows - 1, columns - 1);
  if (nr_chars)
    putchar('\n');
}

void composition(int top, int left, int bottom, int right)
{
  char c;
  do
    c = getchar();
  while (c == '\n');
  if (c == '0' || c == '1') {
    c -= '0';
    for (int i = top; i <= bottom; i++)
      for (int j = left; j <= right; j++)
        bitmap[i][j] = c;
  }
  else { // 'D'
    int rows = bottom - top + 1, columns = right - left + 1;
    if (rows > 1 && columns > 1) {
      composition(top, left, top + (rows - 1) / 2, left + (columns - 1) / 2);
      composition(top, left + (columns + 1) / 2, top + (rows - 1) / 2,  right);
      composition(top + (rows + 1) / 2, left, bottom, left + (columns - 1) / 2);
      composition(top + (rows + 1) / 2, left + (columns + 1) / 2, bottom, right);
    }
    else if (rows > 1) {
      composition(top, left, top + (rows - 1) / 2, right);
      composition(top + (rows + 1) / 2, left, bottom, right);
    }
    else {
      composition(top, left, bottom, left + (columns - 1) / 2);
      composition(top, left + (columns + 1) / 2, bottom,  right);
    }
  }
}

int main()
{
  while (true) {
    char format[2];
    scanf("%s", format);
    if (format[0] == '#')
      break;
    int rows, columns;
    scanf("%d %d", &rows, &columns);
    nr_chars = 0;
    if (format[0] == 'B') {
      printf("%c%4d%4d\n", 'D', rows, columns);
      decomposition(rows, columns);
    }
    else {
      composition(0, 0, rows - 1, columns - 1);
      printf("%c%4d%4d\n", 'B', rows, columns);
      for (int r = 0; r < rows; r++)
        for (int c = 0; c < columns; c++)
          bitmap_putchar(static_cast<char>(bitmap[r][c] + '0'));
        if (nr_chars)
          putchar('\n');
    }
  }
  return 0;
}

UVa 10043 - Chainsaw Massacre

Accepted date: 2011-05-23
Ranking (as of 2013-10-26): 80 out of 387
Language: C++

/*
  14.7.3 Chainsaw Massacre
  PC/UVa IDs: 111403/10043, Popularity: B, Success rate: low Level: 3

  To build using Visucal Studio 2008:
    cl -EHsc chainsaw_massacre.cpp
*/

/*
  This is an application of maximum (or largest) empty rectangle problem.
*/

#include <iostream>
#include <vector>
#include <algorithm>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

struct point {
  int x, y;

  point() : x(0), y(0) {}
  point(int _x, int _y) : x(_x), y(_y) {}
  point(const point &p) : x(p.x), y(p.y) {}
  bool operator==(const point& p) const {return x == p.x && y == p.y;}
};

bool left_lower_order(const point& p1, const point& p2)
{
  if (p1.x < p2.x)
    return true;
  else if (p1.x > p2.x)
    return false;
  else if (p1.y < p2.y)
    return true;
  else
    return false;
}

bool upper_order(const point& p1, const point& p2)
{
  return p1.y > p2.y;
}

int maximum_empty_rectangle(int l, int w, vector<point>& points)
{
  if (points.empty())
    return l * w;
  sort(points.begin(), points.end(), left_lower_order);
    // sort the points in leftmost-lowest order
  for (vector<point>::iterator i = points.begin();
    i != points.end(); ) { // remove the duplicate points
    vector<point>::iterator j = i;
    j++;
    if (j != points.end() && *i == *j)
      i = points.erase(i);
    else
      i++;
  }
  int n = points.size();
  // get the maximum gap between the x coordinates
  vector<point>::const_iterator i = points.begin();
  int mgap = i->x;
  for (i++; i != points.end(); i++)
    mgap = max(mgap, i->x - (i - 1)->x);
  mgap = max(mgap, l - (i - 1)->x);
  int maxr = mgap * w;
  sort(points.begin(), points.end(), upper_order);
    // sort the points in descending order of y coordinates
  for (vector<point>::const_iterator i = points.begin();
    i != points.end(); i++) {
    int tl = 0, tr = l;
    vector<point>::const_iterator j = i;
    for (j++; j != points.end(); j++)
      if (j->x > tl && j->x < tr) {
        maxr = max(maxr, (tr - tl) * (i->y - j->y));
        if (j->x > i->x)
          tr = j->x;
        else
          tl = j->x;
      }
    maxr = max(maxr, (tr - tl) * i->y);
  }
  for (vector<point>::const_reverse_iterator i = points.rbegin();
    i != points.rend(); i++) {
    int li = 0, ri = l;
    vector<point>::const_reverse_iterator j = i;
    for (j++; j != points.rend(); j++)
      // since points are sorted in descending order of y coordinates,
      // j->y >= i->y
      if (j->y > i->y) {
        if (j->x > i->x)
          ri = min(ri, j->x);
        else
          li = max(li, j->x);
      }
    maxr = max(maxr, (ri - li) * (w - i->y));
  }
  return maxr;
}

int main(int /* argc */, char** /* argv */)
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  int nr_scenarios;
  cin >> nr_scenarios;
  while (nr_scenarios--) {
    vector<point> points;
    int l, w;
    cin >> l >> w;
    while (true) {
      int k;
      cin >> k;
      if (!k) // end of a scenario
        break;
      int x, y, dx = 0, dy = 0;
      cin >> x >> y;
      if (k > 1)
        cin >> dx >> dy;
      for ( ; k; k--, x += dx, y += dy)
        points.push_back(point(x, y));
    }
    cout << maximum_empty_rectangle(l, w, points) << endl;
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

Uva 10032 - Tug of War

Accepted date: 2011-03-12
Ranking (as of 2013-10-26): 178 out of 817
Language: C++

Used sort of an incomplete Dynamic Programming to get the candidates of solutions and then Applied backtracking for the candidates.

/*
  8.6.5 Tug of War
  PC/UVa IDs: 110805/10032, Popularity: B, Success rate: low Level: 2

  To build using Visucal Studio 2008:
    cl -EHsc tug_of_war.cpp
*/

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

#ifdef DEBUG
void print_pr_people(int sum_of_weights, const vector< pair<unsigned char,
  unsigned char> >& nr_people)
{
  for (int i = 1; i <= sum_of_weights; i++)
    if (nr_people[i].first)
      cout << i << '(' << static_cast<unsigned int>(nr_people[i].first) << ' ' <<
        static_cast<unsigned int>(nr_people[i].second) << ") ";
  cout << endl;
}
#endif

int generate_nr_people(int n, const vector<int>& weights,
  vector< pair<unsigned char, unsigned char> >& nr_people)
{
/*
  While calculating each realizable team weight, 
  also record the minimum/maximum number of people whose weights are 
  added up to it.
*/
  int sum_of_weights = 0;
  for (int i = 1; i <= n; i++) {
    int w = weights[i];
    for (int j = sum_of_weights; j; j--)
      if (nr_people[j].first) {
        if (nr_people[j + w].first) {
          nr_people[j + w].first = min(nr_people[j + w].first,
            static_cast<unsigned char>(nr_people[j].first + 1));
          nr_people[j + w].second = max(nr_people[j + w].second,
            static_cast<unsigned char>(nr_people[j].second + 1));
        }
        else {
          nr_people[j + w].first = nr_people[j].first + 1;
          nr_people[j + w].second = nr_people[j].second + 1;
        }
      }
    nr_people[w].first = 1;
    if (!nr_people[w].second)
      nr_people[w].second = 1;
    sum_of_weights += w;
  }
#ifdef DEBUG
  print_pr_people(sum_of_weights, nr_people);
#endif
  return sum_of_weights;
}

bool is_valid_team_weight(int nr_one, int nr_other,
  int one_weight, int other_weight, int nr_weights,
  const vector<int>& weights, const vector< pair<unsigned char,
  unsigned char> >& nr_people)
{
  if (!nr_weights)
    return false;
  int w = one_weight - weights[nr_weights];
  if (!w) {
    if (nr_one == 1)
      return true;
    else if (nr_other > 1 && other_weight == one_weight)
      return false;
    else return is_valid_team_weight(nr_other, nr_one, other_weight, one_weight,
      nr_weights, weights, nr_people);
  }
  else if (w < 0)
    return is_valid_team_weight(nr_other, nr_one, other_weight, one_weight,
      nr_weights, weights, nr_people);
  else if (nr_people[w].first && nr_one - 1 >= nr_people[w].first &&
    nr_one - 1 <= nr_people[w].second &&
    is_valid_team_weight(nr_one - 1, nr_other, w, other_weight,
      nr_weights - 1, weights, nr_people))
    return true;
  else {
    if (!(w = other_weight - weights[nr_weights]))
      return (nr_other == 1) ? true : false;
    else if (w < 0)
      return false;
    else if (nr_people[w].first && nr_other - 1 >= nr_people[w].first &&
      nr_other - 1 <= nr_people[w].second &&
      is_valid_team_weight(nr_one, nr_other - 1, one_weight, w,
        nr_weights - 1, weights, nr_people))
      return true;
    else
      return false;
  }
}

pair<int, int> find_minimum_team_weight_pair(int n, int sum_of_weights,
  const vector<int>& weights, const vector< pair<unsigned char,
  unsigned char> >& nr_people)
{
  int nr_one_max = n / 2, nr_other_max = 0; // max. number of people for a team
  if (n & 1)
    nr_other_max = nr_one_max + 1;
  int i = sum_of_weights / 2;
  for ( ; ; i--) {
    int nr_one = nr_people[i].first, nr_other =
      nr_people[sum_of_weights - i].first;
    if (nr_one && nr_other) {
      if (n & 1) {
        if (nr_one < nr_other_max && nr_other < nr_other_max) {
          if (is_valid_team_weight(nr_other_max, nr_one_max, sum_of_weights - i,
            i, n, weights, nr_people) ||
            is_valid_team_weight(nr_other_max, nr_one_max, i, sum_of_weights - i,
              n, weights, nr_people))
              break;
        }
        else if (nr_one == nr_other_max) {
          if (is_valid_team_weight(nr_other_max, nr_one_max, i,
            sum_of_weights - i, n, weights, nr_people))
            break;
        }
        else if (nr_other == nr_other_max) {
          if (is_valid_team_weight(nr_other_max, nr_one_max, sum_of_weights - i,
            i, n, weights, nr_people))
            break;
        }
      }
      else {
        if (nr_one <= nr_one_max && nr_other <= nr_one_max) {
          if (is_valid_team_weight(nr_one_max, nr_one_max, sum_of_weights - i,
            i, n, weights, nr_people) ||
            is_valid_team_weight(nr_one_max, nr_one_max, i, sum_of_weights - i,
            n, weights, nr_people))
            break;
        }
      }
    }
  }
  return make_pair(i, sum_of_weights - i);
}

int main(int /* argc */, char** /* argv */)
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  int cases; // number of test cases
  cin >> cases;
  while (cases--) {
    int n;
    cin >> n; // number of people
    vector<int> weights(n + 1); // vector of weights
    weights[0] = 0;
    for (int i = 1; i <= n; i++)
      cin >> weights[i];
    if (n < 2)
      cout << "0 " << weights[n] << endl;
    else {
      sort(weights.begin() + 1, weights.end());
      int sum_of_weights = 0;
      for (int i = 1; i <= n; i++)
        sum_of_weights += weights[i];
      vector< pair<unsigned char, unsigned char> >
        nr_people(sum_of_weights + 1, make_pair(0, 0));
        //  nr_peoplei].first/second is the minimum/maximum number of people 
        // whose weights are added up to i, or 0 if no weights are added up to i
      generate_nr_people(n, weights, nr_people);
      pair<int, int> weight_pair =
        find_minimum_team_weight_pair(n, sum_of_weights, weights, nr_people);
      cout << weight_pair.first << ' ' << weight_pair.second << endl;
    }
    if (cases)
      cout << endl;
        // the output of each two consecutive cases will be separated 
        // by a blank line
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

UVa 10895 - Matrix Transpose

Accepted date: 2013-10-22
Ranking (as of 2013-10-22): 619 out of 722
Language: C++

/*
  UVa 10895 - Matrix Transpose

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10895_Matrix_Transpose.cpp
*/

#include <cstdio>
#include <algorithm>
using namespace std;

const int nr_non_zero_elements_max = 1000;

struct element {
  int row_;
  int column_;
  int value_;
  bool operator<(const element& e) const {
    if (row_ < e.row_)
      return true;
    else if (row_ > e.row_)
      return false;
    else
      return column_ < e.column_;
  }
} elements[nr_non_zero_elements_max];

int main()
{
  int m, n;
  while (scanf("%d %d", &m, &n) != EOF) {
    int r, c, nr_elements = 0;
    for (r = 1; r <= m; r++) {
      int nc;
      scanf("%d", &nc);
      for (c = 0; c < nc; c++) {
        elements[nr_elements + c].column_ = r;
        scanf("%d", &elements[nr_elements + c].row_);
      }
      for (c = 0; c < nc; c++)
        scanf("%d", &elements[nr_elements + c].value_);
      nr_elements += c;
    }
    sort(elements, elements + nr_elements);
    printf("%d %d\n", n, m); 
    int cs = 0, ce = 0;
    for (r = 1; r <= n; r++) {
      for ( ; elements[ce].row_ == r; ce++)
        ;
      int nc = ce - cs;
      printf("%d", nc);
      for (c = 0; c < nc; c++)
        printf(" %d", elements[cs + c].column_);
      putchar('\n');
      for (c = 0; c < nc; c++) {
        if (c)
          putchar(' ');
        printf("%d", elements[cs + c].value_);
      }
      putchar('\n');
      cs = ce;
    }
  }
  return 0;
}

UVa 11624 - Fire!

Accepted date: 2013-10-19
Ranking (as of 2013-10-19): 40 out of 732
Language: C++

/*
  UVa 11624 - Fire!

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11624_Fire.cpp
*/

#include <queue>
#include <utility>
#include <cstdio>
using namespace std;

const int R_max = 1000, C_max = 1000;
char maze[R_max][C_max + 1];

int bfs(int R, int C, int jr, int jc)
{
  const int nr_dirs = 4;
  int dirs[nr_dirs][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
  queue< pair<pair<int, int>, int> > q;
  q.push(make_pair(make_pair(jr, jc), 0));
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
      if (maze[r][c] == 'F')
        q.push(make_pair(make_pair(r, c), -1));
  while (!q.empty()) {
    pair<pair<int, int>, int> s = q.front(); q.pop();
    for (int i = 0; i < nr_dirs; i++) {
      int r = s.first.first + dirs[i][0], c = s.first.second + dirs[i][1];
      if (r < 0 || r >= R || c < 0 || c >= C) {
        if (maze[s.first.first][s.first.second] == 'J')
          return s.second + 1;
      }
      else if (maze[s.first.first][s.first.second] == 'J') {
        if (maze[r][c] == '.') {
          maze[r][c] = 'J';
          q.push(make_pair(make_pair(r, c), s.second + 1));
        }
      }
      else { // maze[s.first.first][s.first.second] == 'F'
        if (maze[r][c] == '.' || maze[r][c] == 'J') {
          maze[r][c] = 'F';
          q.push(make_pair(make_pair(r, c), -1));
        }
      }
    }
  }
  return -1;
}

int main()
{
  int tc;
  scanf("%d", &tc);
  while (tc--) {
    int R, C;
    scanf("%d %d", &R, &C);
    int jr = -1, jc = -1;
    for (int r = 0; r < R; r++) {
      scanf("%s", maze[r]);
      if (jr == -1) {
        for (int c = 0; c < C; c++)
          if (maze[r][c] == 'J') {
            jr = r; jc = c; break;
          }
      }
    }
    int minutes = bfs(R, C, jr, jc);
    if (minutes == -1)
      puts("IMPOSSIBLE");
    else
      printf("%d\n", minutes);
  }
  return 0;
}

UVa 11239 - Open Source

Accepted date: 2013-10-13
Ranking (as of 2013-10-13): 194 out of 724
Language: C++

/*
  UVa 11239 - Open Source

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11239_Open_Source.cpp
*/

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
using namespace std;

struct project {
  string name_;
  int nr_students_;

  project() : nr_students_(0) {}
  project(const string& name) : name_(name), nr_students_(0) {}

  bool operator<(const project& p) const {
    if (nr_students_ > p.nr_students_)
      return true;
    else if (nr_students_ < p.nr_students_)
      return false;
    else
      return name_ < p.name_;
  }
};

int main()
{
  bool continued = false;
  string s;
  while (true) {
    vector<project> projects;
    map<string, int> students;
    int pi;
    while (true) {
      if (!continued)
        getline(cin, s);
      else
        continued = false;
      if (s[0] == '1')
        break;
      if (isupper(s[0])) {
        pi = static_cast<int>(projects.size());
        projects.push_back(project(s));
      }
      else {
        pair< map<string, int>::iterator, bool >
          result = students.insert(make_pair(s, pi));
        if (result.second)
          projects[pi].nr_students_++;
        else if (result.first->second != pi) {
          if (result.first->second != -1) {
            projects[result.first->second].nr_students_--;
            result.first->second = -1;
          }
        }
      }
    }
    sort(projects.begin(), projects.end());
    for (vector<project>::const_iterator i = projects.begin(),
      e = projects.end(); i != e; ++i)
      cout << i->name_ << ' ' << i->nr_students_ << endl;
    getline(cin, s);
    if (s[0] == '0')
      break;
    continued = true;
  }
  return 0;
}

UVa 10920 - Spiral Tap

Accepted date: 2013-10-13
Ranking (as of 2013-10-13): 265 out of 725
Language: C++

/*
  UVa 10920 - Spiral Tap

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10920_Spiral_Tap.cpp
*/

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
  while (true) {
    int sz;
    long long p;
    cin >> sz >> p;
    if (!sz && !p)
      break;
    long long x = (sz + 1) / 2, y = (sz + 1) / 2;
    long long q = sqrt(static_cast<double>(p));
      // max. odd number equal to or less than sqrt(p)
    if (!(q & 1))
      q--;
    x += (q - 1) / 2; y += (q - 1) / 2;
    p -= q * q;
    if (p) {
      q++;
      if (p <= q) {
        x -= p - 1; y++;
      }
      else if (p <= q * 2) {
        x -= q - 1; y -= p - q - 1;
      }
      else if (p <= q * 3) {
        x -= q * 3 - p - 1; y -= q - 1;
      }
      else {
        x++; y -= q * 4 - p - 1;
      }
    }
    cout << "Line = " << y << ", column = " << x << ".\n";
  }
  return 0;
}