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).
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(); }
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, \ldots, 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)$.