Solution to Pizza Baking from Round 3 of the 2014 Hacker Cup

pizza_baking.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <map>
#include <numeric>
#include <queue>
#include <cassert>

using namespace std;

int N, K;
int C[30];
int S[30];
pair<int, int> E[1010];

bool vis[30];
bool used[100010];
int cn[30][30];

/* Standard augmenting path dfs. */
bool dfs(int x, int snk) {
  if(x == snk) return true;
  if(vis[x]) return false;
  vis[x] = true;

  for(int i = 0; i <= snk; i++) {
    if(cn[x][i] && dfs(i, snk)) {
      cn[x][i]--;
      cn[i][x]++;
      return true;
    }
  }
  return false;
}

int main() {
  int T; cin >> T;
  for(int t = 1; t <= T; t++) {
    printf("Case #%d:", t);

    cin >> K;
    for(int i = 0; i < K; i++) {
      cin >> C[i];
    }
    C[K] = 0;

    cin >> N;
    memset(S, 0, sizeof(S));
    for(int i = 0; i < N; i++) {
      cin >> E[i].first >> E[i].second;
      E[i].second++;
      for(int j = E[i].first; j < E[i].second; j++) {
        S[j]++;
      }
    }

    /* The key lemma of this problem is that the number of ovens needed is always
     * the max number of ovens needed at any given time; i.e. max(ceil(S_i/C_i)). */
    int res = 0;
    for(int i = 0; i < K; i++) {
      res = max(res, (S[i] + C[i] - 1) / C[i]);
    }

    vector<int> R(N, -1);
    memset(used, 0, sizeof(used));
    for(int i = 0; i < res; i++) {
      int src = K + 1;
      int snk = K + 2;
      memset(cn, 0, sizeof(cn));

      /* Setup the initial flow. */
      int lst = 0;
      for(int j = 0; j <= K; j++) {
        cn[src][j] = max(0, C[j] - lst);
        cn[j][snk] = max(0, lst - C[j]);
        lst = C[j];
      }

      /* Each pizza takes us from its start time to end time. */
      for(int j = 0; j < N; j++) {
        if(!used[j]) {
          cn[E[j].first][E[j].second]++;
        }
      }

      /* Add unit length virtual edges so that each oven will be filled to
       * C[i] at all times. */
      for(int j = 0; j < K; j++) {
        cn[j][j + 1] += (res - i) * C[j] - S[j];
      }

      /* Saturate the network to find an initial solution that fills the oven
       * to maximum capacity at all times. */
      do {
        memset(vis, 0, sizeof(vis));
      } while(dfs(src, snk));

      for(int e = 0; e < N; e++) {
        if(used[e]) {
          continue;
        }

        bool can = false;
        if(cn[E[e].second][E[e].first]) {
          /* The edge has already been selected.  Force its future selection. */
          can = true;
          cn[E[e].second][E[e].first]--;
          cn[snk][E[e].first]++;
          cn[E[e].second][src]++;
        } else {
          /* Need to try forcing the edge. */
          cn[E[e].first][E[e].second]--;
          cn[E[e].first][snk]++;
          cn[src][E[e].second]++;

          memset(vis, 0, sizeof(vis));
          if(dfs(src, snk)) {
            can = true;
          } else {
            cn[E[e].first][snk]--;
            cn[src][E[e].second]--;
          }
        }

        if(can) {
          used[e] = true;
          R[e] = i;
          for(int j = E[e].first; j < E[e].second; j++) {
            S[j]--;
          }
        }
      }
    }

    /* Check that solution is valid (not necessary). */
    for(int i = 0; i < res; i++) {
      int V[30];
      memset(V, 0, sizeof(V));
      for(int j = 0; j < N; j++) {
        if(R[j] == i) {
          for(int k = E[j].first; k < E[j].second; k++) {
            V[k]++;
            assert(V[k] <= C[k]);
          }
        }
      }
    }

    for(int i = 0; i < N; i++) {
      assert(R[i] != -1);
      printf(" %d", R[i]);
    }
    printf("\n");
  }
  return 0;
}