Competitive Programming Guide

CP Handbook to jedno miejsce dla wszystkich miłośników programowania konkurencyjnego, ponieważ zawiera wszystkie algorytmy i struktury danych. Również każdy temat zawiera przykłady i nierozwiązane problemy do praktyki.

Programowanie konkurencyjne to sport, mam na myśli dosłownie. Weź udział w jakimkolwiek sporcie, weźmy pod uwagę krykieta, po raz pierwszy wchodzisz do nietoperza. Huśtawka i spudłowanie, zrób to kilka razy, a w końcu trafisz jednego za linę. Rozważ konkurs programowy w metaforyczny sposób gry w krykieta. Skompiluj kod i prześlij, możesz otrzymać WA (złą odpowiedź).

Dokonaj zmian w kodzie, a ostatecznie otrzymasz swój pierwszy AC (Zaakceptowana / Prawidłowa odpowiedź). Pozwól, że dam ci do zrozumienia, około 20% pytań w konkursie programistycznym to prosta konwersja zwykłego angielskiego na kod twojego ulubionego języka programowania.

Wkrocz do tego, nauczysz się niepisanych zasad gry, gdy grasz mocniej i stajesz się lepszy.

 I uwierz mi, nie musisz znać żadnego algorytmu „fantazyjnej nazwy” ani struktury danych, aby zacząć. Słyszałeś kiedyś o „Waft shot”, ale jesteś najlepszym pałkarzem na swojej ulicy, prawda?

Dobra, pokonajmy pierwsze 20% problemów programistycznych.

Musisz wiedzieć:

Pośrednie trzymanie dowolnego języka programowania

Język angielski! Konwertuj angielski na kod!

Weźmy przykładowy problem tego poziomu: Straszne Chandu

Wszystko, co musisz zrobić, to odczytać wiersz wejściowy ze STDIN i wydrukować odwrotną stronę tego wiersza do STDOUT. Śmiało, złóż wniosek. Znajdź swój pierwszy AC. Chcieć więcej? Mamy ładunki w dziale ćwiczeń. Poszukaj tych z tysiącami poprawnych zgłoszeń.

Okej, teraz jesteś gotowy, aby podjąć prawdziwe wyzwanie. Trzymaj się mocno, nurkujemy głębiej.

Musisz wiedzieć:

1. Algorytmy sortowania i wyszukiwania

2. Hashowanie

3. Teoria liczb

4. Chciwa technika

Co ważniejsze, musisz dowiedzieć się, co, kiedy i gdzie je zastosować. To staje się naprawdę trudne i dlatego, aby pomóc początkującym poczuć się pewnie, przeprowadzamy serię konkursów jako Code Monk. Przed każdym konkursem publikujemy samouczek na określony temat, a później w konkursie problemy dotyczą tylko tego konkretnego tematu. Polecam przejrzeć samouczki i rozwiązać pytanie lub dwa na każdy temat.

Do tej pory zdałeś sobie sprawę, że pytania są tak sformułowane, aby oszukiwać nasz sposób myślenia. Czasami, jeśli przekształcisz zwykły angielski na kod, skończysz na werdykcie TLE (Przekroczono limit czasu). Musisz nauczyć się zestawu nowych technik i algorytmów, aby poradzić sobie z ograniczeniami czasowymi. W niektórych przypadkach na ratunek przychodzi programowanie dynamiczne (DP). Rzeczywiście, być może już intuicyjnie użyłeś tej techniki. W każdym konkursie zawsze można znaleźć co najmniej jedno pytanie, które może rozwiązać DP.

Zauważysz także, że istnieją pytania, których nie da się rozwiązać za pomocą struktur danych liniowych.

1. Teoria grafów

2. Disjoint Set Union (Union-find)

3. Minimalne drzewo opinające

Ten zestaw struktur danych doprowadzi cię dość daleko. Co więcej, pomyślałbyś, że prawdziwą sztuką jest modyfikacja technik, które znasz, aby rozwiązać pytanie. W ten sposób można rozwiązać wszystkie pytania na poziomie łatwym, średnim i średnim.

Wszyscy jesteście gotowi na pierwsze miejsce w rankingach Wyzwania krótkiego programowania, po prostu utrzymujcie stałą wytrwałość. Jak już wspomniałem, jest to sport, nie opanujesz go, dopóki go nie wykonasz. Śmiało, weź udział w krótkim konkursie, poznaj swoje mocne i słabe strony i zobacz, jak radzisz sobie z trybem adrenaliny, gdy zegar tyka.

Trzymaj się własnej logiki tak długo, jak to możliwe, w końcu wymyślisz coś podobnego do algorytmu wymaganego do rozwiązania pytania. Musisz tylko to wyszczotkować. Kilka z tych technik pomoże ci rozwiązać niektóre z najtrudniejszych problemów.

1. Drzewo segmentu

2. Algorytmy ciągów

3. Próby, drzewo sufiksów, tablica sufiksów.

4. Ciężki rozkład lekki

5. Kolorowanie wykresów, przepływ sieci

6. Dekompozycja Sqrta.

Pobierz ten Podręcznik CP i ciesz się nauką nowych rzeczy, nie zapomnij też KODOWAĆ je przy mniejszej złożoności czasu.