codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

129.md (4283B)


      1 Source: https://codeforces.com/blog/entry/3196
      2 
      3 Today's contest had some pretty interesting problems; I particularly liked [Problem C](//codeforces.com/contest/128/problem/C) and [Problem D](//codeforces.com/contest/128/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 :).
      4 
      5   
      6 
      7 ### Impossibility
      8 
      9 Let us denote the sequence by *a*1, ..., *a**n* 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* = *a**n* - *a*1, 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 *a*1 to *a**n* and back going around the circle. Now that these cases are out of the way we move on to the actual algorithm.
     10 
     11 ### Transformation
     12 
     13 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 *c**i* to be the number of values *a**j* with *a**j* - *a*1 = *i* for *i* = 0, 1, ..., *m*. Now we replace each *a**i* with *a**i* - *a*1 so that they are all in the range [0, *m*].
     14 
     15 ### Observation
     16 
     17 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
     18 
     19 0, 1, ..., *i* - 1, *i*, *i* - 1, ..., *j* + 1, *j*, *j* + 1, ..., *m* - 1, *m*
     20 
     21 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.
     22 
     23 ### Validation
     24 
     25 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*0 - 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*1 - (*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.
     26 
     27 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.
     28 
     29 ### Code
     30 
     31 ```
     32 
     33 ```
     34 
     35 ```
     36 int a[100100], c[100100];
     37 
     38 int main() {
     39   int n; cin >> n;
     40   for (int i = 0; i < n; i++) cin >> a[i];
     41   sort(a, a+n);
     42   int m = a[n-1]-a[0];
     43   if (n % 2 == 1 || m > n/2 || m == 0) { cout << "NO" << endl; return 0; }
     44 
     45   memset(c, 0, sizeof(c));
     46   for (int i = 0; i < n; i++) c[a[i]-a[0]]++;
     47 
     48   bool poss = true;
     49   int L = c[0]-1;
     50   for (int i = 1; i < m; i++) {
     51     if (c[i] < L+2) { poss = false; break; }
     52     c[i] -= (L+2); L = c[i];
     53   }
     54   poss = poss && (c[m] == L+1);
     55   cout << (poss ? "YES" : "NO") << endl;
     56   return 0;
     57 }
     58 ```