def uniform_but_one_dataset(n, p):
  """Generates a dataset according to the AMS lower bound.

  Args:
    n: The size of the dataset
    p: The frequency moment (used as a parameter in the lower bound)

  Returns:
    A list of (key, value) tuples, where all keys have weight one, except for
    one key which accounts for half of the p-th frequency moment
  """
  elements = []
  for i in range(n):
    elements.append((i, 1))
  elements.append((1, (n**(1.0 / p)) - 1))
  return elements