paladin8's blog

By paladin8, 12 years ago, In English
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 :).

Impossibility

Let us denote the sequence by a1, ..., an and assume it has been sorted already. We can note immediately that there are some easy cases we can rule out. If n is odd, by a parity argument it is impossible. Moreover, let m = an - a1, i.e. the range of the values. If m = 0 it is impossible since n ≥ 3, and if m > n / 2 it is impossible since we cannot get from a1 to an and back going around the circle. Now that these cases are out of the way we move on to the actual algorithm.

Transformation

It's natural to transform the input we're given into a form that's easier to work with, i.e. a histogram. As such, we define ci to be the number of values aj with aj - a1 = i for i = 0, 1, ..., m. Now we replace each ai with ai - a1 so that they are all in the range [0, m].

Observation

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

0, 1, ..., i - 1, i, i - 1, ..., j + 1, j, j + 1, ..., m - 1, m

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.

Validation

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 = c0 - 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 = c1 - (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 cm = 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.

Code


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;
}
  • Vote: I like it
  • +44
  • Vote: I do not like it

| Write comment?
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

A bit easier, I find:

For a circle "min, min+1, min+2,...,max,max-1,max-2...,min+1", the histogram is 1 2 2.... 2 2 1.

There's a solution if the histogram is an overlapping sum of histograms of circles.
You can modify the circles greedily until each one is empty:  Pick one the circles on the left side.  Remove two pieces of the circle so that the min value is increased by one.  In the histogram, it means removing 1 to the two leftmost bins.  That's implemented in this solution .
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Just to "complete" the thread about this problem. I solved it with a maxflow approach, I didn't prove it properly (I will keep thinking, maybe I just had got lucky with the cases), well the main idea was build a bipartite graph with even numbers in one side and odd in the other (because this difference by one) and  give for each node 2 of capacity (instead of 1 as usual) to get the maximum bipartite match (doubled this time), each vertex will have degree 2, and if they are all connected in the same component we have the cycle and the answer is YES, otherwise NO.
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please give me an idea of how to solve Div-2 C statues.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use BFS to find all cells at all moments of time of possible Maria positions. Since after 8 steps all statues are falls from board you can take in account only 20 moments — after 20 steps Maria already for sure either lose or win.

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I solved the problem with your idea

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but what the hell (4007914) you are submit, young padawan? Look at, for example, this solution: 866518 and use the force!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2D ?