USACO

USACO 1.4 Arithmetic Progression

Brutal force, pretty ugly code. Need optimize.

#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>
#include <string>
#include <cctype>
#include <algorithm>

using namespace std;

int main() {
  ifstream fin("ariprog.in");
  ofstream fout("ariprog.out");
  int const SIZE = 250;
  int N, M;
  fin >> N >> M;

  vector<bool> set(SIZE * SIZE * 2 + 1, false);
  for (int i = 0; i <= M; ++i) {
    for (int j = 0; j <= M; ++j) {
      set[i * i + j * j] = true;
    }
  }

  vector<pair<int, int>> result;
  auto limit = M * M * 2;
  for (int i = 0; i < limit; ++i) {
    bool found = true;
    for (int j = 1; j < limit - i; ++j) {
      if (j * (N - 1) + i > limit) {
        found = false;
        break;
      }

      for (int k = N - 1; k >= 0; --k) {
        auto val = i + k * j;

        if (val > limit) {
          found = false;
          break;
        }

        if (!set[val]) {
          found = false;
          break;
        } else {
          found = true;
        }
      }
      if (found) {
        result.emplace_back(std::make_pair(i, j));
      }
    }
  }

  sort(result.begin(), result.end(), [] (const pair<int, int> &lhs,
                                         const pair<int, int> &rhs) {
    return lhs.second != rhs.second ? lhs.second < rhs.second : lhs.first < rhs.first;
  });

  for (auto item : result) {
    fout << item.first << " " << item.second << std::endl;
  }

  if (!result.size())
    fout << "NONE" << endl;

  return 0;
}
USACO

USACO 1.3 Ski Course Design

At first glance, a reasonable approach seems to sort the heights of hills then starting from both ends (smallest and biggest), adjust and iterate and converge to a fixed point. However, the problem has a constraint that for each hill only a single change can be made, so this would not work. Think in the other direction, given the constraints each hill has to end up with a height that’s fall in the range of 0 to 83 (inclusive), so we can simply use brutal force to iterate that for each range, what would be the overall cost to adjust all hills.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <cmath>
#include <climits>

using namespace std;

int N;
vector<int> hills;
int compute() {
  int ret = INT_MAX;
  for (int i = 0; i < 83; ++i) {
    int result = 0;
    for (auto &h : hills) {
      if (h < i) {
        result += pow(i - h, 2);
      }
      if (h > i + 17) {
        result += pow(h -i - 17, 2);
      }
    }
    ret = min(ret, result);
  }
  return ret;
};

int main() {
  ifstream fin("skidesign.in");
  ofstream fout("skidesign.out");

  fin >> N;
  for (int i = 1; i <= N; ++i) {
    int h;
    fin >> h;
    hills.emplace_back(h);
  }

  int ret = compute();
  cout << ret << endl;
  fout << ret << endl;
}


USACO

USACO 1.3 Wormholes

The problem can be reduced to two sub problems:

  • Generate all combinations of pairs. This can be solved using backtrack.
  • For each combination test if there is a cycle. This can be solved by exhaustive search: starting from each wormhole, and try move the number of total wormholes, and repeat, until all wormholes are tested.
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>

using namespace std;

const int kMaxHoles = 12;
int total;
vector<int> vx(kMaxHoles + 1, 0);
vector<int> vy(kMaxHoles + 1, 0);
vector<int> nextWormhole(kMaxHoles + 1, 0);
vector<int> vpair(kMaxHoles + 1, 0);
vector<bool> visited(kMaxHoles + 1, false);

bool hasCycle() {
  for (int start = 1; start <= total; ++start){
    int current = start;
    for (int move = 1; move <= total; ++move)
      current = nextWormhole[vpair[current]];
    if (current != 0)
      return true;
  }
  return false;
}

int backtrack(){
  int unpaired = 0;
  for (int i = 1; i <= total; ++i) {
    if (vpair[i] == 0){
      unpaired = i;
      break;
    }
  }

  if (unpaired == 0) {
    return hasCycle();
  }

  int result = 0;
  for (int topair = unpaired + 1; topair <= total; ++topair)
    if (vpair[topair]  == 0){
      vpair[unpaired] = topair;
      vpair[topair] = unpaired;
      result += backtrack();
      vpair[unpaired] = 0;
      vpair[topair] = 0;
    }
  return result;
}

int main(){
  ifstream fin("wormhole.in");
  ofstream fout("wormhole.out");

  fin >> total;
  cout << total << endl;
  for (int i = 1; i <= total; ++i) {
    fin >> vx[i] >> vy[i];
    cout << vx[i] << " " << vy[i] << endl;
  }

  int current, next;
  for (current = 1; current <= total; ++current) {
    for (next = 1; next <= total; ++next){
      if (vy[current] != vy[next] || vx[next] <= vx[current]) {
        continue;
      }
      if (nextWormhole[current] == 0 || vx[next] < vx[nextWormhole[current]]) {
        cout << "current : " << current << "; next : " << next << endl;
        nextWormhole[current] = next;
      }
    }
  }

  for (int i = 1; i <= 12; ++i) {
    cout << nextWormhole[i] << ";";
  }

  fout << backtrack() << endl;
  return 0;
}