Автор GreenGrape, 3 дня назад, По-русски,

Привет.

В 19.08.2018 16:35 (Московское время), состоится общий рейтинговый раунд Codeforces Round #505. Этот раунд идет в паре с раундом #504.

Часть задач взята с Финала VK Cup 2018 (ashmelev, Errichto, lewin), часть придумана мной. Спасибо моим товарищам — Диме (_kun_), который, кстати, является координатором этого раунда, Коле (KAN), который позвал меня его проводить, а также Грише (gritukan) и Ильдару (300iq) за то, что они просто клевые.

Также спасибо Майку MikeMirzayanov за множественные баг-фиксы и замечательный Codeforces!

Задач будет семь со следующей разбалловкой:
500 — 1000 — 1500 — 1750 — 2250 — 2750 — 3500

UPD. Систесты окончены. Разбор

Поздравляем победителей!

  1. Swistakk
  2. CongLingDanPaiShang3k5
  3. Kostroma
  4. Benq
  5. AwD
  6. xumingkuan
  7. mcfx
  8. fjzzq2002
  9. Egor
  10. kriii

Так же, как и в прошлом раунде, по инициативе компании ВКонтакте будут разыграны очки GP30.

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

Напоминаю, что лучшие 10 по сумме очков GP30 получат фирменного плюшевого персика.

Надеюсь, что вам понравится. Удачи!

Полный текст »

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

Автор fjzzq2002, история, 2 дня назад, По-английски,

#IjustWantContribution

It seems there isn't any blog about Berlekamp-Massey Algorithm around here, so I decided to go on a try. :P

Acknowledgement: Hats off to matthew99 for introducing this algorithm.

What is 'linear recurrence'?

Assuming there is a (probably infinity) sequence a0, a1...an - 1, we call this sequence satisfies a linear recurrence relation p1, p2...pm, iff . (Obviously, if m ≥ n any p can do :P)

How to calculate k-th term of a linear recurrence?

For a polynomial , we define .

Obviously G satisfies G(f) ± G(g) = G(f ± g).

Because , if we let , then G(f) = 0. Also G(fx), G(fx2)... = 0. So G(fg) = 0 (g is any polynomial).

What we want is G(xk). Because G(fxk / f⌋) = 0, then .

Полный текст »

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

Автор Radewoosh, 43 часа назад, По-английски,

Hello, codeforces!

This time I've decided to choose a task from my own contest which took place last April and was known as the Grand Prix of Poland. If you want to write this contest virtually in the future, then consider not reading this blog. If you've participated in this contest and maybe even solved this task, then anyway I recommend reading it, cause this task has many very different solutions, each of them being very interesting (in my opinion). It's also a reason why this blog is longer than previous ones.

I'll write about task C "cutting tree" (not uploaded to the ejudge yet :/). The statement goes as follows:

You are given a tree with n vertices (1 ≤ n ≤ 2·105). The task is to calculate f(k) for each integer k from the range [1, n] where f(k) is defined as the maximum number of connected components of size k which we can "cut off" from the tree. A connected component of size k is a set of k vertices such that it's possible to traverse in the tree between any pair of these vertices using only vertices from this set. Chosen components are not allowed to intersect, so each vertex must belong to at most one component.

Полный текст »

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

Автор MikeMirzayanov, 46 часов назад, перевод, По-русски,

Друзья!

Я бы хотел отдельно обсудить ситуацию вокруг негатива касательно раунда 505.

Я понимаю, что большинство участников расстроены падением задач на систестах. В самом деле, претесты в задачах B, D и E оказались слабыми. С задачей C тоже не всё гладко, но ничего страшного я не вижу.

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

Задача B: 9 претестов, есть и большие и маленькие ответы, два претеста на -1, есть претесты с n = 1 и n = 2, есть четыре претеста для n = 150000.

Задача D: 14 претестов, среди них и ручные и 4 разных генератора, несколько претестов для n = 700, большинство ответов Yes, но есть и No. Моё мнение, что здесь мало было тестов на No.

Задача E: 14 претестов. Да, эта задача на финале VK Cup содержала 10 претестов и сильно упала у участников. Я добавил в претесты еще 4 теста из тех, на которых падали участники Финала. То, что даже после этого она упала у стольких из вас лично для меня — сюрприз.

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

Я не вникал во все задачи, но мне показался раунд интересным. Жестких фейлов по условиям, багов в тестах или решениях замечено не было. И система работала вполне прилично, очереди не было.

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

Спасибо.

Полный текст »

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

Автор lxn, история, 10 часов назад, перевод, По-русски,

Мне было интересно распределение рейтинга на codeforces. Рейтинг каждого участника доступен на сайте, можно пойти на вкладку 'Рейтинг' загрузить все страницы и распарсить их.

Картинка актуальна на 21.08.2018

Может быть кому-то еще это интерсно.

Полный текст »

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

Автор GreenGrape, 47 часов назад, перевод, По-русски,

Пожалуй, я не буду ничего комментировать :D

Автор: GreenGrape

Tutorial is loading...

Автор: GreenGrape

Tutorial is loading...

Автор: GreenGrape

Tutorial is loading...

Автор: GreenGrape

Tutorial is loading...

Автор: ashmelev

Tutorial is loading...

Автор: Errichto

Tutorial is loading...

Автор: lewin

Tutorial is loading...

Полный текст »

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

Автор im0qianqian, 10 часов назад, По-английски,

I am sorry to bother you, my account has recently had some problems. It was stolen by someone else I didn't know and changed my password and email address. I don't know if I leaked my password, or just hacked by someone else. In short, I can't change my password and email address. I can use it temporarily because my account has not been logged out. I am afraid that he will take my account to do something unethical, such as stealing data from the gym, or deliberately deleting something I have now. I know that if this article is seen by him, it may bring more tragic things, but I can only pray that such things will not happen. I know his email, and I also contacted him through QQ, but I have never received a reply.

I also tried to contact MikeMirzayanov and asked him to change the email address and password for me. I have not received a reply yet. In addition, I want Codeforces to send email confirmations when modifying email addresses, which is more secure.

Finally, if you have recently seen me posting some weird comments, please let me know, my email address is: im0qianqian@gmail.com, thank you!

Полный текст »

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

Автор PikMike, история, 4 дня назад, По-русски,

Привет, Codeforces!

В такой замечательный день недели, как 18.08.2018 17:35 (Московское время) состоится Educational Codeforces Round 49.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Владимир Vovuh Петров, Адилбек adedalic Далабаев, Иван BledDest Андросов и Михаил MikeMirzayanov Мирзаянов.

Удачи в раунде! Успешных решений!

А вот сообщение от наших друзей из Harbour.Space:

Hi Codeforces!

Our Hello Barcelona Programming Bootcamp will be kicking off next month from Sept 26 — Oct 4, and we’d love to see you there!

The boot camp will once again feature the all-time greats Mike MikeMirzayanov Mirzayanov, Andrey andrewzta Stankevich, Michael Endagorion Tikhomirov, Gleb GlebsHP Evstropov, Artem VArtem Vasilyev, Ivan ifsmirnov Smirnov and other world renowned Russian coaches to train the participants.

You will be competing and learning side by side with some of the greatest teams in the world, while learning from the best coaches the ICPC has to offer.

Be sure to register before September 1st so everyone has time to get visas if needed, and of course for the Early Bird Discount of 5% or the Loyalty Discount* of 20% off registration for the boot camp!

*The loyalty discount is offered to universities and individual participants that took part in Hello Barcelona Bootcamps and Moscow Workshops ICPC.

Learn more about Barcelona ICPC Bootcamp

You can ask any questions by email: hello@harbour.space

Поздравляем победителей:

Место Участник Задач решено Штраф
1 Um_nik 7 179
2 isaf27 7 343
3 RNS_KSB 7 357
4 eddy1021 6 157
5 djp_cqq 6 176

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 halyavin 200:-25
2 eR6 87:-58
3 jhonber 29:-1
4 Winniechen 35:-13
5 Kaban-5 19
Было сделано 697 успешных и 674 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A arknave 0:02
B eddy1021 0:06
C bekzhan97 0:12
D teja349 0:12
E step_by_step 0:10
F lee_sin 0:24
G uwi 0:39

UPD: Разбор опубликован

Полный текст »

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

Автор MikeMirzayanov, 21 час назад, перевод, По-русски,
Tutorial is loading...

Авторы: MikeMirzayanov, PikMike; разработчик: Vovuh.

Tutorial is loading...

Автор: MikeMirzayanov, разработчик: MikeMirzayanov.

Tutorial is loading...

Автор: MikeMirzayanov, разработчик: PikMike.

Tutorial is loading...

Авторы: Vovuh, MikeMirzayanov; разработчик: PikMike.

Tutorial is loading...

Автор: Errichto, разработчик: Errichto.

Tutorial is loading...

Автор: lewin, разработчик: lewin.

Tutorial is loading...

Автор: Endagorion, разработчик: Endagorion.

Полный текст »

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

Автор PikMike, история, 2 дня назад, перевод, По-русски,

1027A - Палиндромная замена

Разбор
Решение (PikMike)

1027B - Числа на шахматной доске

Разбор
Решение (Vovuh)

1027C - Прямоугольник минимальной стоимости

Разбор
Решение (PikMike)

1027D - Охота за мышью

Разбор
Решение (adedalic)

1027E - Противоположная раскраска

Разбор
Решение (PikMike) O(n^3)
Решение (BledDest) O(n^2)

1027F - Сессия в БГУ

Разбор
Решение (Vovuh)
Решение (Vovuh) Алгоритм Куна

1027G - X-мышь в общежитии

Разбор
Решение (adedalic)

Полный текст »

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