W zadaniu dany jest okrąg o długości $n$ oraz $m$ odcinków na tym okręgu. Należy znaleźć podział odcinków na dwa zbiory tak, aby odcinki z każdego zbioru pokrywały cały okrąg (lub stwierdzić, że taki podział nie istnieje).

Zadanie na prostej

Naturalne uproszczenie zadania na okręgu, to rozwiązanie najpierw wersji na prostej. Tak jest w podzadaniu 4, w którym mamy gwarancję, że żaden odcinek nie przecina punktu 0 na okręgu. Zatem można okrąg rozciąć w punkcie 0 i rozważać następujące zadanie: podzielić odcinki na dwa zbiory $U_{1}$ i $U_{2}$ tak, aby odcinki z każdego zbioru pokrywały cały przedział $[0 . . n]$ .

W zadaniach z pokrywaniem zwykle pomaga posortowanie odcinków po początkach lub końcach, a następnie zastanowienie się nad rozwiązaniem zachłannym lub używającym programowania dynamicznego, które przeglądają odcinki w tej kolejności.

Do naszego zadania istnieje rozwiązanie zachłanne. Sortujemy odcinki po początkach $a_{i}$ i będziemy je rozważać w tej kolejności. Trzymamy dwie zmienne $e_{1}$ i $e_{2}$ , oznaczające, że odcinki ze zbioru $U_{i}$ pokrywają przedział $[0 . . e_{i}]$ .

Rozważmy dołożenie odcinka $a_{i}$ i załóżmy bez straty ogólności, że $e_{1} \leq e_{2}$ . Jeśli $e_{1} < a_{i}$ , to rozwiązanie nie istnieje, bo nie będziemy w stanie już rozszerzyć zbioru $U_{1}$ , aby pokrył fragment $[e_{1}, a_{i}]$ (pozostałe odcinki mają jeszcze dalsze początki niż $a_{i}$ ).

Z kolei jeśli $b_{i} \leq e_{1}$ , to możemy ten odcinek dołożyć do któregokolwiek zbioru -- nie zmieni to naszej sytuacji.

W końcu dla $a_{i} \leq e_{1} < b_{i}$ dołożymy ten odcinek do zbioru $U_{1}$ , zmieniając $e_{1}$ na $b_{i}$ .

Dlaczego takie rozwiązanie jest poprawne? Jeśli $b_{i} \leq e_{2}$ , to dołożenie tego odcinka do zbioru $U_{2}$ nic nie zmienia. W końcu jeśli $e_{2} < b_{i}$ , to zmienimy $e_{2}$ na $b_{i}$ . Czyli przy dołożeniu do $U_{1}$ zmienimy parę $(e_{1}, e_{2})$ na $E_{1} = (b_{i}, e_{2})$ , a przy dołożeniu do $U_{2}$ na $E_{2} = (e_{1}, b_{i})$ . Z nierówności $e_{1} \leq e_{2}$ wynika, że para $E_{1}$ jest nie gorsza od $E_{2}$ .

Z uwagi na sortowanie, rozwiązanie działa w czasie $O (m \log m)$ :

const int N = 110000;
int n,m,a[N],b[N],idx[N];
char answer[N];
int endp[2];

void impossible() {
  printf("impossible\n");
  exit(0);
}

void ret() {
  printf("%s\n", answer);
  exit(0);
}

int main() {
  scanf("%d%d",&n,&m);
  REP(i,m) {
    scanf("%d%d",&a[i],&b[i]);
    a[i]--;
    idx[i] = i;
  }
  sort(idx, idx+m, [](int i, int j) { return a[i] < a[j]; });

  REP(i,m) {
    int id = endp[0] < endp[1] ? 0 : 1;
    if (endp[id] < a[idx[i]]) {
      impossible();
    }
    answer[idx[i]] = '0'+id;
    endp[id] = max(endp[id], b[idx[i]]);
  }
  if (min(endp[0], endp[1]) < n) {
    impossible();
  }

  ret();
}

Zadanie na okręgu

Inną standardową techniką, której można użyć w przypadku zadania z odcinkami na prostej lub okręgu, jest analiza odcinków, które zawierają się w sobie. Powiemy, że odcinek $i$ zawiera odcinek $j$ , jeśli $a_{i} \leq a_{j} \leq b_{j} \leq b_{i}$ . Dla uproszczenia załóżmy, że w przypadku odcinków o takich samych końcach musi być $i < j$ (dzięki temu relacja zawierania jest asymetryczna).

Zauważmy, że jeżeli odcinek $i$ zawiera odcinek $j$ , to nie ma sensu obu tych odcinków umieszczać w tym samym zbiorze $U_{k}$ . Zatem w takiej sytuacji, jeśli $i$ umieścimy w $U_{k}$ , to odcinek $j$ umieścimy w $U_{3 - k}$ .

Na początek wyznaczymy zbiór $W$ tych odcinków, które nie zawierają się w żadnym innym. Na prostej najpierw sortujemy odcinki po początkach $a_{i}$ , remisy rozstrzygając na korzyść odcinków dłuższych. Pierwszy odcinek umieszczamy w zbiorze $W$ . Następnie, gdy analizujemy odcinek $i$ -ty, to wystarczy sprawdzić, czy zawiera się on w ostatnio dodanym odcinku do $W$ . Jeśli nie, to dodajemy go do zbioru $W$ .

W przypadku okręgu sprawa jest nieco trudniejsza, bo musimy jakoś wyznaczyć pierwszy odcinek, który wrzucimy do zbioru $W$ . Można tutaj wziąć np. odcinek najdłuższy (bo na pewno nie będzie zawarty w żadnym innym).

Tak wygląda implementacja generowania zbioru $W$ :

int main() {
  scanf("%d%d",&n,&m);
  REP(i,m) {
    scanf("%d%d",&a[i],&b[i]);
    if (b[i] < a[i]) { b[i] += n; }
    a[i]--;
    idx[i] = i;
  }

  sort(idx, idx+m, [](int i, int j) {
      return a[i] < a[j] || a[i] == a[j] && b[i] > b[j]; });

  int longest = 0;
  REP(i,m) if (b[idx[longest]]-a[idx[longest]] < b[idx[i]]-a[idx[i]]) {
    longest = i;
  }
  REP(i,longest) {
    a[idx[i]] += n; b[idx[i]] += n;
  }

  sort(idx, idx+m, [](int i, int j) {
      return a[i] < a[j] || a[i] == a[j] && b[i] > b[j]; });

  REP(i,m) parent[i] = -1;
  idxk[k++] = idx[0];
  REP(i,m) if (i) {
    if (b[idx[i]] <= b[idxk[k-1]]) {
      parent[idx[i]] = idxk[k-1];
    } else {
      idxk[k++] = idx[i];
    }
  }

Zauważmy, że ponieważ żaden odcinek ze zbioru $W$ nie zawiera się w innym, to posortowanie ich po początkach daje taki sam ciąg, jak posortowanie ich po końcach. Niech zatem $W = {w_{1}, w_{2}, \dots, w_{k}}$ będzie taką kolejnością.

Okazuje się teraz, że jeśli istnieje poprawny podział odcinków na zbiory $U_{1}$ i $U_{2}$ , to odcinki ze zbioru $W$ można przyporządkować w prosty sposób.

Jeśli $k$ jest parzyste, to odcinki $w_{i}$ o nieparzystych indeksach wrzucamy do $U_{1}$ , a te o parzystych -- do $U_{2}$ .

Dlaczego jest to poprawne? Rozważmy dowolny fragment $[s, s + 1]$ i pokażmy, że jest on pokryty przez odcinki z dwóch zbiorów. Jeśli rozwiązanie istnieje, to musi istnieć jakiś odcinek $w_{i} \in W$ , który pokrywa ten fragment (bo wszystkie odcinki spoza $W$ zawierają się w odcinkach z $W$ ). Bez straty ogólności jest on w $U_{1}$ .

Jeśli $w_{i - 1}$ lub $w_{i + 1}$ również pokrywa ten fragment, to ponieważ są one w $U_{2}$ , kończymy dowód. W przeciwnym wypadku żaden inny odcinek z $W$ nie pokrywa $[s, s + 1]$ , więc musi istnieć jakiś odcinek spoza $W$ , który go pokrywa. Ale musi on być zatem zawarty w $w_{i}$ , tak więc należeć do zbioru $U_{2}$ , co też kończy dowód.

W przypadku $k$ nieparzystego, jeśli istnieje rozwiązanie, to musi w nim istnieć jakaś para kolejnych indeksów $w_{j}$ i $w_{j + 1}$ , które należą do tego samego zbioru w podziale. Pozostałe odcinki dzielimy na zbiory względem parzystości indeksów (tzn. nieparzyste przed $w_{j}$ oraz parzyste za $w_{j + 1}$ dajemy do zbioru $U_{1}$ ). Musimy zatem sprawdzić $k$ przypadków wyboru indeksu $w_{j}$ . Dowód poprawności jest podobny, jak w przypadku parzystego $k$ .

Zauważmy jednak, że znalezione przez nas rozwiązanie jest poprawne o ile rozwiązanie istnieje. Musimy zatem jeszcze sprawdzić jego poprawność:

  if (k % 2 == 0) {
    REP(i,k) answer[idxk[i]] = '0'+(i%2);
    if (check()) ret();
  } else {
    REP(ii,k) {
      answer[idxk[ii]] = '0';
      REP(j,k-1) answer[idxk[(ii+1+j)%k]] = '0'+(j%2);
      if (check()) ret();
    }
  }

  impossible();

Procedura sprawdzania poprawności będzie działać w czasie liniowym od $k$ :

bool check() {
  REP(i,m) if (parent[i] != -1) {
    answer[i] = '0'+'1' - answer[parent[i]];
  }

  REP(col,2) {
    int endp = -1, begp = -1;
    REP(i,m) if (answer[idx[i]] == '0'+col) {
      if (endp == -1) { begp = a[idx[i]]; endp = b[idx[i]]; }
      else if (endp < a[idx[i]]) {
        begp = a[idx[i]];
      }
      endp = max(endp, b[idx[i]]);
    }
    if (endp < begp+n) return 0;
  }

  return 1;
}

Ostatecznie zatem rozwiązanie działa w czasie $O (n^{2})$ .