[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2
Author Message
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
Удобный и мощный 3-строчник для дебага (C++17 эдишн)

С++ 17 на DL тоже поддерживается в g73

Отладка в C++

И здесь
много всякой всячины по С++ с Codeforces

Просмотрите – может найдёте что-то полезное
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
Дорешивание с июня 2018

IOI 2018
Костяной - 3
Харрасов - 2
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
#68 G. Очередная мемная задача цифровая динамика (ДП по числу) на 7-мерном массиве - или состояния обозначаются специальными структурами, и эти структуры хранятся в map

Если вы полностью уверены в своих навыках программирования, вы можете просто написать эту динамику на 7-мерном массиве. Я очень не хотел начинать это писать (однако смотря на решения участников, я вижу, что это звучит куда страшнее, чем выглядит в коде), поэтому в авторском решении по этой задаче все состояния обозначаются специальными структурами, и эти структуры хранятся в map. Это довольно известная техника: когда то решение динамическим программированием, которое вы придумали, включает в себя очень сложные состояния и переходы, иногда лучше для состояний динамики написать свою структуру, и хранить структуры в хэш-таблице или map. У этой техники есть несколько плюсов:

иногда ее гораздо проще писать (код может получиться длиннее, чем у такого же решения на многомерном массиве вместо структур, но писать и понимать его сильно проще);
если много состояний являются недостижимыми, то мы их вообще никак не будем рассматривать;
иногда можно очень легко добавлять различные оптимизации, связанные с общим числом различных состояний динамики. Например, количество различных значений mask1 и mask2 может быть очень большим, но его можно уменьшить следующим образом: как только мы найдем пару цифр в mask1 и mask2, которые подходят для x? и y?, можно заменить эти маски на какие-то значения, которые будут обозначать, что это состояние уже «закончено» (мы нашли нужную нам пару цифр), и никогда больше эти маски не менять.
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
[Reference] Github reference project for ICPC contests/programming contests in general

https://github.com/Nisiyama-Suzune/LMR/tree/master/src

After the World Final this year, I think that instead of let the reference material we used rot in a depository, it is better if we can collaborate and polish a piece of reference that can serve as the foundation for any team that wishes to best their skill in contests, or for any person who wishes to achieve a higher rating on Codeforces. After all, who can say that they haven't thought of "color their name red" on this website?

So here it is, Allow me to present you Luna's Magic Reference, which is the foundation we used to develop our reference for the ICPC contests last year: https://github.com/Nisiyama-Suzune/LMR

I hope that you can try to utilize it in the next contest, point out bugs or confusing parts if you find any, and share your own masterpiece of code that can potentialy benefit the whole community.

Thanks in advance and wish you all high rating! 
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
My winning theory in IOI 2018 & 2019 — Why I won 2 golds in IOI

A Beautiful Technique for Some XOR Related Problems
Про хеширование без домножения (ну и без деления, конечно)
Lecture #3 — Exchange arguments (sorting with dp)
Relation in GCD and FIbonacci +1
Number Theory for Competitive Programming
About a general reader / writer for STL-Structures
Useful Builtin functions of GCC Compiler

E-Maxx Algorithms in English


Избранные задачи
#71 G. Инди альбом автомат Ахо-Корасик
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
Курс Михаила Мирзаянова "Алгоритмы и структуры данных"

1 Heap data structure, heap properties and operations. HeapSort. Priority queue. Other heap applications. Mergeable heaps: binomial heap, pairing heap, randomised meldable heap.
2 Fenwick tree. Description and motivation. Implementation of Fenwick tree. Generalisation for higher dimensions. Skip list data structure. Implementation details. Indexable skiplist.
3 Segment trees. Top-down implementation. Bottom-up implementation. Segment trees applications. Persistent data structures. Persistent stack, persistent array. Persistent Fenwick and segment trees.
4 Cartesian trees, treap data structure. Merge and split operations. Treap implementation in detail. Treap applications.
5 Treaps with implicit keys. Ropes. Segment reverse operation. Examples of problems.

6 Introduction to strings. String searching (matching) problem. Pattern pre processings. Z-function, prefix-function. Their applications. Knuth–Morris–Pratt algorithm. Matching finite state machine.
7 Multiple pattern matching. Trie data structure. Aho-Corasick algorithm. Implementation details. Dynamic programming on a trie.
8 String hashing. Rabin-Karp algorithm. Fast substrings comparison with hashes. Suffix array. LCP array. Efficient construction algorithm. Applications.
9 Suffix tree. Ukkonen's algorithm. Suffix tree construction from LCP array. Suffix tree applications.
10 Suffix automaton. Size bounds. Linear Algorithm. Using suffix automata as an index for approximate string searches.
11 Introduction to automata theory. Formal languages. Context-free languages. Formal grammars. Context-free grammars. NFA, DFA, convert NFA to DFA. Build automaton by regular expression.

12 LL(1) parser. Arithmetic expressions parsing. Shunting-yard algorithm. Simplified Pascal language parsing and interpretation.
13 Algorithms for traversing a graph. DFS. Properties. DFS search tree. Edges classification. Linear bridge-finding algorithm. Linear articulation points finding algorithm. Strongly connected components. Tarjan's strongly connected components algorithm.
14 Tree problems. Bottom-up approach. LCA problem. LCA algorithms.
15 Bipartite graphs. Konig's criterion. Problems: maximum matching, minimum edge cover, maximum independent vertex set, minimum vertex cover. Connection of the problems. Berge's lemma. Kuhn algorithm. Kuhn algorithm properties. Minimal vertex cover by maximum matching. Cover DAG by minimal number of paths.
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
Образовательный раздел Codeforces: beta-тестирование

EDU: Новое занятие курса "ITMO Academy: пилотный курс" — Z-функция строки

Теперь курс "ITMO Academy: пилотный курс" состоит из двух занятий:
z-функция
суффиксный массив 
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
An IDE for competitive programming: fetch testcases from websites, test on testcases in one click, and more
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
EDU: Новое занятие курса "ITMO Academy: пилотный курс" — Дерево отрезков, часть 1

Таким образом в нашем курсе сейчас три занятия:

дерево отрезков, часть 1,
z-функция,
суффиксный массив. 
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
Ratings, Statistics & Divisions
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
EDU: Новое занятие курса "ITMO Academy: пилотный курс" — Дерево отрезков, часть 2


Таким образом в нашем курсе уже четыре занятия:

дерево отрезков, часть 1,
дерево отрезков, часть 2,
z-функция,
суффиксный массив.
 
Mihail Dolinskiy

Topics: 1626
Messages: 39507

My Profile
EDU: Новое занятие курса "ITMO Academy: пилотный курс" — Двоичный поиск

В нашем курсе уже пять занятий (и скоро будет больше!):

двоичный поиск,
дерево отрезков, часть 1,
дерево отрезков, часть 2,
z-функция,
суффиксный массив. 
 
Forum Index ->Олимпиадное программирование ->Методика подготовки к IOI 2007 - ... 1, 2
Time:0,093