Мы провели Kotlin Challenge: что в финале?

Утро понедельника? Отличное время вспомнить, что хорошего уже успело случиться, чтобы начать неделю с добрых новостей!

Осенью 2013-го мы затеяли Kotlin Challenge — соревнование по программированию для тех, кто был готов попробовать Kotlin, новый язык программирования для платформы Java. Записались несколько сотен человек, осенью прошли заочные тренировочные туры и четвертьфиналы, в феврале 2014-го — полуфинал, и наконец…

29 апреля 2014 года 23 финалиста встретились в нашем офисе на финале. Финал был очным, все разместились в конференц-зале и приступили к решению задач.

Задач было всего пять, на решение отводилось два часа. Ни одному участнику не удалось успеть решить все задачи, однако каждую задачу хоть кто-нибудь, да решил, так что сложность задач следует признать приемлемой.

Среди участников финала были как очень известные в олимпиадном программировании люди, так и менее именитые. Среди фигур, которые могут быть хорошо знакомы каждому читателю хаба «Спортивное программирование», стоит отметить Геннадия Короткевича, Петра Митричева, Романа Елизарова, Михаила Мирзаянова. В финал прошли программисты с разным опытом — и студенты, и уже остепененные разработчики. Один из финалистов, например, работает в Facebook, два других известны как организаторы олимпиад по программированию в своих регионах.

Участники приехали из четырех разных стран (Белоруссия, Германия, Россия, США), меньше половины были из Санкт-Петербурга. Порадовал результат МФТИ: из Долгопрудного приехали аж два студента этого ВУЗа. Тем из финалистов, кто привез в Питер хорошую погоду 29 апреля — отдельное спасибо!

После напряженной борьбы определились призеры: первое место завоевал Геннадий Короткевич. Геннадий до того уже стал чемпионом мира на ACM ICPC в 2013, вышел в финал TopCoder Open в том же 2013, а в 2014 победил в Facebook Hacker Cup.

Второе место — у Петра Митричева, который дважды выигрывал TopCoder Open, однажды Google Code Jam, а в 2003 году завоевал золотую медаль ACM ICPC. Да-да, это тот самый Петр Митричев, про которого еще в 2008 ходили легенды на Хабре.

На третьем месте — Борис Минаев, победитель квалификации Google Code Jam в 2013.

Некоторые участники торопились на следующие мероприятия, но большинство успело сфотографироваться на память на крыше JetBrains:

После торжественной части финалисты Kotlin Challenge встретились с Андреем Бреславым, вдохновителем и руководителем проекта Kotlin в JetBrains, задавали вопросы про язык, про планы его развития, предлагали свои идеи.

Отметим, что интерес к языку Kotlin растет в разных областях: его изучают не столько для спортивного программирования, сколько для индустриальной разработки. Например, Kotlin использовался при разработке мессенджера Telegram и веб-сервиса для создания презентаций Prezi.

Для JetBrains Kotlin Challenge — необычный проект, и самый приятный его результат — мы собрали вместе много талантливых людей, которым было интересно решать задачи, и язык, разработанный нами для повышения продуктивности разработчиков в индустрии, отлично подошел и для спортивного программирования.

Посмотрите видеоотчет с финала на нашем сайте, если хотите за 3,5 минуты прожить его вместе с финалистами.

И — обещанный разбор одной из задач финала.

Разбор задачи A: Сокровище

Идея: Анна Малова.
Реализация: Анна Малова.
Разбор: Павел Кротков.

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Условие задачи:
Бен Ганн нашел в пещере сокровища Флинта. Так как Флинт был очень хитрым пиратом, то он поместил его в один из многочисленных сундуков, стоящих в ряд и пронумерованных по порядку от 1 до n. На каждом сундуке есть одна из трех надписей: сокровища лежат в сундуке с большим номером, сокровища лежат в сундуке с меньшим номером, сокровища лежат в этом сундуке. Флинт был еще и безграмотным пиратом, поэтому надписи могут не соответствовать действительности. Бен Ганн быстро отыскал сокровища и решил поместить их в один из сундуков и исправить некоторые надписи так, чтобы все они соответствовали действительности.

Бен Ганн решил выбрать такой сундук, чтобы количество надписей, которые надо исправить, было минимально. Помогите Бену Ганну найти минимальное количество исправлений, которые ему придется сделать.

Формат входных данных:

Входные данные содержат несколько тестовых примеров. Первая строка содержит число T — число тестовых наборов (1 ≤ T ≤ 100). Далее идут тестовые наборы в следующем формате.

Первая строка каждого набора содержит одно натуральное число n — количество сундуков. Вторая строка содержит описание надписей на сундуках. Если i-е число равно -1 или 1, это означает что на сундуке номер i написано, что сокровище лежит в сундуке с номером, меньшем или большем, чем i, соответственно. Если i-е число равно 0, это означает, что на i-м сундуке написано, что сокровище лежит в нем.

Суммарное число всех сундуков в одних входных данных не превосходит 100 000.

Формат выходных данных:

Для каждого тестового набора в порядке появления во входных данных выведите одно число — минимальное число надписей, которое нужно исправить Бену.

Примеры:

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

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

Исходный код описанного решения приведен ниже.

import java.util.Scanner

fun main(args: Array) {
    val input = Scanner(System.`in`)
    val T = input.nextInt()
    for (i in 1..T) {
        val n = input.nextInt()
        val a = IntArray(n + 1)
        var cntL = 0
        var cntR = 0
        for (j in 0..n - 1) {
            a[j] = input.nextInt()
            if (j > 0 && a[j] != -1) cntR++
        }

        var ans = n + 1
        for (j in 0..n - 1) {
            ans = Math.min(ans, cntL + cntR + (if (a[j] == 0) 0 else 1))
            if (a[j] != 1) cntL++
            if (j < n - 1 && a[j + 1] != -1) cntR--
        }

        println(ans)
    }
}

Программируйте со спортивным удовольствием!

Автор: philipto

Источник