UVa 10146 - Dictionary

Accepted date: 2016-12-206
Run Time: 0.030
Ranking (as of 2016-12-26): 6 out of 370
Language: C++

/*
  UVa 10146 - Dictionary

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

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

const int nr_chars_max = 10;

const char* spaces[] = {
  "", " ", "  ", "   ", "    ", "     ", "      ", "       ", "        ", 
  "         ", "          "
};

int main()
{
  int nr_cases;
  scanf("%d", &nr_cases);
  while (getchar() != '\n')
    ;
  char s[nr_chars_max + 1], t[nr_chars_max + 1];
  gets(s);
  while (nr_cases--) {
    gets(s);
    puts(s);
    char *previous = s, *current = t;
    int nr_spaces = 1;
    while (gets(current) && current[0]) {
      int i;
      for (i = 0; i < nr_spaces; i++)
        if (!previous[i] || !current[i] || previous[i] != current[i])
          break;
      printf("%s%s\n", spaces[i], current);
      nr_spaces = i + 1;
      swap(previous, current);
    }
    if (nr_cases)
      putchar('\n');
  }
  return 0;
}

UVa 12205 - Happy Telephones

Accepted date: 2016-12-25
Run Time: 0.040
Ranking (as of 2016-12-25): 22 out of 362
Language: C++

First, applied the line sweep algorithm to calculate the number of connections at each start/stop time of the telephone calls.
For a given interval, found the number of calls at the start time of the interval and then iterated over the telephone call times till the end time of the interval and added the phone calls that started during the interval.

/*
  UVa 12205 - Happy Telephones

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

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

const int N_max = 10000, M_max = 100;

struct event {
  int s_; // 0 for start, 1 for stop
  int t_; // time

  event() {}
  event(int s, int t) : s_(s), t_(t) {}
  bool operator<(const event& e) const {
    if (t_ != e.t_)
      return t_ < e.t_;
    else
      return s_ > e.s_;
  }
} events[N_max * 2];

int main()
{
  while (true) {
    int N, M;
    scanf("%d %d", &N, &M);
    if (!N)
      break;
    int n = 0;
    while (N--) {
      int s, d;
      scanf("%*d %*d %d %d", &s, &d);
      events[n].s_ = 0, events[n].t_ = s;
      n++;
      events[n].s_ = 1, events[n].t_ = s + d;
      n++;
    }
    sort(events, events + n);
#ifdef DEBUG
    for (int i = 0; i < n; i++)
      printf("%d:%d%c", events[i].t_, events[i].s_, ((i < n - 1) ? ' ' : '\n'));
#endif
    int nr = 0;
    map<int, int> nr_calls; // key is the time, value is the number of calls from the time
    for (int i = 0; i < n; i++) {
      if (!events[i].s_)
        nr++;
      else
        nr--;
      nr_calls[events[i].t_] = nr;
    }
#ifdef DEBUG
    for (map<int, int>::const_iterator i = nr_calls.begin(); i != nr_calls.end(); ++i)
      printf("%d:%d ", i->first, i->second);
    putchar('\n');
#endif
    while (M--) {
      int s, d;
      scanf("%d %d", &s, &d);
      nr = 0;
      map<int, int>::const_iterator i = nr_calls.upper_bound(s);
      if (i != nr_calls.end()) {
#ifdef DEBUG
        printf("%d:%d\n", i->first, i->second);
#endif
        if (i != nr_calls.begin())
          nr = (--i)->second;
        int j = upper_bound(events, events + n, event(0, s)) - events;
#ifdef DEBUG
        if (j < n)
          printf("%d:%d\n", events[j].t_, events[j].s_);
#endif
        for ( ; j < n && events[j].t_ < s + d; j++)
          if (!events[j].s_)
            nr++;
      }
      printf("%d\n", nr);
    }
  }
  return 0;
}

UVa 12506 - Shortest Names

Accepted date: 2016-12-23
Run Time: 0.010
Ranking (as of 2016-12-23): 31 out of 363
Language: C++

Used trie.
During the construction of trie, counted the number of occurrences of each trie node.
Then, treversed the trie and summed up the number of occurrences of letters except for the nodes whose parent node has the occurrence counter value of 1.

/*
  UVa 12506 - Shortest Names

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

#include <cstdio>
#include <cstring>

const int nr_letters = 'z' - 'a' + 1, nr_chars_max = 1000000;
char name[nr_chars_max + 1];

struct trie_node {
  static int ctrs_[nr_letters];

  int ctr_;
  trie_node* children_[nr_letters];

  trie_node() : ctr_(0) {
    memset(children_, 0, sizeof(children_));
  }
  ~trie_node() {
    for (int i = 0; i < nr_letters; i++)
      delete children_[i];
  }
  void insert(const char* s);
  void count_prefix(int ci);
};

int trie_node::ctrs_[nr_letters];

void trie_node::insert(const char* s)
{
  trie_node* p = this;
  for (int i = 0, length = strlen(s); i < length; i++) {
    int j = s[i] - 'a';
    if (!p->children_[j])
      p->children_[j] = new trie_node();
    p = p->children_[j];
    p->ctr_++;
  }
}

void trie_node::count_prefix(int ci)
{
  ctrs_[ci] += ctr_;
  if (ctr_ > 1)
    for (int i = 0; i < nr_letters; i++)
      if (children_[i])
        children_[i]->count_prefix(i);
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    memset(trie_node::ctrs_, 0, sizeof(trie_node::ctrs_));
    trie_node* root = new trie_node();
    while (n--) {
      scanf("%s", name);
      root->insert(name);
    }
    for (int i = 0; i < nr_letters; i++)
      if (root->children_[i])
        root->children_[i]->count_prefix(i);
    int ctr = 0;
    for (int i = 0; i < nr_letters; i++)
      ctr += trie_node::ctrs_[i];
    printf("%d\n", ctr);
    delete root;
  }
  return 0;
}

UVa 12467 - Secret Word

Accepted date: 2016-12-11
Run Time: 0.020
Ranking (as of 2016-12-11): 3 out of 363
Language: C++

Applied KMP (Knuth-Morris-Pratt) algorithm where patten is an input string and text is the reverse of the input string.

/*
  UVa 12467 - Secret Word

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

#include <cstdio>
#include <cstring>

const int nr_chars_max = 1000000;
char S[nr_chars_max + 1];
int lps[nr_chars_max];
  // length of the maximum matching proper prefix which is also a suffix of S[0..i]

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", S);
    int n = strlen(S);
    // apply KMP (Knuth-Morris-Pratt) algorithm 
    // where patten is an input string and text is the reverse of the input string
    // calculate lps[]
    lps[0] = 0;
    for (int i = 1, length = 0 /* length of the previous longest prefix suffix */;
      i < n; ) {
      if (S[i] == S[length])
        lps[i++] = ++length;
          else {
          if (length)
          length = lps[length - 1];
              else
                  lps[i++] = 0;
      }
    }
    int max_length = 0, max_i;
    for (int i = n - 1, j = 0; i >= 0; ) {
      if (i >= 0 && S[j] == S[i])
        j++, i--;
      if (j > max_length)
        max_length = j, max_i = i + 1;
      if (j == n)
        j = lps[j - 1];
      else if (i >= 0 && S[j] != S[i]) {
        if (j)
          j = lps[j - 1];
        else
          i--;
      }
    }
#ifdef DEBUG
    printf("%d %d\n", max_i, max_length);
#endif
    S[max_i + max_length] = '\0';
    puts(&S[max_i]);
  }
  return 0;
}

UVa 11515 - Cranes

Accepted date: 2016-12-09
Run Time: 0.000
Ranking (as of 2016-12-09): 78 out of 364
Language: C++

Applied dynamic programming.
areas[i] is the areas with the bitmap i of cranes' usage where each bit of i corresponds to the i-th crane.

/*
  UVa 11515 - Cranes

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

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

const int C_max = 15;

struct crane {
  int x_, y_, r_;
} cranes[C_max];

bool overlapped[C_max][C_max];
  // overlapped[i][j] is true 
  // if the covering areas of i-th crane and j-th crane are overlapped
int areas[1 << C_max];
  // areas[i] is the areas with the bitmap i of cranes' usage

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int C;
    scanf("%d", &C);
    for (int i = 0; i < C; i++)
      scanf("%d %d %d", &cranes[i].x_, &cranes[i].y_, &cranes[i].r_);
    memset(overlapped, 0, sizeof(overlapped));
    for (int i = 0; i < C - 1; i++)
      for (int j = i + 1; j < C; j++) {
        int dx = cranes[i].x_ - cranes[j].x_, dy = cranes[i].y_ - cranes[j].y_,
          dr = cranes[i].r_ + cranes[j].r_;
        if (dx * dx + dy * dy <= dr * dr)
          overlapped[i][j] = overlapped[j][i] = true;
      }
    memset(areas, 0, sizeof(int) * (1 << C));
    areas[1] = cranes[0].r_ * cranes[0].r_;
#ifdef DEBUG
    printf("[1]:%d\n", areas[1]);
#endif
    for (int i = 1, ib = 1 << 1; i < C; i++, ib <<= 1) {
      int a = cranes[i].r_ * cranes[i].r_;
      for (int j = 1; j < ib; j++)
        if (areas[j]) {
          int k, kb;
          for (k = 0, kb = 1; k < i; k++, kb <<= 1)
            if (j & kb && overlapped[i][k])
              break;
          if (k == i) // not overlapped
            areas[j | ib] = areas[j] + a;
        }
      areas[ib] = a;
#ifdef DEBUG
      for (int j = 1; j < 1 << ib; j++)
        if (areas[j])
          printf("[%d]:%d ", j, areas[j]);
      putchar('\n');
#endif
    }
    int max_area = 0;
    for (int j = 1; j < 1 << C; j++)
      max_area = max(max_area, areas[j]);
    printf("%d\n", max_area);
  }
  return 0;
}