Блог пользователя caustique

LiveArchive - задачи финала
Автор caustique, 14 лет назад, По-русски

На http://livearchive.onlinejudge.org/ уже появились задачи финала.

Попробовал засабмитить одну на Java - получил Runtime Error.
Вопрос: в какой поток выводить результат? Стандартный? Вроде так и делал. Если в файл, то с каким именем?
Где можно почитать справку про этот сайт?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

Блог Скиданова Алекса
Автор caustique, 14 лет назад, По-русски

Я люблю CodeForces не только за то, что тут можно порешать интересные контесты, но и потому, что есть возможность читать блоги.
К сожалению, большинство блогов унылы чуть более, чем полностью. Исключение составляют разборы задач и отчеты с поездок, а также почти все посты SkidanovAlex.
Недавно в посте RodionGork всплыло обсуждение того, кем работают олимпиадные программисты. Такие обсуждения были и раньше. Было бы интересно послушать рассказы тех, кому действительно есть что рассказать. В одном из комментов SkidanovAlex писал, что ушел из MicroSoft ради работы в стартапе. Я почитал также про это в его блоге (кстати, всем рекомендую) и, думаю, сообществу CodeForces также интересно было бы узнать эту историю. Ведь он уже писал об "истории одной браузерки", о своем путешествии в Лас-Вегас, а также смысле жизни после ICPC.
Так вот было бы здорово послушать о специфике работы в MicroSoft и стартапе, а также почитать советы начинающим, как стать таким крутым.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +44
  • Проголосовать: не нравится

STL lower_bound()
Автор caustique, 14 лет назад, По-русски
Получил в задаче B 66 CFBR Time Limit на 9 тесте.
Сразу скажу, что у меня, возможно, не самое оптимальное решение, потому что я юзаю multiset <int> и прочие стандартные контейнеры, например vector <pair <int, string> >, хотя если убрать последний, ничего не меняется.

В дорешке переделал считывание и все сократил по минимуму - не помогло.

Посмотрел решения других участников и обнаружил у hos.lyric такое же решение, как у меня, за исключением того, что он использовал container.lower_bound(value), а я lower_bound(contaner.begin(), container.end(), value).

Его решение работает на 9 тесте 0.7 с., а мое не влезает в 4.
После переделки, решение заработало на том же тесте за 0.25 с.

Я в шоке.
Всегда думал, что эти стандартные алгоритмы эквивалентны.
Оказывается, нет?
Кто какие еще подводные камни знает в STL?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

Динамика на дереве
Автор caustique, 14 лет назад, По-русски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

Разбор задач A, B, C, D CodeForces Beta Round #42
Автор caustique, 14 лет назад, По-русски

А. Футбол.


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

B. Письмо.


Известно, что символы из таблицы ASCII, к которым относятся все (строчные и заглавные) латинские буквы и пробел, имеют коды от 0 до 127. Значит, достаточно завести два массива на 128 символов (можно узнать требуемую память точнее, но char занимает 1 (или 2 байта в Java), поэтому это непринципиально), инициализированных нулями, и заполнить каждый из них следующим образом: идем циклом по строке, получаем код текущего символа строки, элемент массива с таким индексом (кодом символа) увеличиваем на единицу. Таким образом получим два массива - один для первой строки и один для второй. Чтобы составить вторую строку, нужно, чтобы выполнялось условие b[i] <= a[i] для всех i от 0 до 127, кроме (char)i == ' '. Пробелы вырезать ненужно, поэтому для них неравенство может не выполняться.

С. Счастливые билеты.


Признак делимости на три говорит нам, что натуральное число делится на три тогда и только тогда, когда сумма его цифр делится на 3. Для каждого кусочка билетика мы можем посчитать остатки от деления этого числа на 3 - 0, 1 или 2. Обозначим количество билетов первого типа - a, второго типа -  b, третьего - с. Счастливые билетики можно составить двумя способами: либо соединить кусочки с остатками от деления 0 и 0, либо - 1 и 2. Тогда сумма чисел на получившемся билетике будет 3, что и требуется. Ответом будет число a / 2 + min(b, c). Оставшиеся a % 2 + max(a, b) - min(a, b) билетиков придется выкинуть, так как для них нет соответствующей пары.

D. Путешествие


Сперва заметим, что в оптимальном решении может быть не более одного телепорта. Таблицу n * m можно обойти несколькими способами, перемещаясь только по соседним клеткам - например, змейкой или спиралью. Далее, из последней клетки, в которую мы пришли при обходе таблицы, можно телепортироваться в первую.
В этой задаче нужно было рассмотреть 4 случая:
1. n * m = 2 - тогда ответ легко выписать вручную
2. n = 1, m > 2; n > 2, m = 1 - идем по полоске до конца, а из последней клетки ((1, m) или (n, 1)) телепортируемся в первую
3. оба n и m нечетные (ни одно из чисел не равно 1) - тогда нужна одна телепортация: обходим доску одним из предложенных способов: змейкой (вверх-вниз или вправо-влево) или по спирали - а из последней клетки телепортируемся
4. хотя бы одно из чисел четное, а другое не равно единице - тогда идем вдоль четной стороны до края таблицы, а оставшуюся часть обходим змейкой + делаем один завершающий ход.
Для пояснения пункта 4, рассмотрим пример.
Пусть n - четное, m - нечетное (не равное 1). Тогда идем вдоль края таблицы из клетки (1, 1) в клетку (n, 1). Дальше возвращаемся в клетку (1, 2) следующим образом: если текущая строка i четная - идем вправо от 2 до m, иначе идем влево от m до 2. Заметим, что последней строкой, которую мы так пройдем, будет первая (по номеру), то есть мы действительно закончим в клетке (1, 2). Осталось сделать только заключительный ход в (1, 1).

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 42 (Div. 2)
  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

Вопрос по С++. Макросы
Автор caustique, 14 лет назад, По-русски
Зачем в определении макросов опытные участники пишут #define all(v) (v).begin(), (v).end(), обрамляя название контейнера в дополнительные скобки? То же самое с переменной в цикле for: #define REP(i,n) for (int (i)=0; (i)<n; (i)++)
В каких случаях это может помочь?

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

When not competing on TopCoder, what kind of applications do you work on?
Автор caustique, 15 лет назад, По-русски
http://forums.topcoder.com/?module=Thread&threadID=677778&start=0&mc

В форумах ТопКодера я нашел интересную ветку.

Вопрос сформулирован там так: When not competing on TopCoder, what kind of applications do you work on?

Применительно к CodeForces, можно спросить:

Над какими проектами вы работаете, когда не занимаетесь олимпиадным программированием?

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Отладка в MSVS 10
Автор caustique, 15 лет назад, По-русски
При отладке с заходом в функции (F11) отладчик заходит не только в мои функции, но и в ассемблерные и библиотечные файлы, что мне совсем не нужно.
Как отключить эту опцию?

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Tutorials
Автор caustique, 15 лет назад, По-русски
На сайте уже обсуждались темы по поводу базы алгоритмов.

А как насчёт создать базу ссылок на полезные туториалы, руководства, мануалы, связанные или НЕсвязанные с олимпиадным программированием?

Я предлагаю для начала список из трех ссылок на языковые туториалы. Было бы интересно узнать ссылки на руководства по технологиям программирования, а не только языкам.



Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится