Ми провели 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.
 
Формат вихідних даних:
 
Для кожного тестового набору в порядку появи у вхідних даних виведіть одне число — мінімальне число написів, яке слід виправити Бену.
 
Приклади:
 
                          
Вхідні дані
 
Вихідні дані
 
2 4
5 0
-1 -1 0 1 1
5
1 1 0 -1 -1
 
Переберемо номер скрині, в який ми покладемо скарб. Для того, щоб порахувати кількість написів, які нам доведеться змінити, поклавши скарб у цей скриню, нам необхідно знати кількість чисел, що не рівних одному, зліва від цієї скрині, і кількість чисел, що не рівних мінус одному, праворуч від цієї скрині. Шуканим значенням буде сума двох названих вище значень, до якої необхідно додати одиницю у випадку, якщо на тій скрині написаний не нуль.
 
Обмеження на вхідні дані в задачі не дають нам можливості кожного разу вважати шукані значення, тому що це може зажадати порядку 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)
    }
}

 
 Програмуйте зі спортивним задоволенням!
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.