USACO DEC09 Problem 'mnotes' Analysis

by Brian Jacokes

This problem boils down to finding an efficient way to handle each of FJ's questions. First, we use the lengths of the individual notes to calculate the time at which each note starts, and store this in a new array of variables C_i. Specifically, we set C_1 = 0, and C_{i+1} = C_i + B_i for i >= 1. Thus the i-th note is played from time C_i to C_{i+1} - 1.

This precomputation has enabled us to rephrase the original problem: now we need to be able to tell quickly where a value (the queried time T) falls in an ordered set of intervals (the intervals formed by the C_i values). This is a classic opportunity to exploit a binary search which will give us the answer to each question in O(log N) time. You can use the lower_bound function provided in the algorithm.h library, but it is also easy to code up the binary search yourself. Sample solution:

#include <stdio.h>
#include <stdlib.h>
#define MAX 50005

int N, Q;
int B[MAX];
int C[MAX];

int lbsearch (int low, int high, int target) {
  if (low == high)
    return low;
  int mid = (low+high)/2;
  if (C[mid+1] <= target) return lbsearch (mid+1, high, target);
  else                    return lbsearch (low, mid, target);
}

int main () {
  FILE *in = fopen ("mnotes.in", "r");
  FILE *out = fopen ("mnotes.out", "w");

  fscanf (in, "%d%d", &N, &Q);
  C[0] = 0;
  for (int i = 0; i < N; i++) {
    fscanf (in, "%d", B[i]);
    C[i+1] = C[i] + B[i];
  }

  for (int i = 0; i < Q; i++) {
    int j;
    fscanf (in, "%d", &j);
    fprintf (out, "%d\n", lbsearch (0, N-1, j) + 1);
  }

  return 0;
}