CERC 2010: Szkice rozwiązań

28.11.2010

I: Insults

Treść (pdf) | wyślij rozwiązanie.

Dla danego słowa dobrze ustawionych nawiasów, zadanie polega na znalezieniu leksykograficznie następnego słowa z dobrze ustawionymi nawiasami. Jeden typ nawiasów to litery a i e, zaś drugi to litery i oraz o. Opiszemy rozwiązania na przykładzie słowa w = aaioee. W tym celu próbujemy znaleźć leksykograficznie pierwsze słowo z dobrze rozstawionymi nawiasami zaczynające się od następujących prefiksów:

  • w[1..5]i = aaioei
  • w[1..5]o = aaioeo
  • w[1..4]i = aaioi
  • w[1..4]o = aaioo
  • w[1..2]o = aao
  • w[1..1]e = ae
  • w[1..1]i = ai
  • w[1..1]o = ao
  • e
  • i
  • o

Kończymy przeglądanie prefiksów, kiedy uda nam się znaleźć takie słowo. Zbiory słów charakteryzowanych przez te prefiksy są rozłączne i zawierają wszystkie słowa, które są alfabetycznie późniejsze niż w.

Ale jak znaleźć słowo z dobrze rozstawionymi nawiasami zaczynające się od danego prefiksu długości k? Na początku należy obliczyć niezbalansowanie nawiasów po przeczytaniu takiego prefiksu: po przeczytaniu liter a oraz i wkładamy je na stos i zdejmujemy je z niego po przeczytaniu odpowiednio liter e oraz o. Niech f będzie liczbą elementów na stosie po przetworzeniu takiego prefiksu.

Następnie sprawdzamy, czy na pozostałych n-k miejscach możemy zbalansować f nawiasów, które są już na stosie. Jeśli f > n-k, to nie jest to możliwe. W przeciwnym przypadku jest to możliwe a leksykograficznie najmniejsze słowo składa się z prefiksu, po którym następuje (potencjalnie pusty) ciąg a(n-k-f)/2e(n-k-f)/2, a całość jest zakończona f literami balansującymi stos.

Ponieważ można obliczać zawartość stosu dla każdego prefiksu na podstawie stosu dla poprzedniego prefiksu w stałym czasie, całkowity czas działania wynosi O(n).

Informacje dodatkowe

Zadanie to było stosunkowo proste do wymyślenia i implementacji, jednak na zawodach drużyny zabrały się za nie dość późno.

Przykładowe obelgi wraz z odpowiedziami pochodzą z utarczek słownych piratów z gry Monkey Island, zaś ostateczna obelga pochodzi z filmu Monty Pythona. Zostały one wykorzystane bez wiedzy i woli oryginalnych autorów oraz przy zdecydowanym sprzeciwie organizatorów CERC, którzy uważali te obelgi za obraźliwe. I słusznie!

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com