Notatki z omowienia zadan 1 dzien

For those who don’t know Polish: Below are solutions to algorithm problems from 1st day of informatics training camp.

(brak polskich literek, notowane na szybko)

Omowienie zadan 2006-07-20
Latwe i trudne

Prowadzacy: Filip Wolski

(niestandardowa gadka)

Dzien probny:
1. Ciagi artmetyczne
Autor: Maciej Laszcz

Dany jest ciag liczb calkowitych i trzeba w nim znalezc najdluzszy podciag bedacy ciagiem artmetycznym.

Zlozonosc: O(n^2*lgn)
Klasa: dynamik

1 -2 3 5 -3 7

Dla kazdej kolejnej liczby sprawdzamy wszystkie poprzednie liczby tworzac mozliwe ciagi (2 elementowe). Liczymy roznice i dlugosc hipotetycznego ciagu. Oprocz tego patrzymy na te struktury i probujemy jakis ciag przedluzyc. Wyszukiwanie w tych strukturach przyspieszamy za pomoca wyszukiwania binarnego lub hashowania.

2. Sumowanie

Mamy permutacje liczb od 1 do n. Sumujemy sasiednie element tworzac nowy ciag o jeden mniej liczny. Tak postepujemy tak dlugo az ciag bedzie mial 1 element.

Np.

3 1 2 4
4 3 6
7 9
16

Klasa: sprytniejszy brut

Latwo zauwazyc podobienstwo tego problemu do trojkata pascala. Rownowaznoscia operacji w dzialaniu jest mnozenie poczatkowe ciagu z odpowiednimi wartosciami w trojkatu Pascala i sumujemy.
Trojkat pascala:

1
1 1
1 2 1
1 3 3 1

Przyklad mnozenia:
1*3+3*1+3*2+1*4

Korzystajac z tego faktu, sprawdzamy wszystkie mozliwosci w kolejnosci leksykograficznej.

Dzien 1:
3. Perly

aacca
bacac
baaaa
bbdda

Litery symbolizuja perly. Jas chce wyciac najdluzszy sznur z perel tego samego typu.
(FIXME: sznur ma grubosc 1 perly)

Trzeba zastosowac algorytm DFS. Nalezy chodzic tylko po tych samych perlach. Jesli dojdzie sie rozgalezienia (w szczegolnosci punkt poczatkowy), trzeba pamietac wyniki 2 najlepszych zapuszczen defesow i probowac je zlaczyc (ewentualnie dlugosci z ktorej przyszlismy).

2. Jas prawoskretny

Jas rozwozi pizze. W plaszczyznie 2 jest miasto i miejsca gdzie dostarczy pizze. Kazde 2 miejsca sa polaczono w lini prostej drogi. Jas nie lubi odwiedzac 2 razy tego samego miejsca, wiec tego nie robi. Znajdz trase ktora przechodzi przez wszystkie punkty i moze skrecac tylko w prawa strone (zgodnie z wskazowkami zegara).

Klasa: geometria obliczeniowa
Rozwiazanie: wypukla otoczka
Zlozonosc: O(n*lgn)

3. Pizza

Jas zaplacil za pizze i musi wydac reszte kolegom. W kraju kazdy nominal dzieli wszystkie wieksze.

Zlozonosc: O(n*k)

Wydawac kolejnym klientom w najwiekszych mozliwych nominalach. Uwagi implementacyjne: posortowac nominaly.
4. Kumple

Trzeba podzieli ludzi na 2 grupy, ktore bylyby je “jak najbardziej” rownoliczne. Problemem jest to ze czesc osob chce koniecznie byc z kims lub _nie zyczy_ sobie kogos widziec w tej samej grupie.

Klasa: grafowe i dynamik

Ten problem rozwiazujemy w dwoch etapach. W pierwszym rozpatrujemy niezalezne grupy (takie ktore nie maja miedzy soba relacji) w drugim laczymy grupy miedzy ktorymi nie ma relacji.

Latwo zauwazyc ze relacja przyjazni lub wrogosci jest wzajemna. Zakladamy dla pierwszej nieprzydzielonej osoby, ze nalezy do pierwszej grupy. Liczymy wszystkie konsekwencje. I postepujemu tak az wszystkie osoby beda przydzielone. Latwo zauwazyc ze przy kazdym razie gdy zakladamy ze ktos nalezy do grupy pierwszej to jest to niezalezna podzbior problemu. Latwo
zauwazyc ze mozemy “odwracac” przynaleznosci. Tworzymy tablice roznic (w liczebnosci).

Np.:

Res: value:0
Team 1: 1 6
Team 2: 5 4
Res: value:1
Team 1: 7
Team 2:
Res: value:2
Team 1: 2 3
Team 2:

Teraz ten problem rozwiazuje tak jak dyskretny problem plecakowy. Dynamicznie liczymy wszystkie mozliwosci i szukamy tego ktory najblizszy by liczbie polowy sumy wszystkich roznic.

5. Odzysk
(FIXME: nie dokonca zrozumialem Filipa Wolskiego, jesli ktos ma cos lepszego to niech przysle)

Probujemy odzyskac ciag. Mamy dane mozliwe wartosci w ciagu i liczby:
a1,a1+a2, … , a1+a2+…+an-1+an
an+an-1+…+a1, an-1+…+a1, … , a1
w dowolnej kolejnosci.

Sortujemy wszystkie liczby i patrzymy czy sumujac dowolne dwie rozne liczby rowno odalone od srodka daja ta sama sume. Jesli nie to nie istnieje taki ciag.

Majac te pary probujemy je wstawiac od zewnetrznych do dwoch wejsciowych ciagu. Sprawdzamy wszystkie mozliwosci. Jesli znajdziemy poprawna to odtwarzamy pierwotny ciag z wejsciowych ciagow.

Zlozonosc: O(n^2)

1. Filip • 2006-07-21 15:55

   Jestem aż tak przewidywalny, że nawet standardowe gadki mam ? ;(

Leave a Comment

Name:
E-mail:
URI:
Enter this code: