A editora “DMK Press” publicou um livro “Programação das Olimpíadas” com o subtítulo “Estudando e melhorando algoritmos em competições”. Tornou-se uma lufada de ar fresco para todos os interessados, preparando e se preparando para participar, ou apenas planejando no futuro, um tipo de atividade intelectual como vários eventos de programação esportiva. Na Rússia, eles não estão bem familiarizados.
A edição russa do livro “Guide to Competitive Programming” (Springer International Publishing AG) foi publicada com o apoio do Instituto de Física e Tecnologia de Moscou e seu chefe Alexei Maleev, do Mail.Ru Group, além do projeto ICPC de oficinas de Moscou.
“A programação das Olimpíadas está se tornando cada vez mais popular a cada ano entre estudantes e estudantes. Um ótimo exemplo disso foi o fato de que em 2019, nós, as Oficinas de Moscou do ICPC, realizaremos em novembro os décimos preparativos para a Copa do Mundo em diferentes partes do mundo, eles já passaram em Cingapura, Europa e América do Sul e Rússia - de Vladivostok a Moscou. No início de outubro, o Concurso de Programação de Moscou foi realizado em Moscou, no qual 2.284 pessoas participaram de 18 locais de universidades de Moscou - este é um recorde absoluto para a escala da competição, realizada com o apoio de Rosmolodezh.
Estamos muito felizes com o interesse animado dos rapazes e estamos prontos para apoiá-lo de todas as formas - por exemplo, para estudantes de universidades de Moscou, realizamos treinamento gratuito para o ICPC com a participação dos melhores treinadores. E, é claro, é sempre útil que os participantes consolidem material, analisem tarefas e aprimorem seus conhecimentos. Portanto, estou muito feliz que seu livro tenha aparecido e parabenizo todos nós por isso. Esperamos que, nas finais do ICPC em Moscou, em junho de 2020, já haja aqueles que leem e se tornam os heróis da segunda edição atualizada. ”
Alexey Maleev, diretor da final da Copa do Mundo ICPC 2020 em Moscou, vice-reitor do MIPT, fundador do projeto ICPC de Oficinas de Moscou.
O "Guia de Programação Competitiva" foi traduzido para o russo do inglês. Além de inglês e russo, a publicação em coreano foi lançada.
O autor do livro é Antti Laaxsonen, professora e pesquisadora da Universidade de Helsinki Aalto (Finlândia) [3], com vasta experiência no ensino de programação e algoritmos, e o treinador da equipe finlandesa em competições internacionais de programação. Ele tem uma classificação alta de 2347 e o status de "mestre internacional" no portal Codeforces sob o apelido "pllk" [4]. Em 2008, ele A. Laaxsonen se tornou um dos organizadores da Olimpíada de Informática em seu país. Em 2016 - supervisor científico da Olimpíada do Báltico em Informática.
O público-alvo do livro está todo interessado e / ou trabalhando no campo da programação das Olimpíadas. Mas, para a total assimilação do material, é necessário o conhecimento dos fundamentos da programação, enquanto o autor não exige que o leitor experimente projetar algoritmos e participar de olimpíadas. Tudo isso nos permite recomendar este trabalho a uma ampla gama de leitores interessados. Para iniciantes, isso se tornará uma introdução à moderna programação das olimpíadas, especialistas experientes ajudarão a sistematizar o conhecimento, se tornarão uma ferramenta de referência para eles.
A submissão do material no livro é realizada do simples ao complexo. A princípio, ele se familiariza com as metas e objetivos do livro, com a programação da Olimpíada, a coleção de tarefas CSES [5] e outros livros relevantes sobre a programação da Olimpíada.
Tendo recebido a base teórica necessária, o leitor estará pronto para seguir em frente. Técnica de programação é o próximo tópico. Nele, o autor incluiu os conceitos básicos da linguagem C ++ (padrão C11), que implementa todos os exemplos do livro; análise de algoritmos recursivos e operações bit a bit.
Nos capítulos do livro, o leitor poderá encontrar informações sobre a maioria dos tópicos "padrão" e exemplos de implementação de algoritmos oferecidos aos participantes na programação de olimpíadas: estruturas de dados, programação dinâmica, algoritmos gráficos e algoritmos de árvore, consultas de intervalo e trabalhar com strings.
Separadamente, gostaria de destacar vários capítulos do livro. Por exemplo, o capítulo "Problemas de design selecionados para algoritmos". Ele incluiu algoritmos com visualização paralela de descargas, análise de depreciação e localização dos valores mínimos. Ao leitor são oferecidos algoritmos para encontrar a distância de Hamming, a solução do problema de atingibilidade em gráficos, o método de dois ponteiros, pesquisa ternária, minimização de somas e outros tópicos interessantes para a "Olimpíada" e seus treinadores.
Como exemplo, darei um exemplo de tarefas do capítulo "Perguntas selecionadas sobre o design de algoritmos".
Vamos considerar algoritmos com visualização paralela de bits nos quais operações bit a bit são usadas para processamento eficiente de dados. Em um caso típico, podemos substituir o loop for por operações bit a bit, o que reduz significativamente o tempo de execução do algoritmo.
Algoritmos de navegação paralela
Algoritmos com visualização paralela de dígitos são baseados no fato de que dígitos individuais de um número podem ser manipulados em paralelo usando operações bit a bit. Portanto, um dos métodos de projetar algoritmos é apresentar as etapas do algoritmo de forma que elas possam ser efetivamente implementadas usando operações bit a bit.
Distância de Hamming Distância de Hamming
hamming (a, b) entre as linhas aeb do mesmo comprimento é o número de posições nas quais essas linhas diferem. Por exemplo:
hamming (01101, 11001) = 2.
Considere a seguinte tarefa: considerando n strings de bits de comprimento k, calcule a distância mínima de Hamming entre duas strings. Por exemplo, para as linhas [00111, 01101, 11110], a resposta seria 2, porque
- hamming (00111, 01101) = 2;
- hamming (00111, 11110) = 3;
- hamming (01101, 11110) = 3.
O problema pode ser resolvido "de frente", calculando a distância de Hamming entre cada duas linhas. A complexidade de tempo de um algoritmo desse tipo é (n
k) Para calcular a distância entre as linhas aeb, use a seguinte função:
int hamming(string a, string b) { int d = 0 for (int i = 0; i < k; i++) { if (a[i] != b[i]) d++; } return d; }
Mas como as strings consistem em bits, a solução pode ser otimizada armazenando-as como números inteiros e calculando a distância entre elas usando operações bit a bit. Em particular, se k ≤ 32, as seqüências de caracteres podem ser armazenadas como valores do tipo int e, para calcular a distância, use esta função:
int hamming(int a, int b) { return __builtin_popcount(a^b); }
Aqui, a operação EXCLUSIVE OR constrói uma linha na qual as unidades estão nas posições em que aeb são diferentes. Em seguida, o número de dígitos da unidade é calculado pela função __builtin_popcount. A tabela mostra os resultados da comparação do algoritmo original e do algoritmo com uma visão paralela dos bits em termos de tempo de execução em um computador moderno. O algoritmo com visualização paralela de bits mostrou-se cerca de 20 vezes mais rápido.
Tabela: Tempo de execução dos algoritmos que calculam a distância mínima de Hamming para n cadeias de bits de comprimento k = 30
Os capítulos "Matemática" e "Geometria" não merecem menos atenção. Como o leitor já adivinhou, eles são dedicados à solução de problemas matemáticos e geométricos por meio da linguagem de programação C ++ e à construção de algoritmos apropriados. No capítulo "matemática", aguardamos cinco grandes tópicos: "Teoria dos números", "Combinatória", "Matrizes", "Probabilidade" e "Teoria dos jogos". E no “geométrico”: “Meios técnicos em geometria”, “Algoritmos baseados na linha de varredura”. Assim, a complexa apresentação da construção de algoritmos para resolver problemas matemáticos e geométricos faz do livro um "achado" para o "olimpíada", porque, no contexto de uma escassez de livros sobre esse assunto, isso é uma raridade.
Uma série de problemas, o autor decidiu colocar no capítulo "Tópicos adicionais". Seu desenvolvimento “às vezes pode ajudar na solução dos problemas mais difíceis das olimpíadas”. Estes são "Raiz quadrada em algoritmos", "E novamente sobre árvores de segmentos", "Duchi", "Otimização de programação dinâmica" e "Diversos". Com base no nome da explicação adicional, eles exigem subtítulos em árvores de segmentos e em coisas diferentes.
Quanto às árvores de segmentos, o leitor se familiarizará com a propagação lenta, árvores dinâmicas, estruturas de dados nos vértices, árvores bidimensionais. E em "Diversos" ele está esperando: uma reunião no meio (dividindo o espaço de pesquisa em duas partes, aproximadamente iguais, realizando uma pesquisa em cada parte e depois combinando os resultados), conjuntos de contagem, pesquisa binária paralela, conectividade dinâmica.
Complete as informações de referência do livro sobre matemática e uma extensa bibliografia (32 fontes).
Portanto, o livro "Programação das Olimpíadas" de Antti Laaxsonen é uma excelente introdução ao mundo da programação esportiva. Ao mesmo tempo, um maravilhoso guia de referência. O livro é adequado para iniciantes "olympiadnikov" e ajudará na organização do conhecimento experimentado. Será útil para treinadores.
Mais uma vez, observamos que todos os exemplos do livro são implementados na linguagem de programação C ++. Ele é mais procurado nas Olimpíadas. Mas alguém pode achar isso uma desvantagem do livro, porque outras linguagens são populares - Python, Java. Quem prefere essas linguagens de programação pode resolver os problemas propostos em um livro em seu idioma favorito. Este será um bom treino. Por fim, é precisamente na busca da solução ideal que as tarefas da Olimpíada são concluídas.
O artigo foi preparado por: Igor Shtompel, autor e apresentador da seção "Carreira \ Educação" na revista
"System Administrator"