Omowienie zadan 2 dzien

Omowienie zadan 2006-07-21
Dzien 2

Zadania trudniejsze

1. Hydraulik

Obracanie rur tak, zeby sie nic nie wylewalo.

Przeksztalcamy klocki na male grafy.

zakonczenie -> 1 wierzcholek i 4 krawedzie
…

“Tworzymy” z planszy szachownice pomalowana na dwa kolory. Wierzcholki malujemy na kolor taki na jakim polu stoi lub owrotnie (jeden wierzcholek I-). Wtedy laczymy przeciwstawne kolory. Dalej tworzymy graf dwudzielny stosujac maksymalne skojarzenie. W kazdym grafie wszystkie nieskojarzone krawedzi sa rurami. Jesli nie istnieje pelne maksymalne skojarzenie to zadanie to nie ma rozwiazania.

Zlozonosc: O( (n+k)*sqrt(n) ) n -> ilosc pol, k -> ilosc krawedzi
Klasa: algorytmy grafowe

(TODO: zalaczyc rysunek)

2. Polaczenia

Mamy dana prostokatna plansze. Kazde pole moze miec wartosci ‘*’, 0, 1, 2, 3, 4. Niektore pola maja byc polaczone z sasiednimi polami (gora, dol, prawo, lewo). Te z cyframi maja miec dokladnie tyle sciezek jaka wartosc. ‘*’ moze miec 0 sciezek lub 2 i wiecej.

Zakladamy ze mamy czesc wierszy rozwiazanych. Jedyne co potrzebujemy wiedziec o tych wierszach to z jakich miejsc wychodza sciezki na “zewnatrz”. Probujemy rozwiazac jedno sasiednie pole w ponizszym wierszu. Tak postepujemy az zapelni sie caly wiersz i tak dalej do konca.

Na koncu zeby otrzymac cofamy sie odtawarzajac najlepsze rozwiazanie:

Streszczenie: przegladanie wszystkich mozliwosci z spamietywaniem, tak zeby sie nie cofac

Zlozonosc: O(2^m*nm) m -> liczba kolumn, n -> iczba wierszy

Klasa: dynamik

3. Dzialki trojkatne

Dla danego zbioru punktow, znajdz liczbe trojkatow, ktore zawieraja dokladnie 3 punkty, z ktorych kazdy jest w wierzcholku. 2 dowolne punkt nie pokrywaja sie

Dla kazdego punktu sortujemy pozostale wzgledem katow, potem sprawdzamy wszystkie mozliwe trojkaty zawierajace te wierzcholki. Sprawdzamy czy jakis inny go “blokuje”. “Blokuje” czyli ostatni punkt jaki tworzy trojkat jest zawarty w rozpatrywanym nastepnym trojkacie.

Klasa: geometria obliczeniowa
Zlozonosc: O(n^2*lgn)

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)

After science camp in Miedzieszyn

Last Saturday (6 May 2006) I returned from a two-week science camp in Miedzieszyn (near Warsaw, Poland). It was organized by KFnrD. There were plenty of various activities. Activities such as workshops and lectures were chooseable and concerned on specific area. There were also evening talks where all participants were welcomed.

The list of all activities that I participate in:

• Workshops:
  they consist of many lectures, exercises and usually project.
  1. Operating Systems
     A series of following topics: computers architecture, linux kernel internals, file system architecture, debugging and profiling, real time systems, task schedule…
     Exercises such as writing simple modules to linux’s kernel, optimizing programs (mainly memory use), “playing with” user mode linux …
     Project work: write an extension to linux kernel (module, or simply add code) that will collect information about files, blocks, inodes read at boot time. Then use this information to put it all those files together in order they were used. This should reduce time needed to boot.
     Status of project: This project was a bit hard. We try to collect all information, but at last our “best” working solution was getting informations from translation dentry to inode. My strange idea was to create user space program which use inotify and place it in initrd. This solution could work but have two major drawbacks. Firstly, it get info only about whole files, nothing about blocks. Secondly, what’s more important, it’s impossible to use recursive inotify (unlike old dnotify) and it’s hard to put watch on every directory.
  2. Design Patterns
     We learned about various aspects of object-oriented programming and design models and patterns. I will describe them later on this blog.
     Exercises: design architecture for given application.
• Lectures:
  plus questions, consultations and discussion. All in one event.
  1. What promise quantum informatics? (prof. Marek Ku?, physics)
  2. Poland way to Euro (prof. El?bieta Kawecka-Wyrzykowsk, economics)
  3. Metric holomorphical invariant (PhD Armen Edigarian, mathematics)
  4. Singularities of functions and mappings (prof. Stanis?aw Janeczko, mathematics)
  5. Randomness and order (prof. Tomasz ?uczak, mathematics)
  6. Physics of whip sound (prof. Piotr Piera?ski, physics)
  7. Bernoulli Lemniscate (prof. Marek Bo?ejko, mathematics)
  8. About a few algorithm problems (prof. Wojciech Rytter, informatics)
  9. Difficult theorem about curves on plane (PhD Adrian Langer, mathematics)
• Others: formal talks (by a scientist, poet or professor etc.),
  there was a lot of them (I was on about 15). They were usually short (< 1.5h) and require only general knowledge. Interesting, but I don’t learned a lot from them.
  Some famous speakers:
  • prof. Jan Madey
  • prof. Pawe? Wieczerzak
  • poet Julia Hartwig
  • director and prof. Krzysztof Zanussi
  • prof. Andrzej S?kowski
  • writer Antoni Libera

What’s more, in Miedzieszyn there is loads of opportunities to share ideas. Strange conceptions like version file system or peer2peer file system occurres ;-). It is also good place to exchange knowledge. For example a person next to you is writing new os from scratch (for education reason only). Now it only boot, handle with memory and support a few posix functions.

From the time I arrived I’m reading KDE/Qt docs, doing simply apps to be prepared for Google Summer of Code. I will desceibe some things that I worked out. I’m also busy at school, despite many lessons were canceled because of the final exams. My CAE exams will also be soon.

Before the final stage

3rd stage of OI is coming soon. It will take place in Sopot (a city on the coast, near Gda?sk and Gdynia). It’s quite far from my home (about 600km direct), so I will go there by train next Monday (27.03.2006). Now, as always, I’m preparing for it. I’m solving problems from websites and I’m looking through IT literature during recent days.

Yet another good information, today I received mail that I qualified for interdisciplinary camp. Rumour says that we will be analysing linux kernel booting process, and try speed it up by placing file blocks in order they are loaded. In the other hand, I hope that the teachers from my high school are not going to kill me, because of the lessons I missed (and going to miss).

I’m planning to do a research work on public transport. Mainly about synchronising bus service and how delays affect timetables. To do this in a nice way I’m learning how to use Qt toolkit to make user interface. I like this library, because it’s intuitive to use and multiplatform.

I will also participate in Polish young parliament contest (the translation of title is awful). at first I didn’t won’t to take part in it, but after teacher read my homework, he convinced my to give it a try. I need to send them essay about dependence between ecology and politics/economy. I would also like to write to another competition about unemployment and its reasons. However, because of lack of the time, I prefer to concentrate on thing that I’m already in.

I also must admit that I’m playing on Warsaw stock market. Of course virtually, because my savings are too small to avoid be eaten by provisions. I now having about 17,5% income before tax, but counting provisions. I get it between end of the September and now (6 months). Quick summary:

• Best investment: Comarch – stocks price almost doubled, since I bought it.
• Worse investment: LPP – stock fall down from 915 to about 690 PLN.

Our politics is like a swamp (like in most of democratic countries, unless your favourite party is in charge). They discuss even about making dependent of our national bank, who control our currency. Because coalition is breaking down, there is a little chance of tax reform and so. What is optimistic, despite lack of law changes, our economic growth is smoothly, 4.5% increase of PKB in the beginning of 2006. It’s good that our companies are making money without looking at politics.