Pull to refresh
  • by relevance
  • by date
  • by rating

Олимпиадное хобби. Разминка

Sport programming *
Sandbox
В качестве хобби, я решаю олимпиадные задачки по программированию. Это помогает отвлечься от повседневных проблем, позволяя на часок другой уйти от мира в собственный астрал. Мой мозг, благодаря этому хобби, находится в постоянной спортивной форме.

Я решил, что неплохо было бы поделиться с Вами алгоритмами, размышления, результатами, а также получить качественную критику моих путей решения задач.
Будем брать задачу, разбирать ее по частям, анализировать, выдумывать различные пути решения, выбирать лучший, а потом нести на суд «великих судей». Для многих, по моему мнению, такой час разгрузки будет очень полезным, а кому-то просто будет интересно посоревноваться и придумать свой алгоритм.

Задачи я буду брать с сайта http://uva.onlinejudge.org/, где располагается достаточно большая коллекция задач на любой вкус, и там же можно проверить свое решение. Выбирать буду случайным образом и всегда доводить начатое до финального решения, которое ознаменуется оценкой «Accepted» (Принято). Для решения этих задач нам потребуется знание одного из языков программирования: c, c++, java, pascal, а также терпение, логика и базовое знание английского языка, т.к. условия задач мы получаем на английском языке.

Итак, начнем мы с простой задачки из набора «Для новичков» для разминки, чтобы проверить свои способности.
Читать дальше →
Total votes 53: ↑46 and ↓7 +39
Views 5K
Comments 19

Разбор задач Hacker Cup Qualification Round + перенос Facebook Hacker Cup Online Round I

Python *
Sandbox
Facebook Hacker Cup 2011 проходит в 4 раунда — квалификационный, два онлайн раунда и финальный, в главном офисе.

Квалификационный раунд, анонсированный официально Хабром завершился успешно.
Результаты раунда говорят о 5846 игроках, прошедших в первый онлайн тур.
Участникам квалификационного раунда предлагалось 3 задачи, для прохождения достаточно было правильного решения любой из них.

А вот первый онлайн раунд, прервав ближе к завершению, перенесли из-за технических проблем минимум на неделю:
We've decided to push back the remaining subrounds of round 1 until we are sure that they can run smoothly. Updates will follow here, but you can safely assume that the subrounds will not occur at least until next weekend.
image
Читать разбор задач Facebook Hacker Cup 2011 Qualification Round
Total votes 50: ↑42 and ↓8 +34
Views 4.4K
Comments 75

Динамика по подотрезкам: базовые вещи и «одна хорошо, а две лучше»

Algorithms *
Добрый вечер.
В этом посте я разберу задачу B «Дубы» с практического тура городской олимпиады школьников Санкт-Петербурга по информатике.
Задача эта на динамическое программирование по подотрезкам и идея решения интересна тем, что удобнее посчитать две динамики вместо одной. Если вас заинтересовало (незнание динамики не освобождает, но будет труднее) — добро пожаловать.
Читать дальше →
Total votes 32: ↑25 and ↓7 +18
Views 15K
Comments 11

Динамическое программирование. Классические задачи

Algorithms *
Sandbox
Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.

Во многих олимпиадных задачах по программированию решение с помощью рекурсии или полного перебора требует выполнения очень большого числа операций. Попытка решить такие задачи, например, полным перебором, приводит к превышению времени выполнения.

Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.
Читать дальше →
Total votes 105: ↑97 and ↓8 +89
Views 266K
Comments 72

Персистентные структуры, часть 1: персистентный стек

Algorithms *
Sandbox
Я заметил, что на хабре было достаточно много постов о таких классических структурах данных, как стек, очередь, хип; рассматривались так же дерево отрезков и множество различных деревьев поиска, но очень мало внимания уделялось персистентным структурам данных. В этом цикле статей я хотел бы поговорить как раз о них. Так уж сложилось, что я достаточно давно занимаюсь олимпиадным программированием, так что рассматривать я их буду с точки зрения моего опыта применения персистентных структур в этой области.
Читать дальше →
Total votes 51: ↑47 and ↓4 +43
Views 29K
Comments 42

Динамическое программирование. Спичечная модель

Sport programming *
Sandbox
Здравствуйте, Хабрахабр. В этом после я хочу рассказать о динамическом программировании на примере решения одной из задач. С этой задачей я недавно столкнулся на портале олимпиадных задач (ссылка указана в конце). Сразу перейду к делу.

Задача


Профессор Самоделкин решил изготовить объемную модель кубиков из спичек, используя спички для рёбер кубиков. Длина ребра каждого кубика равна одной спичке.
Для построения модели трех кубиков он использовал 28 спичек.
Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков?
Все числа в задаче не превышают 2·109.

Технические условия

Входные данные
Одно число N – количество кубиков.
Выходные данные
Одно число – количество спичек.

Я решил эту задачу используя динамическое программирование, но ее можно было решить и другими способа, и даже просто одной формулой — которую мы выведем в конце.

«Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.» — Класс задач которые решаются динамическим программированием.
И наша цель добиться решения, согласно описанию задач на динамическое программирование, в котором решение для текущих параметров строится на решении предыдущих.
Читать дальше →
Total votes 34: ↑29 and ↓5 +24
Views 21K
Comments 15

Теория Игр и функция Шпрага-Гранди

Sport programming *
Sandbox
Доброго времени суток, уважаемое Хабрасообщество.

В последнее время все большее и большее распространение получает олимпиадное программирование, неотъемлемой частью которого является знание алгоритмов (и, разумеется, умение их применять).

Я хочу рассказать вам основы теории Игр, доказать функцию Шпрага-Гранди, разобрать несколько классических impartial-задач и проиллюстрировать их кодом на python.
Читать дальше →
Total votes 53: ↑52 and ↓1 +51
Views 30K
Comments 30

Полиномиальные хеши и их применение

Algorithms *
Sandbox
Здравствуй, хабр. Сегодня я напишу, как можно использовать полиномиальные хеши (далее просто хеши) при решении различных алгоритмических задач.

Введение


Начнем с определения. Пусть у нас есть строка s0..n-1. Полиномиальным хешем этой строки называется число h = hash(s0..n-1) = s0 + ps1 + p2s2 +… + pn-1sn-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а si — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).

Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство.
Читать дальше →
Total votes 74: ↑69 and ↓5 +64
Views 59K
Comments 41

Задачка из реальной жизни: Как восстановить дерево процессов в Linux

Sport programming *System Programming *Algorithms *
Мы разрабатываем проект CRIU (Checkpoint/Restore in Userspace) и у нас возникла достаточно интересная задача о том, как восстановить оригинальное дерево процессов. Я предлагаю вам попытаться решить ее.

Задача


CRIU — это утилита, которая позволяет сохранить состояние процессов на диск и постановить их позднее на этой или на любой другой машине. Одной из подзадач восстановления является нахождение последовательности действий для того, чтобы восстановить дерево процессов. Входные данные содержат набор параметров для каждого процесса: уникальный идентификатор (PID), ссылку на родителя (PPID), идентификатор сессии (SID).

image
Читать дальше →
Total votes 20: ↑17 and ↓3 +14
Views 8.6K
Comments 12

Разбор задачи «Зеркало в коридоре» и негодование

Programming *Mathematics *
Sandbox
Хочу более подробно разобрать задачу из публикации «Олимпиады по программированию среди школьников», а также показать, что она действительно нетривиальная. Хотя в результате программа и состоит из трех присваиваний и двух сравнений, прийти к этому результату не так уж и просто, тем более, если нет под рукой справочника по аналитической геометрии.


Читать дальше →
Total votes 42: ↑31 and ↓11 +20
Views 22K
Comments 53

Разбор задач финала Технокубка 2016

VK corporate blog Sport programming *Programming *
Компания Mail.Ru Group совместно с МФТИ и МГТУ им. Н. Э. Баумана подвели итоги Технокубка — первой олимпиады по программированию для учащихся 8–11-х классов. За звание самого талантливого молодого программиста сражались школьники более чем из 20 городов России и СНГ. Всего на олимпиаду зарегистрировались 2132 участника, 113 приехали на очный финал, который проходил одновременно на двух площадках: в МГТУ им. Н. Э. Баумана и МФТИ. Награждение состоялось в офисе Mail.Ru Group. Олимпиада проходила на платформе Codeforces.



У ребят было три часа на решение семи задач, которые составляли преподаватели и специалисты ведущих технических вузов России. Последнюю, самую сложную, решил только один из участников — Владислав Макеев, который в итоге и занял первое место. Всего призёрами стали 27 участников олимпиады, они разделили между собой дипломы I, II и III степени. Победители (диплом I степени) получили дополнительные восемь баллов для поступления, обладатели дипломов II и III степени — по шесть баллов. Первое место занял Владислав Макеев (Москва, 11-й класс), второе — Александра Дроздова (Нижний Новгород, 10-й класс), третье — Григорий Резников (Москва, 11-й класс). Полный список победителей доступен по ссылке. В этом посте мы предлагаем вам ознакомиться с задачами финала и их решениями.
Читать дальше →
Total votes 21: ↑20 and ↓1 +19
Views 11K
Comments 1

Разбор задачи с Международной олимпиады по информатике IOI 2016

Sport programming *Entertaining tasks C++ *
image

В августе этого года в Казани прошла Международная олимпиада по программированию для школьников — IOI 2016. Российская команда стала второй в общем зачете.

Один из серебряных медалистов, Денис Солонков из г. Мытищи, сделал разбор задачи «Обнаружение молекул», которая предлагалась участникам олимпиады.

Денис Солонков — многократный победитель Всероссийских олимпиад по программированию и Moscow CTF School, выпускник Школы программистов, ныне студент ВШЭ.
Читать дальше →
Total votes 10: ↑9 and ↓1 +8
Views 21K
Comments 5

Технокубок: итоги финального раунда и разбор задач

VK corporate blog Sport programming *Programming *

image


Пятого марта прошел финальный раунд Технокубка — олимпиады по программированию для школьников. В этом году в ней приняли участие 3000 человек, 400 из которых прошли в финал. Предлагаем вам взглянуть итоги финала и разбор задач:


A. Андрюша и носки
B. Место встречи изменить нельзя
C. Андрюша и разноцветные шарики
D. Иннокентий и футбольная лига
E. Подземная лаборатория
F. Аксель и Марстон в Битландии
G. Андрюша и живые барьеры
H. Автобусы и интранет


Что такое Технокубок? Это олимпиада по программированию для учащихся 8-11 классов, организуемая Mail.Ru Group совместно с МГТУ им. Баумана и МФТИ. Она состоит из трех этапов: ознакомительного (онлайн), отборочного (онлайн) и заключительного (очно).

Читать дальше →
Total votes 23: ↑22 and ↓1 +21
Views 7.3K
Comments 1

Эксперименты над олимпиадной задачей

SQL *Microsoft SQL Server *
Так получилось, что я попал в магистратуру, и как то гуляя мимо кафедры на глаза попалась олимпиадная задача по 1С. Кратко задача звучит так: «Есть записи продажи за каждый день, необходимо найти наибольший период когда план выполнялся». А потом когда я гулял со спящей дочкой у меня встав вопрос, а сколькими способами это можно сделать на SQL. Решения будут на основе MS SQL.
Читать дальше →
Total votes 9: ↑6 and ↓3 +3
Views 4.1K
Comments 4

Динамическое программирование в олимпиадных задачах

Algorithms *Mathematics *
Привет!

Недавно решал задачи с архива Timus Online Judge и наткнулся на раздел под названием задачи динамического программирования. Задачи такого типа вызывают у меня особый интерес, потому что зачастую такой подход обеспечивает быстроту и элегантность решения. Что же такое — динамическое программирование?

Динамическое программирование — это подход к решению задач, при котором происходит разбиение на подзадачи, которые «проще» в сравнении с исходной. Слово «динамический» близко по значению к «индуктивный»: предполагается, что известен ответ для какого-то значения $k$, и хочется найти ответ для $k+1$. В математике это называется индуктивным переходом, и составляет основную идею динамического программирования.

Простые примеры


Наиболее яркой и показательной задачей является задача вычисления $n$-ого числа последовательности Фибоначчи.
Читать дальше →
Total votes 13: ↑12 and ↓1 +11
Views 13K
Comments 3

Джулия в лабиринте

Abnormal programming *Sport programming *Programming *Julia *
Tutorial


Разбирая одну олимпиадную задачу мы отправимся по петляющим коридорам генерации лабиринтов и их прохождения, а также увидим, что на языке Julia простота реализаций алгоритмов граничит с их псевдокодом.

Читать дальше →
Total votes 28: ↑28 and ↓0 +28
Views 7.9K
Comments 12

Ozon go school: Как не нужно проводить отбор

Programming *Algorithms *Go *Personnel Management *IT career

Go School


Как вы знаете, в середине мая Ozon объявил о запуске школы программирования на языке Go. Обещали следующее:

  • бесплатное обучение
  • возможность получить знания по реальной разработке на Go от Ozon
  • возможность получить работу в Ozon

Чтобы попасть в школу, нужно было:

  • иметь опыт промышленного программирования
  • пройти тестовые задания по программированию на платформе Яндекс.Контест
  • пройти skype-собеседования

Уже в ходе отбора выяснилось, что онлайн школа будет только до момента, пока эпидемиологическая ситуация не наладится. Впрочем, иногородним жителям все-таки была обещана возможность проходить обучение по интернету.

Тогда же было озвучено число студентов, которое готовы принять в Школу — около 40 человек.

Так понемногу условия поступления прирастали новыми пунктами, среди добавленных также значилось:

  • желательно проживать в Москве
  • быть гражданином РФ
  • возраст старше 18 лет

Но все это выяснилось уже позже, а пока предложение Ozon привлекло многих разработчиков. Пора было приступать к первому этапу: прохождению теста.

Вроде все выглядело неплохо, условия не такие сложные и вполне выполнимые.


Читать дальше →
Total votes 139: ↑134 and ↓5 +129
Views 33K
Comments 107

Спортивное программирование — социальный лифт в IT. Как его использовать школьнику, родителям школьника и разработчику?

IT-People corporate blog Sport programming *Algorithms *Studying in IT

С какого возраста можно обучать ребенка программированию и какой язык лучше выбрать? Как попасть на самые крутые IT-направления в лучшие вузы? Становятся ли дети разработчиков разработчиками? Как попасть на стажировку в Яндекс или на работу в Google?

Обо всем этом нам рассказывает Михаил Рубинчик — лидер и главный тренер по спортивному программированию в Уральском федеральном университете и основатель онлайн-школы по спортивному программированию SPGuide. Подробности под катом

Читать далее
Total votes 10: ↑6 and ↓4 +2
Views 5.6K
Comments 27