Russian Code Cup 2012: Разбор задач третьего квалификационного раунда

[BlessMaster]

Из описания задачи про шоколадку:

Ограничение по памяти 256 мегабайт

Интересно, из каких соображений, из расчёта на какие языки выставлен подобный лимит? Не, я конечно понимаю, что это реалии завтрашнего дня, но навевает очень грустные мысли и воспоминания о тех временах, когда винчестер на 200 Мб был пределом мечтаний.

В какую же пропасть мы движемся?

[raliev]

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

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

[eventviewer]

В далекие 97-98 участвовал в ACM, и у них было еще ограничение на размер стека.
Оно было не искуственно, а скорее техническое, использовались C/Pascal для MS-DOS, там было 64K. В некоторых задачах это мешало.

[Anexroid]

Здесь тоже есть такое ограничение. Достаточно глянуть ключи компиляции.

А вообще, это стандартная практика для олимпиад, про ограничение. Просто, например, на школьных олимпиадах, ограничение обычно 64мб. И лично встречал задачу (на областной олимпиаде в 10-м классе), когда оно было критично, ибо задача «в лоб» не решалась, а приходилось придумывать хитрую структуру данных.

[MIXALbI4]

В задаче про очередь, в строке начало 3-го часа в столбец вариант 2, почему вы прибавляете 5х1, ведь, как я понял, человек с раздрожителеностью 5 пришел и сразу же ушел.

[raliev]

Спасибо за внимательность, отпечатка, поправил)

[socro]

Про часы.

Я прошу прощения, но решение, приведенное в посте, очень неоптимально.

Как мне показалось, вы перебираете 3600 вариантов положения стрелок, проверяя каждое на корректность.

Вот так намного проще:

for ( int mins = 0; mins < 720; mins++ ) {
   int m = mins%60;
   int h = mins/12;
}

Положение стрелок при этом подходе _всегда_ будет корректно. Осталось лишь проверить входит текущее положение в открытый сектор, или нет.

Кстати, совершенно не нужны массивы. Если хотите, могу запостить сюда лаконичное решение. Спасибо.

[socro]

И еще там один товарищ решил ПЯТЬ задач за 20 минут. Причем решил верно. Забанили ли вы его за явный читинг, или нет?

[socro]

Сорри, посмотрел результаты — 5 задач за 32 минуты (про 20 минут написал со слов друга).

[xXxVano]

это был Короткевич… интересно будет когда его на ACM пустят :)

[raliev]

Нет, он их честно решил. Это один из сильнейших программистов, мы его знаем (как и многих других сильных ребят), а поскольку у нас wild cards нет, они все проходят квалификации, на простых задачах (для них простых). На первые, более сложные, он, видимо, не смог прийти, ну а на третьей решил просто быстро)

[socro]

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

Ну да ладно. Скорее всего, просто я тупой.

[raliev]

У них «работа такая». Как собрать кубик-рубик за 6,24 секунд мне тоже непонятно, хотя я в общих чертах знаю методику сборки. Здесь так же: определяется класс алгоритмов, решающие задачу, чем конкретная задача меняет классический алгоритм, а дальше кодинг алгоритма по памяти или нет.

[Beo]

Не, тут вы не правы.

Я сам достаточно плохо выступил (я работаю в Mail.Ru, потому не выделял время под раунд, пропустил час и потом ещё отходил в процессе), но:

первую задачу сделал минуты за 3
вторую примерно за 4 минуты, там код примерно такой:

#!/usr/bin/perl -l
<>;
while(<>) {
    my ($m, $x1, $y1, $x2, $y2) = split ' ', $_;
    if(abs($x1-$x2) + abs($y1-$y2) <= $m) {
        print "First 1";
    }
    else {
        print "Infinity";
    }
}

третью за 10 (потом ещё 15 ловил баги, но спортсмены таких багов не делают)

И четвёртую минут 15 колупал, но не успел уже отправить.

Итого, если бы шёл идеально, сделал бы за 35 минут четыре задачи.

А я не спортивный программист :) Первые 3 задачи были очень уж просты.