Matematická olympiáda – kategorie P

Řešení úloh ústředního kola (2. soutěžní den) 52. ročníku

P-III-4 Poklad kapitána Flinta

Úloha, převedená do podoby v matematice běžnější, zní: Je dán konvexní N-úhelník a M jeho neprotínajících se tětiv dělících N-úhelník na díly. Nalezněte maximální počet dílů, z nichž žádné dva nemají společnou stranu.

Uvažujme následující graf G. Vrcholy grafu budou odpovídat jednotlivým dílům N-úhelníka, přičemž dva vrcholy budou spojeny hranou, pokud jim odpovídající díly mají společnou stranu. Graf G zřejmě bude souvislý a navíc nebude obsahovat žádný cyklus. Uvnitř cyklu by totiž ležela alespoň jedna stěna grafu G. Té musí odpovídat nějaký průsečík v nakresleném N-úhelníku. Tento průsečík však rozhodně nemůže ležet na okraji N-úhelníka, a máme tak spor s tím, že žádné dvě tětivy se neprotínají.

Souvislý graf bez cyklů je strom a naše úloha se tím zjednodušuje na nalezení maximální nezávislé množiny vrcholů (tj. takové množiny vrcholů, že žádné dva vrcholy z této množiny nejsou spojeny hranou) ve stromu. Maximální nezávislou množinu můžeme určit prohledáváním do hloubky. Na počátku si označíme všechny vrcholy jako přijatelné do nezávislé množiny. Začneme v libovolném vrcholu prohledávat strom. Když se vracíme z nějakého vrcholu, který je označen jako přijatelný, přidáme ho do nezávislé množiny a jeho otce odznačíme. Když takto projdeme celý graf, máme vybranou maximální nezávislou množinu. Nezávislost vybrané množiny je zřejmá. Proč ale bude vybraná množina maximální? Označme si vybranou nezávislou množinu A a dále si vezměme maximální nezávislou množinu B, která se od naší vybrané množiny liší v nejméně vrcholech. Nyní se podívejme na takový vrchol v, ve kterém se A a B liší a který je nejvzdálenější od vrcholu, ve kterém začalo prohledávání do hloubky. Případ, kdy v je v B a ne v A, nastat nemůže, protože když jsme nějaký vrchol v nevzali do A, tak pouze proto, že byl sousedem nějakého vrcholu u pod ním zařazeného do A. Protože v je nejvzdálenější vrchol, ve kterém se A a B liší, musí být u obsažen i v B, a tedy B také nemůže obsahovat v. Může tedy nastat pouze situace, že v je obsažen v A a není obsažen v B. Pokud ale v přidáme do B a z B vyřadíme otce v (pokud v ní byl), bude B stále maximální nezávislá množina a přitom se bude lišit v méně vrcholech, což je spor s výběrem B. Vybraná nezávislá množina A musí být proto skutečně maximální.

Zkonstruovat výše popsaný graf a na něm pak provést prohledání do hloubky je zbytečně pracné. My budeme graf prohledávat bez jeho explicitní konstrukce. Nejdříve si tětivy zorientujeme tak, aby každá tětiva začínala ve vrcholu s nižším číslem a přidáme pomocnou tětivu začínající v prvním a končící v posledním vrcholu. Tětivy si pomocí přihrádkového třídění setřídíme vzestupně podle jejich počátku, tětivy začínající ve stejném vrcholu pak sestupně podle jejich konce. Nyní postupně procházíme vrcholy N-úhelníku v pořadí od vrcholu s číslem jedna po vrchol s číslem N. Při procházení si udržujeme zásobník s tětivami, od nichž jsme viděli začátek, ale ne konec. U každé tětivy na zásobníku si navíc pamatujeme, zda je přijatelná. Vždy, když začneme zpracovávat nový vrchol, nejdříve ze zásobníku odebereme tětivy, které v tomto vrcholu končí. Pokud je odebíraná tětiva označena jako přijatelná, zvětšíme velikost nezávislé množiny a odznačíme tětivu pod ní v zásobníku. Po odebrání všech končících tětiv přidáme na zásobník všechny tětivy začínající v daném vrcholu a označíme je jako přijatelné. Pak pokračujeme do dalšího vrcholu N-úhelníku. Výpočet skončíme po projití všech vrcholů N-úhelníku.

Uvedený algoritmus přesně odpovídá dříve popsanému prohledávání do hloubky. Každá tětiva totiž jednoznačně koresponduje s hranou v grafu, která spojuje vrcholy odpovídající dílům odděleným tětivou. Uložení pomocné tětivy (1,N) na zásobník odpovídá vstupu do vrcholu, ze kterého začínáme prohledávání. Uložení další tětivy na zásobník odpovídá přejití po odpovídající hraně dolů (směrem od vrcholu, ve kterém začalo prohledávání), vybrání tětivy ze zásobníku pak návratu zpět po hraně. Při prohledávání do hloubky jsme si označovali vrcholy, které lze přidat do nezávislé množiny. V upraveném algoritmu místo vrcholu značíme tu hranu, po které jsme do vrcholu poprvé vstoupili. Algoritmus má časovou i paměťovou složitost O(N) (tětiv nikdy nemůže být více než N-3).

#include <stdio.h> #include <stdlib.h> #define MAXV 30000 /* Maximální počet vrcholů */ #define MAXR 30000 /* Maximální počet řezů */ /* Struktura pro jeden řez */ struct rez { int a, b; }; int rezu, vrcholu; /* Počet řezů a vrcholů */ struct rez r[MAXR]; /* Jednotlivé řezy */ int vpoc[MAXV]; /* Počty řezů začínajících v jednotlivých vrcholech */ /* Načte vstup */ void nacti(void) { int pom, i; FILE *vstup; if (!(vstup = fopen("poklad.in", "r"))) exit(1); fscanf(vstup, "%d %d", &vrcholu, &rezu); for (i = 0; i < rezu; i++) { fscanf(vstup, "%d %d", &r[i].a, &r[i].b); r[i].a--; r[i].b--; if (r[i].a > r[i].b) { pom = r[i].a; r[i].a = r[i].b; r[i].b = pom; } } fclose(vstup); /* Přidáme ještě fiktivní řez mezi prvním a posledním vrcholem */ r[rezu].a = 0; r[rezu].b = vrcholu-1; rezu++; } /* Setřídí řezy podle počátku a konce */ void setrid(void) { struct rez r1[MAXR]; /* Jednotlivé přeskládané řezy */ int vrchind[MAXV]; /* Index, kde začínají řezy z/do daného vrcholu */ int vrchpoc[MAXV]; /* Počty řezů z/do daného vrcholu */ int i; /* První průchod třídění */ for (i = 0; i < vrcholu; i++) vrchpoc[i] = 0; /* Spočteme počty řezů do jednotlivých vrcholů */ for (i = 0; i < rezu; i++) vrchpoc[r[i].b]++; vrchind[0] = 0; for (i = 1; i < vrcholu; i++) vrchind[i] = vrchind[i-1] + vrchpoc[i-1]; /* Přerovnáme řezy podle cílového vrcholu */ for (i = 0; i < rezu; i++) r1[vrchind[r[i].b]++] = r[i]; /* Druhý průchod třídění */ for (i = 0; i < vrcholu; i++) vrchpoc[i] = 0; for (i = 0; i < rezu; i++) vrchpoc[r1[i].a]++; vrchind[0] = 0; for (i = 1; i < vrcholu; i++) vrchind[i] = vrchind[i-1] + vrchpoc[i-1]; /* Přerovnáme řezy podle zdrojového vrcholu (bereme je sestupně podle cílového vrcholu) */ for (i = rezu-1; i >= 0; i--) r[vrchind[r1[i].a]++] = r1[i]; } /* Spočte, kolik částí mapy může kapitán rozdat */ int spocti(void) { int casti = 0; /* Počet částí */ int zasvrch = 0; /* Vrchol zásobníku */ int zas[MAXR]; /* Zásobník na zpracovávané řezy */ int zasuzit[MAXR]; /* Značka, že příslušná část mapy může být rozdána */ int actvrch = 0, actrez = 0; /* Aktuální vrchol a řez mnohoúhelníka */ while (actvrch < vrcholu) { while (zasvrch && r[zas[zasvrch-1]].b == actvrch) { if (zasuzit[zasvrch-1]) { /* Část oddělená tímto řezem může být použita? */ casti++; if (zasvrch > 1) zasuzit[zasvrch-2] = 0; } zasvrch--; } while (actrez < rezu && r[actrez].a == actvrch) { zas[zasvrch] = actrez++; zasuzit[zasvrch++] = 1; } actvrch++; } return casti; } int main(void) { FILE *vystup; nacti(); setrid(); if (!(vystup = fopen("poklad.out", "w"))) exit(1); fprintf(vystup, "%d\n", spocti()); fclose(vystup); return 0; }

P-III-5 Vážení

Použijeme upravený třídící algoritmus mergesort. V programu si budeme vytvářet jednosměrné spojové seznamy, jež budou mít svým jednotlivým prvkům přiřazeny mince. Váhy mincí budou od počátku ke konci seznamu tvořit rostoucí posloupnost. Mince stejné hmotnosti budou přiřazeny témuž prvku seznamu. Tento seznam budeme realizovat tak, že každý jeho prvek bude obsahovat ukazatel na následující prvek seznamu a na strom, který obsahuje mince (téže hmotnosti) přiřazené tomuto prvku. Samotný strom bude binární strom, ve kterém má každý prvek žádného nebo dva syny. Čísla mincí ve stromě budou uchovávána v jeho listech a každý uzel tohoto stromu bude obsahovat číslo některé mince ze svého podstromu (v naší implementaci to bude nejmenší číslo mince ve stromě).

Základem programu bude rekurzivní procedura vytvor(prvni,posledni), která vytvoří jednosměrný spojový seznam popsaný v prvním odstavci. Tento seznam bude obsahovat všechny mince s čísly od prvni do posledni. Pokud jsou čísla prvni a posledni shodná, procedura vytvoří jednoprvkový seznam. Jeho jediný prvek bude ukazovat na strom tvořený jedním uzlem, který bude obsahovat číslo prvni=posledni. Pokud jsou čísla prvni a posledni různá, procedura nejdříve rozdělí interval tvořený čísly od prvni do posledni na dva intervaly polovičních délek a na každý z nich se rekurzivně zavolá. Takto získáme dva lineární spojové seznamy s vlastnostmi popsanými v prvním odstavci. Z nich naše procedura vytvoří jeden.

Výsledný seznam budeme vytvářet od začátku, a to následujícím způsobem: Na některou z mincí ve stromě hlavy (tj. prvního prvku) prvního ze seznamů a na některou z mincí ve stromě hlavy druhého seznamu zavoláme funkci |porovnej|. Pokud je mince hlavy prvního seznamu lehčí, odpojíme hlavu od prvního seznamu a připojíme ji na konec výsledného seznamu; poté pokračujeme porovnáním hlav nově vzniklé dvojice seznamů. Pokud je naopak mince hlavy druhého seznamu lehčí, připojíme na konec výsledného seznamu hlavu druhého seznamu a pokračujeme s druhým seznamem bez jeho původní hlavy. Zbývá případ, kdy mince obou hlav mají stejnou hmotnost. V tomto případě připojíme na konec výsledného seznamu prvek, který ukazuje na strom, jehož levý podstrom je strom hlavy prvního seznamu a pravý podstrom je strom hlavy druhého seznamu; od obou seznamů následně odpojíme jejich hlavy. Takto pokračujeme, dokud jeden nebo oba z našich dvou seznamů nejsou prázdné. Pokud je jeden z nich neprázdný, nezapomeneme ho připojit na konec výsledného seznamu.

Vytvořit celý program je nyní již snadné: Nejprve ze souboru vahy.in načteme počet mincí N. Poté zavoláme proceduru porovnej s parametry prvni=1 a posledni=N. Nakonec vypíšeme čísla v listech stromů (zleva doprava) ve výsledném seznamu; každý strom vypíšeme na samostatný řádek souboru vahy.out, a to v pořadí, v jakém stromy odpovídají prvkům seznamu. Čísla na každém řádku jsou setříděna (z konstrukce stromů patřícím prvkům seznamu) a hmotnosti mincí v pořadí dle řádků jsou rostoucí (dle vlastností vytvářeného seznamu). Zbývá si rozmyslet, že náš algoritmus neprovádí zbytečné volání funkce porovnej, a určit jeho časovou složitost.

Nejprve dokážeme indukcí dle délky intervalu určeného parametry při volání procedury vytvor, že náš program neprovádí zbytečné volání funkce porovnej. Procedura vytvor volá funkci porovnej pouze na dvojice prvků z intervalu specifikovaného parametry procedury vytvor. Pokud je tento interval jednoprvkový, dokazované tvrzení platí z triviálních důvodů. V opačném případě, se nejprve vytvoří dva seznamy rekurzivním voláním procedury vytvor a ty se následně sloučí. Při slučování dvou seznamů je funkce porovnej volána pouze na dvojice mincí z různých seznamů (tedy výsledek takového volání není určen výsledky volání funkce porovnej při rekurzi). Vzhledem k tomu, že porovnáváme z každého seznamu minci s nejmenší vahou (a mince s menšími vahami jsme zařadili již do výsledného seznamu), nemůže být vztah hmotností mincí z dotazované dvojice určen předchozími dotazy. Můžeme tedy uzavřít, že žádné volání funkce porovnej není zbytečné.

Hloubka rekurzivního volání procedury vytvor je O(log N) (N je počet mincí), neboť při každém volání se délka intervalu specifikovaného parametry funkce zmenší na polovinu. Na sloučení dvou seznamů je třeba čas úměrný délce výsledného seznamu. Protože na každé úrovni volání se libovolná mince vyskytuje právě v jednom seznamu, je čas strávený algoritmem během procedur vytvor na jedné úrovni rekurze lineární, tj. O(N). Celková časová složitost je tedy O(N log N). Libovolná mince se vyskytuje při běhu programu vždy právě v jednom seznamu, a tedy paměťová složitost programu je O(N).

#include <stdio.h> #include <stdlib.h> #include "vahy_lib.h" struct tuzel { int prvek; struct tuzel *levy, *pravy; }; struct tseznam { struct tuzel *strom; struct tseznam *dalsi; }; struct tseznam *vytvor(int prvni, int posledni) { struct tseznam *vysledek, *seznam1, *seznam2, **ocas, *pomocna; if (prvni==posledni) { vysledek=malloc(sizeof(struct tseznam)); vysledek->dalsi=NULL; vysledek->strom=malloc(sizeof(struct tuzel)); vysledek->strom->prvek=prvni; vysledek->strom->levy=vysledek->strom->pravy=NULL; return vysledek; } seznam1=vytvor(prvni,(prvni+posledni)/2); seznam2=vytvor((prvni+posledni)/2+1,posledni); ocas=&vysledek; while (seznam1&&seznam2) { switch (porovnej(seznam1->strom->prvek,seznam2->strom->prvek)) { case 0: (*ocas)=malloc(sizeof(struct tseznam)); (*ocas)->strom=malloc(sizeof(struct tuzel)); (*ocas)->strom->prvek=seznam1->strom->prvek; (*ocas)->strom->levy=seznam1->strom; (*ocas)->strom->pravy=seznam2->strom; pomocna=seznam1; seznam1=seznam1->dalsi; free(pomocna); pomocna=seznam2; seznam2=seznam2->dalsi; free(pomocna); break; case -1: *ocas=seznam1; seznam1=seznam1->dalsi; break; case +1: *ocas=seznam2; seznam2=seznam2->dalsi; break; } ocas=&((*ocas)->dalsi); } *ocas=seznam1?seznam1:(seznam2?seznam2:NULL); return vysledek; } void vypis_strom(FILE *soubor, struct tuzel *uzel) { if (uzel->levy) { vypis_strom(soubor,uzel->levy); vypis_strom(soubor,uzel->pravy); } else fprintf(soubor,"%d ",uzel->prvek); } void vypis_seznam(FILE *soubor, struct tseznam *seznam) { while (seznam) { vypis_strom(soubor, seznam->strom); fprintf(soubor,"\n"); seznam=seznam->dalsi; } } int main(void) { FILE *soubor; int N; struct tseznam *seznam; soubor=fopen("vahy.in","r"); fscanf(soubor,"%d",&N); fclose(soubor); seznam=vytvor(1,N); soubor=fopen("vahy.out","w"); vypis_seznam(soubor,seznam); fclose(soubor); return 0; }