(no subject)

Friday, 20 May 2011 21:33
skiminok: (Default)
В коллекцию эпичных ошибок на контестах:
#define INF 10^9

Слава Богу, не моё :)
skiminok: (Compas)
Итак, к нам приближается:

Google Code Jam


6 мая 23:00 UTC — Qualification
21 мая 01:00 UTC — Online Round 1: Sub-Round A
21 мая 16:00 UTC — Online Round 1: Sub-Round B
22 мая 09:00 UTC — Online Round 1: Sub-Round C
4 июня 14:00 UTC — Online Round 2
11 июня 14:00 UTC — Online Round 3
29 июля — Onsite Finals

TopCoder Open


14 мая 12:00 UTC-4 — Qualification Round 1
19 мая 07:00 UTC-4 — Qualification Round 2
24 мая 21:00 UTC-4 — Qualification Round 3
18 июня 12:00 UTC-4 — Round 1
25 июня 12:00 UTC-4 — Round 2
9 июля 12:00 UTC-4 — Round 3
23 июля 12:00 UTC-4 — Round 4
6 августа 12:00 UTC-4 — Round 5
27 сентября 08:30 UTC-4 — Semifinal 1
27 сентября 12:30 UTC-4 — Semifinal 2
27 сентября 17:30 UTC-4 — Wildcard Round
28 сентября 10:00 UTC-4 — Championship

Russian Code Cup


8 мая 11:00 UTC+4 — 1 квалификационный тур
14 мая 11:00 UTC+4 — 2 квалификационный тур
15 мая 17:00 UTC+4 — 3 квалификационный тур
19 июня 11:00 UTC+4 — Отборочный тур
17 сентября — Финал

Открытый турнир Яндекса


4 мая, 9:00 UTC+4 — 1 квалификационный раунд
6 мая, 19:00 UTC+4 — 2 квалификационный раунд
20 мая, 19:00 UTC+4 — 1 отборочный раунд
22 мая, 19:00 UTC+4 — 2 отборочный раунд
12-18 июля — Финальный раунд

Quite a bit

Friday, 4 February 2011 22:16
skiminok: (Default)
Выдержка из одного эдиториала TC.

We then need to count the number of maximum matchings in this graph, and then we're done. Unfortunately, this is a #P-complete problem, and if we can solve it in polynomial time, we would have proved that P = NP. That would make this problem quite a bit trickier than the usual Division 1 Medium.

Слова, вынесенные в заголовок, отправили меня ржать под стол :D Почти буквально)
skiminok: (Compas)
За последние несколько месяцев у меня набралось несколько планов на статьи, которых сильно не хватает хабра-аудитории. В целом они делятся на три больших класса: ФП, Computer Science и ACM-алгоритмистика.

Это - список, себе на память, чтобы брать из очереди, как время появится.

  • FParsec - "утереть нос" товарищу Дмитрию mezastel Нестеруку :)

  • Списочные гомоморфизмы. Свертка. Сканирующие пробеги. Короче, основы Vector Models for Data-Parallel Computing, и немного про MapReduce с математической стороны вопроса.

  • Структура данных Rope, на основании уже существующего моего цикла про декартово дерево.

  • В рамках той же темы "Основы Computer Science: ликбез для птушников" - λ-исчисление, порядок редукций, теорема Черча-Россера, и как отсюда логически выходят потоки и ленивые вычисления. Ссылки на SICP и ПФП.

  • (?) Что-то про теорему Райса и теоретически вычислимые алгоритмы. Можно и классы сложности упомянуть.

  • Дерево отрезков.

  • (?) Дерево Фенвика.

  • Суффиксный массив, его применения. Возможно - суффиксный автомат и дерево. Уже почти год хочу рассказать, офигенная вещь ведь.


To be continued...
skiminok: (Compas)
Я тут вернулся из Винницы, с финала All-Ukrainian Collegiate Programming Contest.
И там был офигительнейший ролик — фотонарезка с прошедших 9 прошлых финалов (и еще нескольких ивентов украинского мира спортивного программирования).

Если кому-нибудь когда-то было интересно, чем мы действительно занимаемся, когда ездим на эти олимпиады, и почему же там так классно — посмотрите этот ролик :) Только полностью.

Спасибо ребятам из ВНТУ за его создание.

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

skiminok: (Compas)
На мотив "Потерянный рай".

От края до края люди контест лажают
И вот исчезают все надежды на финал.
Ты тоже лажаешь, задачу ты посылаешь
И вновь получаешь Presentation on test 2.

Не лажай, не лажай, программер, не лажай,
Подебужь, а сабмит подождет,
Ты потесть и конкретную багу поймай,
и тогда задача пройдет.

Там хитрый Станкевич гробов может дать штук 9,
Их вашей команде ни за что не порешать.
Бояться не надо, дух тренера будет рядом
и хитрые баги он поможет отыскать.

Не лажай, не лажай, программер, не лажай,
Подебужь, а сабмит подождет,
Ты потесть и конкретную багу поймай,
и тогда задача пройдет.

И вот ты в финале, все счастье в воздушном шаре,
5 лет тренировок перед тобою промелькнут.
Там был Билли Пучер, китайцы и ты их вздрючил,
За эти старанья тебе кубок принесут.

Не лажай, не лажай, программер, не лажай,
Подебужь, а сабмит подождет,
Ты потесть и конкретную багу поймай,
и тогда задача пройдет.

via СГУ

skiminok: (xkcd)
Тут сегодня некто решил перевести на Хабре скучный пост с перечислением фич нового контейнера SortedSet<T> из .NET 4.0. Увидел я его только к вечеру, поскольку весь день мотался по городу. Пролистнул, ничего особенного вроде не обнаружил (в конце концов, что я не знаю про их дерево и его внешний интерфейс?), хотел было уже закрывать, как тут глаз зацепился за название метода GetViewBetween.

Видимо, когда я сразу после выхода .NET 4 просматривал спеки MSDN, я его как-то картинно и красиво прое не заметил. Полез в документацию. Совершенно не в стиле MSDN: капитанское описание цели метода (спасибо, я это и так уже знаю!), пример кода и ни слова о сложности алгоритма. Ладно, будем действовать самостоятельно.

Ценная строчка в документации указала, что класс хранится в сборке System.dll. Лезем в папку с фреймворком, открываем сборку Рефлектором, прокручиваем до нужного класса и нужного метода. Далее - серия code snippet`ов: как я в поисках истинной реализации прыгал от метода к методу:

public virtual SortedSet<T> GetViewBetween(T lowerValue, T upperValue)
{
    if (this.Comparer.Compare(lowerValue, upperValue) > 0)
    {
        throw new ArgumentException("lowerBound is greater than upperBound");
    }
    return new TreeSubSet<T>((SortedSet<T>) this, lowerValue, upperValue, true, true);
}


public TreeSubSet(SortedSet<T> Underlying, T Min, T Max, bool lowerBoundActive, bool upperBoundActive) : base(Underlying.Comparer)
{
    this.underlying = Underlying;
    this.min = Min;
    this.max = Max;
    this.lBoundActive = lowerBoundActive;
    this.uBoundActive = upperBoundActive;
    base.root = this.underlying.FindRange(this.min, this.max, this.lBoundActive, this.uBoundActive);
    base.count = 0;
    base.version = -1;
    this.VersionCheckImpl();
}


internal Node<T> FindRange(T from, T to, bool lowerBoundActive, bool upperBoundActive)
{
    Node<T> root = this.root;
    while (root != null)
    {
        if (lowerBoundActive && (this.comparer.Compare(from, root.Item) > 0))
        {
            root = root.Right;
        }
        else
        {
            if (upperBoundActive && (this.comparer.Compare(to, root.Item) < 0))
            {
                root = root.Left;
                continue;
            }
            return root;
        }
    }
    return null;
}
 


Все, приехали. Очевидный проход по дереву за O(H). Поскольку дерево у них там внутри сбалансированное (красно-черное, если конкретнее) - за O(log N).

Подводя итоги: неужели я таки дожил до этого священного дня, когда в стандартной библиотеке .NET появился lower_bound на set`ах? Учитывая, что BigInteger там тоже уже имеется, остается только пожелать для полного счастья next_permutation. Ну и какой-нибудь там nth_element на закуску.

Только вот ведь блин, нет этого .NET 4 нигде. Ни на одном контесте :(
skiminok: (xkcd)
Этот блогпост-конспект лично для меня, как памятка. Все дело в том, что листок, на котором я записывал севастопольскую лекцию, пришел в негодность, а откапывать в случае чего видео каждый раз впадлу. У e-maxx`a жуткий кошмар с кучей кода, совсем не похожий на ту простую красоту, которую рассказывал Лопатин (хотя по сути то же самое).

Сумма на отрезке массива [1; X]:
for (int i = X; i > 0; i -= i & -i)
    S += A[i];


Обновление в точке A[X] += V:
for (int i = X; i <= N; i += i & -i)
    A[i] += V;


f(i) = i & -i — максимальная степень двойки, на которую делится i.
A[i] хранит частичную сумму на отрезке (i - f(i); i]. Нумерация 1-based.
skiminok: (Default)
А я тут продолжаю отортовывать Хабр и выносить помаленьку мозг всем его читателям :)
Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней.
skiminok: (Default)
Немного впечатлений о Севастопольской ЛКШ.

В первую очередь хочу сказать спасибо команде организаторов. Учитывая, что вузом-оргом является Севастопольский Национальный университет ядерной энергии и промышленности - то есть совершенно непрофильный для программирования вуз, если сравнивать с Харьковскими школами, русскими ЛКШ, и пр. - то это достижение. Была кучка организационных фейлов, я о них расскажу. Но, учитывая, что мероприятие проводилось впервые, то на многое можно закрыть глаза.

Начнем с организационных минусов.
Номер первый - общага. Это просто вынос мозга. Когда ты подымаешь матрац, и перед твоим носом десяток тараканов разбегаются во все щели, экологические проблемы и глобальное потепление кажутся какими-то далекими и незначительными. Где-то на пятый день школы тараканов стало значительно меньше, они почти не появлялись (если верить местному "завхозу" Сергею Дмитриевичу, то наконец-то подействовала отрава, которую наложили специалисты перед заездом), однако к последним дням ребятки осмелели, выздоровели, и стали вылазить на свет Божий по новой. Парочку образцов местной фауны я поневоле привез с собой :)
Горячей воды - нет. Кухни - нет. Населена роботами.
В душе три душевые. Не в смысле три кабинки, а просто три лейки в одной общей комнате без каких-либо перегородок между ними. Замка на двери в душ нет. Было обидно, что у участников и участниц разные корпуса общаг.

Объект университета режимный. Там рядом какой-то реактор, я так и не понял: то ли он действующий, то ли недействующий, то ли вообще учебная модель для студентов, но колючей проволокой он огражден по периметру в любом случае. На территорию университета вход через КПП по пропускам с некоторыми дебильными правилами. Например, нельзя ходить в шортах (#define шорты "форма одежды со штанинами выше коленей"). А в бриджах - можно (#define бриджы "форма одежды со штанинами ниже коленей"). Слава Богу, через день-два после начала школы сверху спустили указ "олимпийцам можно ходить через КПП хоть в трусах", но до того солдатики, заворачивающие ребят в шортах, топающих на завтрак, выглядели забавно. Зато так до конца школы и не позволили сидеть в помещении без футболки. А это, учитывая температуру, было бы более чем насущно.

Кстати, насчет температуры. Если с +42 в тени мы поделать ничего не в силах, то надо хотя бы какие-то находить компромиссы. Контест начинался в 10:00 и длился 4 часа, к исходу последнего часа в читальном зале библиотеки было уже ощутимо жарковато и соображать становилось туго. На разборе и добивании сидеть вообще было нереально, мозг просто-напросто плавился и не воспринимал тупейшие алгоритмы. Либо выдавать всем карманные вентиляторы :), либо что-то придумывать с охлаждением, либо менять место проведения ивентов.
Зато за ежедневные вечерние поездки на море все перипетии с жарой прощались природе и организаторам мгновенно :)

Ах да, еще насчет столовой. На пищу особых нареканий нет: не ресторан, конечно, и не харьковские деликатесы из "дорогого" варианта, но тем не менее злого слова сказать нельзя. Зато в столовой было совершенно невозможно находиться, жара там перевешивала все возможные нормы. В итоге любой прием пищи проходил 10 минут: быстро вкинуть в себя максимум из того, что на столе и бежать скорей из этого кошмара на воздух!

Технические замечания. Интернет. Пожалуйста, дайте Интернет! Я понимаю, что это режимный объект, и что сложно вдолбить в голову местным спецам по безопасности, что свободный доступ к вайфаю для незарегистрированных лиц - это не провал всех устоев и не ад на земле. Но хотя бы до следующего лета какую-то психологическую работу стоит провести, должно сработать. Зато если будет Интернет и онлайн-доступ к серверу через сайт, можно будет дорешивать круглосуточно, прохладными вечерами в своих комнатах с ноутов, а не в душной атмосфере читального зала в разгар дневной жары.

По лекциям. Вот за собственно наполнение контентом, за контесты, за непосредственно школу хочется сказать огромное спасибо.
В первую очередь Андрею Лопатину за дерево Фенвика и декартово дерево - хотя с контестом он, конечно, схалявил, взяв готовый бурундуковский - но тем не менее простой и красивый контест :) И, конечно же, за потрясающий ивент по отладке (который, сволочи, не записали на видео!!)
Во вторую Аджею Сомани за интересную лекцию - хотя акцент у него, конечно, кошмарный, разбирать это слитное индийское "инконстянтайм" было тем еще квестом.
В третью Диме Кордубану за самый интересный и разнообразный контест из всех контестов школы.
В четвертую Михаилу Медведеву за задачу о сигаретах и долгах. За лекцию говорить особо нечего (ничего нового), за контест стоит отметить только две любопытные задачи на поток.
У Виталия Неспирного был самый гробовой контест всей школы - максимум 3 решенных задачи. Впрочем, это неудивительно, можно сказать, традиция - ведь половину задач готовил Лунёв :)
Ну и традиционно Темури Заркуа, без него не обходится хоть сколько-нибудь значительное олимпийское меропритие. Ему не повезло, конечно, с контестом и неприятным инцидентом с электропроводкой, однако его вины здесь нет, конечно.

Спасибо еще раз всем. Крайне жаль, что писать все контесты мне приходилось в одиночку: мои тиммейты оказались крайне тяжелыми на подъем. Надеюсь, следующим летом это положение изменится.
skiminok: (Default)
Я вернулся с Севастопольской ЛКШ. Скажу пока только, что там было офигенно, полный отчет сейчас делать нет сил.

Нет сил потому что по свежим впечатлениям после ЛКШ (мне напомнили про одну лекцию полугодичной давности) я накатал большой и красивый пост на Хабрахабр про декартовы деревья. Простая, красивая, производительная и очень мощная структура данных. Поскольку материала, про который можно еще рассказывать по теме, чуть менее чем дофига, будет еще как минимум два таких поста.

Надеюсь, всем будет интересно почитать ;)
skiminok: (!int)
Нет, ну по сравнению с предыдущим годом это все-таки прогресс - но какой-то не впечатляющий.

Для начала, писать мне его пришлось в крайне непривычных условиях: не дома, а в КПИшной общаге. В принципе, работать там было вполне возможно, при условии толстых наушников (а их я ношу с собой постоянно =)). Студия есть, интернет есть, бумажка в клеточку с ручкой есть - что еще нужно человеку для счастья? Мозги, как выяснилось.

В общем, смолл-тесты на B и С делались очевидно. Что я и написал быстренько за первый час (пытаясь, в случае В, построить код так, чтобы при наличии гениальной идеи на лардж-тест исходник легко переделывался). Как оказалось, на этом все и закончилось. На А я забил, прочитав условие, формат ввода и строчки типа "15 wrong tries" в мониторе, а смолл-тест D написал, потеребил некоторое время на предмет багов и понял, что зря теряю время, геометр из меня все равно хреновый, а 7 баллов погоды не сделают.

Дальше могла бы следовать success story - но увы. Вообще обидно: идея динамики В была совсем прямой и лобовой, не знаю, что меня переклинило не выписать ее аккуратно на листочек.
Правда, с таким поздним сабмитом штрафное время все равно не дало бы мне вырваться в топ-500. А С-шка могла бы дать. Но там уже требовались какие-то аналитические способности представить, каким образом скукоживаются в точку разноформенные группы бактерий. Красиво, на самом-то деле.

В общем, до GCJ 2011. Понтовая футболочка подождет еще годик.
skiminok: (Default)

open System

open System.IO

 

do

    use reader = new StreamReader("B.in")

    use writer = new StreamWriter("B.out")

    let readLine _ = reader.ReadLine()

 

    let testCount = reader.ReadLine() |> int

    let split (s: String) = s.Split(' ') |> List.ofArray

    let gcd a b = bigint.GreatestCommonDivisor(a, b)

 

    let solve (y::_ as moments) =

        Seq.pairwise moments

        |> Seq.map (fun (x,y) -> abs(y-x))

        |> Seq.reduce gcd

        |> fun g -> (g - (y % g)) % g

 

    List.init testCount

        (readLine >> split >> List.map bigint.Parse >> List.tail >> List.sort >> List.rev)

    |> List.map solve       

    |> List.iteri (fun i ans -> writer.WriteLine("Case #{0}: {1}", i+1, ans))

skiminok: (xkcd)
Простенькая задача А отлично ложится на F#. Как-то так.

open System

open System.IO

 

do

    use reader = new StreamReader("A.in")

    use writer = new StreamWriter("A.out")

    let readLine _ = reader.ReadLine()

 

    let testCount = reader.ReadLine() |> int

    let split (s: String) = s.Split(' ') |> fun arr -> int arr.[0], int arr.[1]

 

    List.init testCount (readLine >> split)

    |> List.map (fun (N, K) -> (K+1) % (1 <<< N) = 0)

    |> List.map (fun b -> if b then "ON" else "OFF")

    |> List.iteri (fun i s -> writer.WriteLine("Case #{0}: {1}", i+1, s))



А С-шку сдавал на C#, она не так красиво выглядит в итоге.

using System.Linq;

using System.IO;

 

namespace CodeJamCs

{

    class Program

    {

        static void Main(string[] args)

        {

            using (var reader = new StreamReader("C.in"))

            using (var writer = new StreamWriter("C.out"))

            {

                int testCount = int.Parse(reader.ReadLine());

                for (int test = 0; test < testCount; ++test)

                {

                    var line = reader.ReadLine().Split(' ').Select(int.Parse).ToArray();

                    int r = line[0], k = line[1], n = line[2];

                    var size = reader.ReadLine().Split(' ').Select(long.Parse).ToArray();

                    var shift = new int[n];

                    var cost = new long[n];

 

                    for (int sh = 0; sh < n; ++sh)

                    {

                        long sum = 0;

                        int i, cnt;

                        for (i = (n - sh) % n, cnt = 0; cnt < n && sum <= k; i = (i + 1) % n, ++cnt)

                            sum += size[i];

                        i = (i + n - 1) % n;

                        if (sum > k)

                            sum -= size[i];

                        shift[sh] = (n - i) % n;

                        cost[sh] = sum;

                    }

 

                    long totalCost = 0;

                    for (int i = 0, curShift = 0; i < r; ++i, curShift = shift[curShift])

                        totalCost += cost[curShift];

 

                    writer.WriteLine("Case #{0}: {1}", test + 1, totalCost);

                }

            }

        }

    }

}

 

skiminok: (Compas)
Все-таки есть в жизни справедливость.
После х-надцатого коллективного возмущения сишарперов на форум TopCoder вылез добрый админ и пообещал удариться птицей оземь, но за несколько недель таки организовать на сервере свежий .NET. Как минимум 3.5, а там, глядишь, и на 4.0 уломают.
Спасибо тебе, мил человек. Здрав буди.

Profile

skiminok: (Default)
skiminok

Most Popular Tags

July 2011

S M T W T F S
     12
3456789
10111213141516
17181920212223
242526272829 30
31      

Syndicate

RSS Atom