USACO 3.1 Humble Numbers

The idea is to generate and maintain a sorted list of humble numbers:

Each humble number can be generated together with this sorted list, and with one of the seed prime numbers.
For each humble number, there is one and only one way of generating the number - in other words the prime factors are fixed for a given humble number.
For each prime factor number, maintain an index into the humble number sorted list. The indexed number in the humble number list would be the next number that this prime factor should multiply.
The invariant is, at each iteration, the smallest possible humble number is generated, and each index associated with each prime factor is incremented by one, if the prime factor contributes to the generation (num % prime == 0).

Following this idea, the humble numbers can be generated systematically without duplicates, and we only need maintain a single sorted list of humble numbers.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <unordered_map>
#include <climits>
#include <sstream>

using namespace std;

int N, K;

int main() {
  ifstream fin("humble.in");
  ofstream fout("humble.out");
  
  fin >> K >> N;
  vector<int> dp(N + 1, INT_MAX);
  vector<int> num(K, 0);
  vector<int> indices(K, 0);
  for (int i = 0; i < K; ++i) {
    fin >> num[i];
  }
  dp[0] = 1;
  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j < K; ++j) {
      dp[i] = std::min(dp[i], dp[indices[j]] * num[j]);
    }
    for (int j = 0; j < K; ++j) {
      if (dp[i] % num[j] == 0) {
        ++indices[j];
      }
    }
  }
  fout << dp[N] << endl;
  cout << dp[N] << endl;
}

2016-10-18

USACO

USACO 3.1 Inflation

This is a standard ‘Complete Knapsack’ problem. First stab:

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <unordered_map>
#include <climits>
#include <sstream>

using namespace std;

int M /* minutes */, N /* classes */;

int main() {
  ifstream fin("inflate.in");
  ofstream fout("inflate.out");
  fin >> M >> N;
  vector<vector<int>> dp;
  vector<int> w;
  vector<int> v;
 
  dp = vector<vector<int>>(N + 1, vector<int>(M + 1));
  w = vector<int>(N, 0);
  v = vector<int>(N, 0);
  for (int i = 0; i < N; ++i) {
    fin >> v[i] >> w[i];
  }
  
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= M; ++j) {
      if (j < w[i]) {
        dp[i + 1][j] = dp[i][j];
      } else {
        dp[i + 1][j] = std::max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
      }
    }
  }
  
  fout << dp[N][M] << endl;
  cout << dp[N][M] << endl;
}

This solution exceeds the memory limit (16MB, it seems) set by the problem judge. So the optimization of using a rolling array to compress the states is required. It is possible to do the optimization because the compute of a given state only depends on the value of the current state and the value of previous state.
Now this one passes:

int main() {
  ifstream fin("inflate.in");
  ofstream fout("inflate.out");
  fin >> M >> N;
  vector<int> dp = vector<int>(M + 1);
  vector<int> w = vector<int>(N, 0);
  vector<int> v = vector<int>(N, 0);
  
  for (int i = 0; i < N; ++i) {
    fin >> v[i] >> w[i];
  }
  
  for (int i = 0; i < N; ++i) {
    for (int j = w[i]; j <= M; ++j) {
      dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
  
  fout << dp[M] << endl;
  cout << dp[M] << endl;
}

2016-10-14

USACO

USACO 3.1 AgriNet

Easy problem with prim MST algorithm.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <unordered_map>
#include <climits>
#include <sstream>

using namespace std;

int N;
int ret = 0;
vector<bool> minset;
vector<int> parent;
vector<int> dist;
vector<vector<int>> grid;

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

  fin >> N;
  grid = vector<vector<int>>(N, vector<int>(N, 0));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      fin >> grid[i][j];
    }
  }

  minset = vector<bool>(N, false);
  parent = vector<int>(N, -1);
  dist = vector<int>(N, INT_MAX);
  dist[0] = 0;

  // Iterate N -1 times (since we have initialized dist for vertex 0 already).
  for (int i = 0; i < N - 1; ++i) {
    // Find next vertex that not in set, which has smallest distance to existing
    // set of vertices.
    int min = INT_MAX; int minIdx = 0;
    for (int ii = 0; ii < N; ++ii) {
      if (!minset[ii] && dist[ii] < min) {
        minIdx = ii;
        min = dist[ii];
      }
    }

    // Add the new vertex to the set, and update all dist accordingly.
    minset[minIdx] = true;
    for (int j = 0; j < N; ++j) {
      if (grid[minIdx][j] && !minset[j] && grid[minIdx][j] < dist[j]) {
        dist[j] = grid[minIdx][j];
        parent[j] = minIdx;
      }
    }
  }

  int ret = 0;
  for (int i = 1; i < N; ++i) {
    ret += grid[parent[i]][i];
  }

  fout << ret << endl;
  cout << ret << endl;
}