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

Автор I_love_natalia, 12 лет назад, По-русски
class A
{
public:
  virtual std::string name() = 0;
};
class C
{
public:
  C(A* p)
  {
    std::cout << p->name() << std::endl;
  }
};
class B: public A
{
public:
  B(): A(), m_obj(this)
  {
     
  }
  virtual std::string name()
  {
     return "Hello, world!";
  }
  C m_obj;
};

Кратко: одно из полей класса в конструкторе по указателю на предка сделало вызов виртуальной функции.

Вопрос: будет работать правильно или все-таки undefined behavior? Т.е. гарантируется ли, что первым делом конструктор инициализирует vtbl?

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

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

Автор I_love_natalia, 12 лет назад, По-русски
  • Проголосовать: нравится
  • -19
  • Проголосовать: не нравится

Автор I_love_natalia, 12 лет назад, По-русски

Upd. похоже, что придумалось решение.

====== Задача такая:

Пусть задан некоторый алфавит A и алфавит B. Будем считать, что все символы алфавита A появляются равновероятно. Каждый символ алфавита B имеет некоторый вес — вещественное число, характеризующее сложность его передачи. Необходимо построить префиксный код, кодирующий символ алфавита A словом над алфавитом B, минимизирующий средний вес получающегося слова над алфавитом B.

Техническое замечание: алфавит A как можно больше (меньше 224 — странно), алфавит B порядка 220, причем в нем примерно 5 различных весов 4 различных веса передачи. Радовать будет просто хорошее решение.

Источник: жизнь (необходимо записать бинарные данные в Unicode так, чтобы UTF-16 и UTF-8 представления были не очень длинными).

Примерные данные алфавита B:

Количество символовw1w2Описание, кому интересно
27 - 2511Однобайтовые UTF-8 символы, кроме "плохих" первых 32
211 - 2721Двухбайтовые UTF-8 символы
216 - 211 - 211 - 231Трехбайтовые UTF-8 символы, кроме "плохих" последних двух и суррогатов:
Неверный BOM U+FFFE и символ U+FFFF запрещены в Unicode.
U+D800..U+DFFF — диапазон суррогатных пар для UTF-16, запрещен в Unicode.
22042Старшая часть Unicode, которая кодируется суррогатной парой в UTF-16

Итоговый вес — это, например, 0.45w1 + 0.55w2

Upd. в итоге получилось построить перекодировку бинарных данных в Unicode со средней избыточностью ~30% для UTF-8 и ~20% для UTF-16 представлений (~40% и ~35% худшие случай, соответственно) кодированием 12-байтовых последовательностей. Для UTF-8 это практически неулучшаемо из-за собственной избыточности UTF-8, для UTF-16 низкая избыточность ведет к высокой избыточности представления в UTF-8. Вероятно, что для более длинных последовательностей можно улучшить результат UTF-16 при том же значении UTF-8, но избежать вычислений в длинной арифметике будет крайне проблематично.

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

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

Автор I_love_natalia, 12 лет назад, По-русски

За пределами Самары мало кто знает, что в Самаре 18 марта прошло межвузовское первенство по спортивному программированию. Это одно из двух первенств, проводимых ежегодно в Самаре.

В общем, все желающие потренироваться, кто не был на этой олимпиаде, могут принять участие в соответствующей тренировке на Codeforces. Тренировка будет по правилам ACM, задачи будут на русском языке и, почти наверное, на английском языке.

Задания были подготовлены Алексеем Дергуновым (dalex), Никитой Глащенко (Hohol), Павлом Семушиным (craus) и Андреем Гайделем (Shlakoblock). Тестировали комплект я (I_love_natalia) и Наталья Бондаренко (natalia).

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

Пройдет тренировка 24 марта в 16:00 по московскому времени, участвовать приглашаем всех желающих.

Просим при участии не использовать prewritten код и вообще материалы в интернете в знак уважения к призракам участников олимпиады, которые будут участвовать с вами ;)

Upd. Время поменяли на 16:00.

Upd2. Для ввода-вывода используйте файлы input.txt и output.txt!

Upd3. Не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

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

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

Автор I_love_natalia, 12 лет назад, По-русски

Обсуждая будущее группы, созданной с известными целями, мы обнаружили, что у проекта совсем нет более или менее развитой собственной группы ВКонтакте. Нам показалось это странным, так что мы решили просто переименовать группу и изменить ее цели и задачи.

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

Вступаем, разводим дискуссию, пишем сообщения "а зачем это надо?", в общем, кнопка "написать комментарий" в этой теме доступна, как и всегда.

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

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

Автор I_love_natalia, 12 лет назад, По-русски

Недавно я узнал, что на Codeforces можно использовать prewritten code, в случае, если этот код написан тобой.

Хотелось бы задать вопрос Максиму Иванову (e-maxx) на каких условиях публикуются исходные коды на всеми нами любимом сайте e-maxx.ru, в том числе, могу ли я переформатировать его под предпочитаемый мною стиль и считать своим.

P. S.

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

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

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

Автор I_love_natalia, 12 лет назад, По-русски

Сейчас, наверное, администрация в поте лица ищет ошибку в скрипте пересчета голосов. Вместе с тем, создается момент поискать забавные результаты голосования (пока они еще не пересчитаны). Предлагаю размещать их здесь.

Вот мои замечательные примеры.
http://codeforces.com/blog/entry/3308#comment-66213 - призыв к администрации о соблюдении правил законодательства РФ. -32.
http://codeforces.com/blog/entry/3085#comment-62434 - очень старый анекдот. +121. Самый "лучший" мой пост на текущий момент.

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

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

Автор I_love_natalia, 12 лет назад, По-русски

Ответ на стихотворения от имени исходного кода.

Написан я был темной ночкой,
Samsung рыдает по мне,
Болею я лишней строчкой,
Костыль на каждой ноге.

Отправлен я на проверку
(Мой автор оранжевый. Был...)
На F, в которой снежинку
Кто-то кому-то дарил.

Мечтаю, что будет прозренье,
Откроет меня программист
И со слезой умиленья
Допишет последний bugfix.

Не будет мой друг-компилятор
Смеяться тогда надо мной,
Найдет что любой генератор
Ошибку в цифре одной...

Так... все разговоры - на полку!
Попал под проверочный пресс.
Сейчас, подождите немного,
Решу 19ый тест...

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

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

Автор I_love_natalia, 12 лет назад, По-русски

Извините за очередную оффтопную тему, но я принципиально не понимаю действия администрации.

> Контент, не соответствующий ожидаемому уровню общения будет удаляться и впредь.
ЧТО ОНИ ХОТЯТ? Чтобы Codeforces превратился в эдакое собрание бородатых профессоров, которые ведут чинно ведут дискуссию о том, почему у фиолетового участника не сдается задача? Или в место, где любой школьник может попросить решить за него домашнее задание?

Давайте посмотрим на статистику, предложенную здесь. Например, на количество комментариев по отношению к количеству постов. Среднее количество комментариев на пост Codeforces в 2010 году составляло чуть менее, чем 17. В 2011 году порядка 22. Отбросим комментарии, которые сделаны в обсуждениях раундов CodeForces и других ресурсов и так называемые "офтопные темы". Что останется? Примерно 10 комментариев в среднем на 85% постов. Это вы называете сообществом? Этого вы хотите? Чтобы на Codeforces заходили поиграть соревнования и порешать задачи? Есть 20 других ресурсов, на которых можно сделать то или другое. Интересно, администрация пыталась задуматься, какую роль в развитии проекта сыграло сообщество?

Говорят, что последние события вызвали "вызывает внутренний протест как у меня лично, так и у многих членов сообщества". За последние два дня я не видел ни одного раздраженного комментария, а в событиях с явным интересом участвовали не менее 20 человек. Стоит ли говорить, что подобную смену ников провел 1 человек из топа рейтинга и 3 человека из топа вклада, а еще два человека из топа вклада по разным причинам не могли быть в них вовлечены? По вкладу я предлагаю поделить и заметить забавную цифру 37,5%. Здесь очень хочется вспомнить некоторые слова Alex_KPR по вопросу, почему он ничего два месяца не писал. Но я не буду их приводить, сказано в личной переписке, все что как.

Позицию пользователя RodionGork, который предлагает, подходя к человеку, предъявить перед разговором с ним ему паспорт, я знаю. Он может считать, что правила этого поста запрещают ему его комментировать.

P. S. Верните мне назад ник. Я не просил ставить назад anonymous.

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

Теги i, am, angry
  • Проголосовать: нравится
  • +66
  • Проголосовать: не нравится

Автор I_love_natalia, 12 лет назад, По-русски

Мне интересно мнение участников CF, в особенности тех, у которых оно есть.

Опрос дня такой. Верите ли вы, что хотя бы половина засчитанных сегодня голосов не подделаны и не даны в результате подкупа или давления?

Upd 05/12. Замечательные и заведомо достоверные итоги голосования, спасибо ivan.popelyshev.

http://www.youtube.com/watch?v=7_SAUXJDzVc
"Математика убивает креативность" (с) Фурсéнко

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

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

Автор I_love_natalia, 12 лет назад, По-русски

В отличие от обычных авторов "помогите разобраться, решение не работает" я долго не мог понять, почему мое решение работает :)

http://codeforces.com/contest/134/submission/915471

через 5 минут после контеста я понял, что забыл проверить, есть ли карты для обмена у того, с кем мы меняем. И очень расстроился. Уже подумав много нехороших слов про необходимость тестирования, ВНЕЗАПНО, я получил по ней ОК на систестах. В чем же дело?

P.S. просьба решения прятать за спойлеры.

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

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

Автор I_love_natalia, 12 лет назад, По-русски

Я не буду писать про результат нашей команды (кстати, каждый из них уже осознал свою роль). Но несколько моментов таки порадовало.


Команда ИТМО случайно отправила задачу на светофор. WA.


I don't SSU. А вы?

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

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

Автор I_love_natalia, 12 лет назад, По-русски

Anonymous is reporting in с открытия NEERC.

Пост постепенно будет обновляться.

11:15 Все как всегда началось с культурной программы. В прошлые разы это были участники СПбГДТЮ, но в этот раз, похоже, они выбрали музыкальную группу по рейтингу на TopCoder. Возникло желание найти Петрозаводскую майку и идти купаться в мазуте.

11:21 Выступают официальные лица. Выступают хорошо, как, впрочем всегда и было. 

11:26 Показали выступление Царева на встрече с Медведевым. Тоже порадовало. Кстати, великолепный диалог (примерно).

- (Федор Царев) Наши студенты трижды становились чемпионами мира по программированию.

- (Дмитрий Медведев) Да, я помню, я трижды с ними встречался.

- (Федор Царев) Да, вы дважды с ними встречались.

11:42 Выступление трех спонсоров уложилось в 2 минуты. Да здравствуют спонсоры NEERC, самые лаконичные спонсоры в мире!

11:54 А вот это выступление с песочной анимацией надо просто видеть, очень хочу запись. Просто потрясающе.

12:05 Перехвалил спонсоров...

12:21 Mail.ru объявила о завтрашней трансляции на http://news.mail.ru/neerc2011

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

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

Автор I_love_natalia, 12 лет назад, По-русски

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

В ходе экспериментов я натолкнулся на забавный факт. Оказывается, что разделение по дивизионам увеличивает рейтинг участников первого дивизиона! Рассмотрим гипотетическую последовательность:
1) участник Х хорошо сыграл тур див-2 и попал в первый дивизион, с рейтингом, скажем, 1735.
2) участник Х некоторое время поиграл в див-1.
3) участник Х слил тур див-1 и попал в див-2 с рейтингом, скажем, 1680.

Тут можно заметить, что при балансировке по сумме 55 рейтинга этого участника осталось в див-1! Более того, обратного перехода рейтинга, вообще говоря, никогда не происходит. Таким образом, даже при отсутствии поступления новых участников, разные дивизионы при балансировке суммы дают инфляцию рейтинга в див-1 (и дефляцию в див-2). Вот такие пироги.

P.S. Хотелось бы задать Михаилу Расиховичу несколько вопросов относительно системы расчета рейтинга на Codeforces. Точнее, попросить уточнить/поправить модельные предположения (на эффект выше они не повлияют).
1) Seed в 0-base вычисляется как сумма вероятностей проигрыша участникам.
2) Рейтинг изменяется на величину 360 * относительную разницу фактического места и seed-а (т.е. деленных на количество участников тура).
3) Для участвующих в первый раз относительный 0-base seed равен n/2 (хотя, точнее было бы (n-1)/2).
4) ?? - При рассчете seed-а вероятность выиграть у участника, играющего в первый раз, считается 1/2, а не вычисляется на основании рейтинга. Обратное приводит к дисбалансировке суммы seed-ов и мест.
5) Хочется знать уточнения, внесенные для подавления инфляции в ходе ноябрьской революции, применяется ли округление (и если да, то как), а также уточнения, появившиеся после забавной ситуации, когда tourist выиграл контест и получил минус к рейтингу.

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

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

Автор I_love_natalia, 13 лет назад, По-русски
Здравствуйте, извините за очередную оффтопную тему. Сегодня мне стало интересно, как много спортивных программистов занимаются троллингом, и если такие есть(кроме меня :D), то на каких ресурсах обитаете (в России, в Европе), какие холивары считаете самыми красивыми и интересными в истории троллинга.

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

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

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

Знаю, что тема стара, как CodeForces, и что сейчас навлеку гнев большого количества пользователей, но все же.

Я провел небольшой подсчет. Вот количество успешно решенных задач D и E фиолетовыми пользователями на последних раундах.

  Итого Раунд Число задач
 91  2
 90 1
 88 0
 87 0
 86 0
 85 0
 84 12
 83 1
 81 0
 80 9
  25


Итого получается, что 2,5 из примерно 160 фиолетовых участников в среднем решают в первом дивизионе задачу, которой нет во втором. А в половине случаев фиолетовым участникам задачи D и E вообще оказываются не по силам.

Внимание, вопрос. Не настало ли время фиолетовых участников отправить во второй дивизион?

==========================================================
В связи с ноябрьской революцией, частично отражающей выводы данного поста, теме закрыта минимум до 123 раунда (оценки дают порядка 200+ красных к этой дате).

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

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

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

Подумал, что отвечать в соответствующем обсуждении каждому будет утомительно, решил создать для этого новую ветку.

Примечание. Ни одну задачу не сдавал. Могут быть ошибки. Пишу как решал бы сам, что не придумал очно - спасибо MikeMirzayanov за замечательный разбор после контеста.

Задача А.
Общие намеки на решение

Может быть показано, что при оптимальном начальном выборе игроков ситуация на поле полностью определяется тройкой чисел (расстояния до гениев).

Действительно, понятно, что если расстояние до некоторого (одного) гения у игрока 2 меньше, чем у игрока 1, то помешать "захватить" его игрок 1 никак не может.

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

утверждение 1. Игрок 2 при оптимальном начальном выборе не может изменить баланс ходом приблизижающим к двум "лучшим" гениям одновременно. Иначе: а почему он сразу не выбрал первой эту точку?
утверждение 2. Игрок 1 при оптимальном начальном выборе не может изменить баланс ходом приблизижающим к двум "лучшим" гениям одновременно. Иначе: а почему игрок 2 не выбрал первой эту точку?

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

Задача В.

Отсортируем банки по координате, посчитаем частичные максимумы для ответа на запрос "количество денег на отрезке индексов 1..i", переберем правый ограбляемый банк и бинпоиском найдем границу индекса возможного левого. Лучшая сумма - ответ.

Задача С.

Перебираем все пары горизонтальных отрезков, считаем, сколько вертикальных пересекает их оба, и прибавляем к счетчику С(верт, 2)

Задача D.

Думаю, что не решившие эту задачу зря читают этот разбор.

Задача Е.

Найдем (взвешенный) центр дерева. Дальше разберем случаи, а ответ найдем по динамике по поддеревьям.

Upd. Если центр - две точки, то надо либо пошинковать ребро между ними, либо поддерево одной, либо поддерево другой. Если центр - одна точка, надо пошинковать все кроме одного пути от нее до наиболее удаленных.

Задача F.

Для начала, вычистим строчку от вхождения [a-z][A-Z]. Например, aA означает понятно что, а aB понятно что.

Также, если первая команда вытащить или последняя добавить - понятно что.

После этого строка будет выглядеть как ([a-z]*\*[A-Z]*)* (то есть перед каждой звездочки будет сколько-то добавлений в стек, после - сколько-то вытаскиваний из стека)

Воспользуемся стандартной динамикой по подотрезкам.

Ответ на отрезке [i,j] это единица плюс (либо ответ на отрезке [i-1,j-1], если s[i] == s[j], либо ответ на отрезке [i, j-1], если s[i] == '*', либо ответ на отрезке [i+1, j], если s[j] == '*'),
либо ноль плюс (либо ответ на отрезке [i, j-1], если s[j] == '*', либо ответ на отрезке [i+1, j], если s[i] == '*', либо сумма ответов на отрезках [i,k] и [k+1,j])

Заметим, что в качестве k в последнем случае достаточно проверить лишь либо позицию звездочки, либо позицию границы описанного выше шаблона.
Доказательство. а) заметим, что если подпоследовательность начинается закрывающейся, она неправильная. б) заметим, что если подпоследовательность заканчивается открывающейся, она неправильная. в) заметим, что все позиции, где не выполняются пункты а) и б) - указанные выше.

Задача G.

В качестве состояния берем (позиция короля, маска наличия фигур) и запускаем BFS. Достижимости считаем заранее для каждой маски.

Задача H.


Понятно, что достаточно найти gcd всех чисел заданного шаблона.

Выпишем все возможные числа, получающиеся заменой одной буквы на 1, а остальных на 0.
Если различных букв 10, то вычтем из всех минимальное из них, а само минимальное помножим на 45.
Полученный набор чисел имеет gcd как исходный набор.

Доказательство (на примере).
Пусть s = 'lalala'. Тогда любое получаемое число имеет вид x(L,A) = L * 101010 + A * 010101. Понятно, что оно делится на gcd(101010,010101). Понятно, что x(L+1,A) - x(L,A) = 101010, значит ответ - делитель 101010. Аналогично для 010101.
Если различных цифр было 10, например, s='qwertyuiop', то x(...) = P + O * 10 + ... + Q * 10^9. Заметим, что Q + W + ... + P = 45. Тогда x(...) = 45 + 9*o + ... + Q * (10^9 - 1). Смотрим рассуждения выше.

Задача I.

Думаю, что не решившие эту задачу зря читают этот разбор.

Задача J.

Проверим, что ответ не равен 0. Проверим, что ответ не равен 1, пытаясь жадно поменять числа местами (если оба встанут - меняем). Иначе будем думать, что это перестановка.

Пусть есть перестановка (1 2 3 4 5 ... N), т.е. массив имеет вид 2 3 4 5 ... N 1. Поменяем местами 2 и N, 3 и N - 1 и т. д. Массив будет иметь вид N N-1 ... 3 2 1. Очевидно, что полученная перестановка (1 N)(2 N-1)(3 N-2) ... может быть досортированна за один тик. Известно, что любая перестановка может быть представлена в виде произведения циклов. Проделаем подобную операцию в каждом цикле. Получим сортировку за 2.

Задача K.

Рассмотрим плоскость событий (x,t), красный свет будет на нем вертикальным отрезком. Задача - провести прямую, которая пересекает наименьшее число отрезков. Отсортируем точки "крутильной сортировкой" по углу (Upd. возможно, локальное название. Сортировка x1 * y2 > x2 * y1) и после этого пройдем последовательно и найдем участок, покрытый наименьшим числом отрезков. Видимо, важно не учитывать недостижимые по ограничению скорости отрезки (можно поймать TLE).

Задача L.

Очевидно, что каждый "маленький" цикл может быть посчитан по его двум точкам касания. Сделаем это для всех случаев. Между "маленькими" циклами ответ посчитаем, например, "разорвав" цикл перебором одной точки и потом посчитав динамику по состоянию (текущее положение, "правая" отметка на цикле), обходя его по часовой.

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

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

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

Родилась интересная идея в рамках "поделки на коленке", которой спешу поделиться.

Есть много алгоритмов факторизации (например, описанные на e-maxx), но, кажется, что всем им можно понаходить нехорошие контрпримеры в данном диапазоне (по крайней мере, они известные стандартные, и можно ждать подобного, хотя в детали не вдавался - может быть, просветят).

Пусть дано N ≤ 1018. Для начала, проверим маленькие делители до 107 (решето Эратосфена и деления должны уложиться в таком диапазоне). Также проверим, что число не точный квадрат.

Теперь, число либо простое, либо имеет два простых делителя не больше 1011. Попробуем найти функцию Эйлера от числа . Очевидно, что она лежит в диапазоне

Зададимся некоторым a. Предпросчитаем an для n ≤ 107. Если у числа окажется маленький порядок, то просто запомним этот порядок. Иначе с шагом 107 пройдем диапазон значений pq - 1011 - 107 ≤ n ≤ pq - 1 + 107 и обнаружим решения an = 1, в которых одно из n будет являться искомым значением функции . Удостовериться, что данное значение является искомым можно просто решив квадратное уравнение и проверив один из получившихся делителей.

Будем проверять a начиная с двух и так далее. Единственной особенной ситуацией может быть то, что много чисел в начале будут иметь маленький порядок. Будем попутно считать НОК всех получившихся порядков, и, как только этот НОК будет больше 107 проведем процедуру проверки на с шагом НОК.

Не реализовывал, хотя выглядит верным. Discuss.

Upd 1. Сортировать 107 чисел после предпросчета может быть долго. Быть может, надо понизить эту константу до 106 (105 проверок нас вполне устроит). Кроме того, можно использовать тот факт, что делится на 4 и наш шаг делится на 4 и сохранить только 107 / 4 шагов предпросчета.

Upd 2. Итого к реализации: gcd, быстрое возведение в степень, решето Эратосфена, решение квадратного уравнения, точное извлечение корня из числа до 10^18. Не так много и совсем стандартно.

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

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

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

По мотивам  http://codeforces.com/blog/entry/2374 от  SkidanovAlex.

Изначальная формулировка задачи (та же самая, просто другими словами).

Имеется N потоков. На всех имеется общий объект синхронизации следующего вида: в синхронном режиме поток обращается к флагу, смотрит его значение ("да" или "нет"), и по желанию выставляет новое значение флага "да" или "нет".  

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

Все потоки помечены собственным номером. Планировщик задач действует строго случайным образом.

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

Вроде бы, легко. Далее положение флага будем считать известным.

б) задача 2. Необходимо, чтобы каждый поток с гарантией узнал, что все потоки закончили работу. То есть каждый поток должен сказать "хватит", причем все остальные потоки должны к этому моменту хотя бы раз обращаться к флагу, после чего перестать обращаться к флагу.

Есть решение, хотя оно и ужасно непрактично. И есть еще более непрактичное решение, в котором потоки неразличимы :)

в) задача 3. Будем оценивать средние затраты времени на синхронизацию потоков в задаче 1, считая, что ни один поток не может отказаться от работы. Будем считать, что флаг имеет O(1) >= 2 состояний. Возможно ли добиться оптимальных затрат ? Кажется, что можно добиться

На это нет идей даже близко.

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

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

Автор I_love_natalia, 13 лет назад, По-русски
"Администрирование постов здесь не практикуется по причине демократии, а жаль..."
AWPRIS


Видимо, администрирование постов здесь и правда не практикуется. Все круче.



Я не буду вторгаться в право администрации оценивать заведомую неверность какой-либо информации. Я задам сообществу три вопроса:

  1. Находится ли хотя бы один участник сообщества в заблуждении относительно моих анкетных данных?
  2. Под "большими картинками" понимается объем в КБ, размер в пикселях или и то, и другое?
  3. Следует ли считать шутку "Berland, City N"  достаточно скучной для того, чтобы ее удалить?
    (напомню, что в Берляднии N городов, а город N - типичное место жительства анонима)

Примечание. Любителям разжигать оффтоп о кольчатых червях - найдите другое место!


P. S.
Возможно, когда вы читаете это, я уже регистрирую новый ник по причине бана.
P. P. S. Не бойтесь ссылок.

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

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

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

Я не буду просить, чтобы вы ее решили. Просто кажется интересным.

Пусть дан некоторый массив a размером N < 230 32-битных целых чисел. Требуется выполнить M запросов вида "сумма чисел на данном отрезке" за O(N+M), используя как можно меньше дополнительной памяти.

Очевидно, что существует решение, использующее 30 * N бит дополнительной памяти.


Update 1.
Если допускать сложность O(N+M*log(N)), то можно добиться 6 * N бит дополнительной памяти.


=============

В связи с особыми шаманствами, думаю, надо формализовать задачу немного по-другому.

Пусть дан некоторый массив a размером N из β-битных целых чисел. Требуется выполнить M запросов вида "сумма чисел на данном отрезке" за O(N+M), используя как можно меньше дополнительной памяти. Операция сложения и обращения по индексу выполняются за О(1), умножение процессор не поддерживает.

Очевидно, что существует решение, использующее бит дополнительной памяти.

Если допускать сложность O(N+M*log(N)), то можно добиться сколь угодно мало дополнительной памяти ценой сколь угодно большой константы во времени.

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

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

Автор I_love_natalia, 13 лет назад, По-русски
Ответа на комментарий по задаче так и не получил, поэтому перепост.

Мне кажется, для любых a и t верно утверждение



если



Это связано с тем, что в последовательности предпериод не превосходит степени максимального простого в t, а период после разложения t = t1t2 на часть t1, взаимно простую с a и все остальное будет совпадать по длине с периодом , делителем , делителем

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

Примитивной программой проверил до t <= 100, n < t*4, работает.


Как использовать этот факт, если это верно? 

Например, расчет быстрым возведением в степень требует либо представления числа n в двоичной системе счисления, либо использования десятичного возведения в степень с плохой константой. При ограничениях a, b ≤ 106, n ≤ 1010000000 быстрое возведение в степень невозможно.

С уточнениями от freopen

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

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

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

Очень вдохновился этим старым постом участника ralekseenkov.
Думаю, стоит повторить нечто подобное.

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

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

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

Это решение этой задачи было придумано однажды ночью при разработке совершенно другого контеста :)

Пусть - ответ задачи.

Тогда верен факт (например, можно доказать его из формулы включений-исключений)


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

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

Автор I_love_natalia, 13 лет назад, По-русски
Но почему-то добавление страны не работает. Как быть?

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

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