Today's contest had some pretty interesting problems; I particularly liked Problem C and Problem D. I'm going to describe my solution to D which I think is quite nice (and results in simple code). I don't doubt that there are even easier solutions to the problem, so please enlighten me if you have one :).

A nice observation we can make about any valid sequence is the following. Consider the positions of any 0 and any m in the circle. There are two paths from 0 to m. We observe that if any valid sequence exists, then there exists one for which, along each of these paths, the value never decreases twice in a row (that is, we can think of each path as "increasing" with some oscillation). Suppose this does happen in our sequence, i.e. we have something like

where j < i - 1 so i, i - 1, ..., j + 1, j is the decreasing sequence. Then we note that j + 1 appeared somewhere between 0 and i, so we can take the values j, j + 1 and move them directly after the j + 1 that was between 0 and i (easy to see that the sequence is still valid). Repeating this for whenever we have a decrease of two or more gives us paths that never decreases twice in a row.

Now with our transformation and observation, we can come up with the method of checking whether or not the histogram can produce a valid sequence. To do so, first place a 0 on the circle. Then we have L = c₀ - 1 zeros left to place. Note, however, that each zero must be adjacent to a one. So in fact there must be at least L + 2 ones to "hide" all of the zeros from the rest of the numbers (one on each side and one for each additional zero). If there are fewer than that many, it is impossible. After placing the remaining zeros and ones arbitrarily (but alternating) on each side of the initial 0, we see that there are L = c₁ - (L + 2) ones remaining. By the same argument, we know how many twos there must be (again, L + 2). We can continue like this until we get to m. If there are L remaining values of m - 1, we need c_m = L + 1 to complete the circle (one to be the "end" and one for each additional m - 1). If this is true, then it is possible and otherwise it is not.

Note that the above placement strategy works because of the observation we made (we know we can use the small numbers greedily) and the fact that it doesn't matter how many of each number we put in each path as long as they end in the same value.

int a[100100], c[100100];

int main() {
  int n; cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  sort(a, a+n);
  int m = a[n-1]-a[0];
  if (n % 2 == 1 || m > n/2 || m == 0) { cout << "NO" << endl; return 0; }

  memset(c, 0, sizeof(c));
  for (int i = 0; i < n; i++) c[a[i]-a[0]]++;

  bool poss = true;
  int L = c[0]-1;
  for (int i = 1; i < m; i++) {
    if (c[i] < L+2) { poss = false; break; }
    c[i] -= (L+2); L = c[i];
  }
  poss = poss && (c[m] == L+1);
  cout << (poss ? "YES" : "NO") << endl;
  return 0;
}