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

Вторая командная интернет-олимпиада (neerc.ifmo.ru/school/io/)
Автор agul, 13 лет назад, По-русски

Сегодня прошла вторая олимпиада из цикла интернет-олимпиад, проводимого ИТМО.

Предлагаю после завершения усложненной номинации обсудить здесь задачи (примерно через 20 минут).


P.S. По возможности, кто-нибудь, расскажите решения задач.

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

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

Тренировки ИТМО (neerc.ifmo.ru/trains/
Автор agul, 13 лет назад, По-русски

Здесь обсуждаются задачи тренировок ИТМО (http://neerc.ifmo.ru/trains/).

Тренировки проводятся по средам и субботам, начало в 16:30 (МСК), длительность - 5 часов, формат - ACM.

P.S. Пожалуйста, не обсуждайте до окончания тренировки задачи. Мы за честность :)

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

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

Построение декартового дерева
Автор agul, 13 лет назад, По-русски

Задача: http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=2781#1


Пытался написать что-то свое - WA 9.
Взял код в двух вариантах из теоретической части c этого же ресурса - WA 9 (http://informatics.mccme.ru/moodle/mod/book/view.php?id=444, http://informatics.mccme.ru/moodle/mod/book/view.php?id=423).

Вот сам код:


Можете подсказать, в чем ошибка?

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

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

Декартово дерево
Автор agul, 13 лет назад, По-русски
Задача: http://informatics.mccme.ru/moodle/mod/statements/view.php?id=1974#1

В каких случаях дерево построить невозможно?

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

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

Операторы С++ - нужен совет
Автор agul, 13 лет назад, По-русски
int a[50];

void good(int& m,int x){
for (int i=0; i<x; i++)
       m&=~a[i];
}

Не могу разобраться: что происходит при выполнении этой операции: m&=~a[i];?

Заранее спасибо.

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

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

Задача на RMQ
Автор agul, 13 лет назад, По-русски

Пока некоторые люди страдают от нехватки контестов, я решаю задачки из архивов (:


Сегодня открыл эту задачу: http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=597&chapterid=753#1

Вроде тема курса намекает на то, что ее нужно решать через Range Maximum Query.
Я так и делаю, но что-то не получается.

Кратко опишу свой алгоритм:

1) строим дерево из N элементов (все нули)
2) Каждый запрос, в зависимости от его типа, обрабатываем особым образом:
    2.1) Если запрос первого типа, то вызываем RMQ(L,R). Если результат 0, то ни один элемент этого
           отрезка не входит ни в одну группу - объединяем.
           2.1.1) Что значит объединяем? Всем элементам из данной группы присваиваем одно и то же
                       значение - номер группы (номер группы - счетчик, увеличиваем его с появлением каждой новой группы)
           2.1.2) При каждом изменении значения элемента делаем update данного элемента в дереве.
    2.2) Если запрос второго типа, то проверяем:
           2.2.1) Если значение элемента - 0, то элемент не принадлежит ни одной группе, выводим "0 0"
           2.2.2) Если значение элемента больше 0, то:
                     2.2.2.1) Проходим вправо - ищем правую границу, попутно обнуляя элементы и делая
                                  update дерева. Аналогично ищем левую границу
                     2.2.2.2) Выводим границы

Приветствуются прямые указания на ошибки и хорошие тесты, которые завалят программу.

Заранее спасибо!

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

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

Количество разбиений в суммы слагаемых
Автор agul, 13 лет назад, По-русски

Не знаю, как точно сформулировать вопрос, поэтому постараюсь писать подробно.


Пусть мне дано некоторое множество чисел [A1, A2, A3,  ... , Ak] - множество возможных слагаемых и дано число N, которое нужно разложить в суммы слагаемых (слагаемые являются числами множества).

Например:
N=8
A=[1, 2, 6]

Возможные разбиения:

8=6+2
8=6+1+1
8=2+2+2+2
8=1+1+2+2+2
8=1+1+1+1+2+2
8=1+1+1+1+1+1+2
8=1+1+1+1+1+1+1+1

Ответ в данном случае - 7.

Существует ли какой-то алгоритм подсчета ответа по заданному числу N (предполагается, что множество A дано в условии и постоянно на всех тестах).

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

Заранее спасибо!

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

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

Google Code Jam 2011: Round 1
Автор agul, 13 лет назад, По-русски
На всякий случай напоминаю расписание раундов Google Code Jam.


Продолжительность контеста - 2 часа 30 минут.

К участию допускаются участники, прошедшие квалификацию (набравшие >25 баллов в 24-часовом квалификационном раунде).

В Round 2 проходят первые 1000 участников из каждого раунда. 

  • Если вы прошли отбор в одном из под-раундов, то вы не сможете участвовать в последующих под-раундах.
  • Если вы не прошли отбор в под-раунде, то вы сможете принять участие в следующих под-раундах, если они еще останутся.
Например: вы не прошли отбор в Round 1A, тогда вы еще сможете принять участие в Round 1B и 1C. Если вы пройдете отбор в Round 1B, то уже не сможете принять участие в Round 1C, зато сможете участвовать в Round 2.

Предлагаю после окончания раундов обсудить здесь задачи и решения.

P.S. Во избежание неприятных ситуаций, прошу не обсуждать задачи вплоть до окончания текущего раунда.

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

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

Страница пользователя Codeforces не открывается. Баг?
Автор agul, 13 лет назад, По-русски

Воспользовался новой фишкой рейтинга Codeforces: http://codeforces.com/ratings/country/Russia/city/Novosibirsk

В рейтинге нашел знакомый хэндл - kirill.
Однако, никак не могу открыть страницу - вылетает ошибка:

Упс! Что-то сломалось на Codeforces. Не стоит паниковать. Вы можете попробовать перегрузить страницу или вернуться на главную. Мы уже читаем мегабайты логов, решая проблему.


Что случилось?

UPD: Вроде пофиксили.

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

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

Использование Testlib
Автор agul, 13 лет назад, По-русски
У меня есть своя тестирующая система с открытым исходным кодом. Я немного модифицировал Testlib (переписал создание отчета о тестировании для приведения к формату моей тестирующей системы), добавил комментарий о том, что я добавил изменения, но при этом все копирайты сохранил, стандартный код создания отчета закомментрировал, дописал свой. 

Могу ли я теперь выложить этот исправленный Testlib на Google Code (где лежит код моей тестирующей системы), не нарушая ни чьи права?

P.S. Я исправил testlib.pas и testlib.h. Оба файла изначально были взяты в архиве РОИ-2011. Если я не ошибаюсь, то авторы testlib.pas - ИТМО, testlib.h -  MikeMirzayanov.

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

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

Баг с отображением рейтинга на Codeforces
Автор agul, 13 лет назад, По-русски
Случайно открыл страницу пользователя Petr не в развернутом состоянии окна, а сжатом. Скриншот:

Пока что все ок.

Затем я развернул страницу, и получил странное отображение. Скриншот:

Видно, что само поле графика в размерах не увеличилось и расположение не поменяло, а цифры рейтинга (слева) и легенда графика (с хэндлом Petr) сдвинулись.

Если открыть страницу в развернутом состоянии, а потом свернуть в окно, то получается так:



P.S. Если вдруг важно, то:
ОС - Windows XP
Браузер: Google Chrome 10

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

Теги bug, cf
  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

Помогите придумать алгоритм (задача о делителях)
Автор agul, 13 лет назад, По-русски
Задача J с Huge Easy Contest II на uva.onlinejudge.org (текст задачи в оригинале на английском).

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

Входные данные
В первой строке дается количество тестов T (T ≤ 50000). В следующих T строках записано единственное число N (1 ≤ N ≤ 106), соответствующее данному тесту.

Выходные данные
Каждая из T строк должна содержать единственное число - ответ на задачу Стива.

SAMPLE INPUT
3
1
10
37

SAMPLE OUTPUT
1
10
36

Подскажите, пожалуйста, идею, как решить эту задачу. 

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

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

COCI R7
Автор agul, 13 лет назад, По-русски
Как-то обошли эту тему стороной на Codeforces. 

Предлагаю здесь обсудить решения и результаты. http://www.hsin.hr/coci/

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

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

Очередное предложение по улучшению CF
Автор agul, 13 лет назад, По-русски
Может перенести блок "Прямой эфир" в правой колонке немного выше, а "Лидеров" сместить вниз? Мне кажется, что это было бы намного удобнее, т.к. "Прямой эфир" обновляется часто, поэтому его приходится просматривать чаще, чем другие блоки, а блок "Лидеры" обновляется очень редко.

P.S. Я понимаю, что у некоторых людей есть огромные 24-дюймовые мониторы, на которых, вероятно, скроллить страницу Codeforces в поисках прямого эфира не нужно, но таких людей, имхо, меньшинство.

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

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

Как зарегистрироваться на сервере соревнований SnarkNews?
Автор agul, 13 лет назад, По-русски
Собственно, весь вопрос в заголовке.

Хотел бы зарегистрироваться на сервере соревнований SnarkNews, чтобы что-нибудь порешать, но никак не могу найти ссылку регистрации.

Дайте, пожалуйста, ссылку для регистрации. Заранее спасибо.

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

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

Девятая Интернет-олимпиада на neerc.ifmo.ru/school/
Автор agul, 13 лет назад, По-русски
Сегодня в 16:00 (МСК) началась девятая интернет-олимпиада. После ее окончания предлагаю здесь обсудить решения и прочее.

Ссылка: neerc.ifmo.ru/school/

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

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

ИОИП
Автор agul, 13 лет назад, По-русски
Сегодня прошел очный тур ИОИП. 

После 18:00 (МСК), когда закончится 8 индивидуальная интернет-олимпиада на neerc.ifmo.ru/school/, проводимая по задачам ИОИП, предлагаю обсудить здесь решения и ожидаемые результаты (по правилам ИОИП за первые 5 попыток по задаче выдается количество баллов).

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

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

Баг Codeforces?
Автор agul, 13 лет назад, По-русски
Сегодня уже весь вечер решаю задачки с архива, открыв новую задачу, внезапно получил ошибку 
RPC call for action failed:

Причем такая ошибка вылезает только на нерешенных задачах, т.к. на решенных ранее все ок.
Кто-нибудь знает в чем причина?

UPD: Как отметил StelZ40494, если задачу переключить в английскую версию, то ошибка исчезает.
UPD: Кроме того, задачи можно найти в кэше гугла, где есть и русские тексты условий. Но все же, не сильно круто каждый раз идти в гугл.

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

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

olympiads.ru лежит
Автор agul, 13 лет назад, По-русски
Уже несколько дней при заходе на olympiads.ru выдается ошибка "Google Chrome could not connect to olympiads.ru". Хотел посмотреть полные результаты всероссийской заочной олимпиады.

Кто-нибудь знает причину, почему сайт не работает, и когда он поднимется?
И дайте, пожалуйста, ссылку на полные результаты олимпиады, если они есть где-нибудь кроме olympiads.ru.

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

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