CODEFESTIVAL site is updated with info about this year edition but only in Japanese.

Using Google Translate I read that this time only people living in Japan are allowed to participate (at least in the final round).

rng_58, can you confirm this?

Main reason for asking now is that the Finals date is 17.11 which is very close to TCO onsite dates (13.11-16.11).

I want to apologize once more for queue problems. It has also aggravated some tight ML/TL issues which probably would be not so big otherwise. I hope you enjoyed the problems nevertheless.

38799778

38799800 — logs
38799811 — case analisys

38799824

38799831

38799840

I hope that Petr is not mad at me for my joke.

38799850
38799853 — completely different solution with complexity O(6^n / 2)

38799873

38799881

I hope that PrinceOfPersia is not mad at me for my joke.

38799887

Hello!

I'm glad to invite you all to Round 485 which will take place on Tuesday, May 29 at 18:35 UTC+3.

There will be 6 problems in each division, 3 of them are shared between divisions. 2 of div.2 problems created by KAN, 7 others created by me. The contest duration is 2 hours. My problems were originally used in HSE Championship.

I would like to thank Merkurev and GlebsHP with whom I discussed the problems, I_love_Tanya_Romanova for testing, KAN for round coordination and Codeforces and Polygon team for these beautiful platforms. I would also like to thank HSE for organizing the event. Oh, and kb. for writing great legend for one of the problems (he will be surprised).

For those who for some reason like to know score distribution in advance:
div.2: 500 — 1000 — 1250 — 1750 — 2250 — 3000
div.1: 500 — 1000 — 1750 — 2500 — 2750 — 3000
But I didn't properly discuss it with KAN so this is subject to change :)
UPD: Discussed with KAN, scores for C and D in div.2 increased by 250.

Good fun, have problems, read all the luck. As usual.

Oh, and if there will be no bad things, round will be rated. I hope.

I'm very sorry for issues with queue. I understand that it could ruin the contest for many of you. But please be understanding. Bad things happen. It could be some network problems or some electricity problems. MikeMirzayanov, KAN and other people behind Codeforces trying their best to provide good service. But sometimes it's very hard for some reasons. I hope that you enjoyed the problems despite all the bad things.

We decided that round will be rated.

Editorial will be posted tomorrow.

div.1 winners:
1. tourist
2. jqdai0815
3. Radewoosh
4. webmaster
5. LHiC

div.2 winners:
1. sminem
2. Fortza_Gabi_Tulba
3. cheburazshka
4. Lomk
5. 2ez4me

Editorial is up.

Всем привет.

27 мая пройдёт личное первенство ВШЭ по спортивному программированию. К участию приглашаются (очевидно) студенты ВШЭ, а также школьники Москвы и Московской области, показавшие высокие результаты на региональном туре ВсОШ по информатике (500+ баллов, если у вас немного меньше, тоже можете подать заявку, если мы сможем вас разместить — разместим). Более подробную информацию можно прочитать здесь. Регистрация.

Задачки делаю я, другие плюшки — ФКН ВШЭ.

Ещё раз подчеркну — это не открытое первенство. Пожалуйста, не надо регистрироваться, если вы студент другого вуза :)

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

На этих же задачах будет проведён Codeforces раунд 29 мая. Разумеется, о раунде будет ещё отдельное объявление :)

Когда-то давно я хотел сделать канал с какими-то мыслями по поводу задач с регулярных контестов
Сегодня я даже что-то сделал
Получилось стремно, на мой взгляд
Но я надеюсь, что
1. кто-то кроме меня тоже захочет что-то писать
2. формат постепенно трансформируется во что-то прикольное

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

К сожалению, RUS only. Я не готов писать так много на английском.

Ну и раз уж зашла речь: У меня есть более персональный канал, но там тоже почти все про ACM. Настолько почти все, что канал даже был признан блогом года по версии snarknews :)

I think that most of us know about situation with problem 843B - Интерактивный LowerBound. The intended solution (and it looks like all possible solutions) was randomized and it generates huge amount of hacks based on fixed randseeds.

I want to mention that I'm not against good randomized problems and I even set one myself.

But for me it seems that hacks can ruin such type of problems. The only thing author's solution is better than contestant's is that it is invisible during the competition. I can even imagine that some tester's solutions (maybe not the solution which is used to generate judge answers) was broken by some hacks.

I think that it breaks the problem as art piece and breaks the contest format too. You solved the problem just like authors wanted and now... it depends on is there a hacker in your room. It also breaks the idea of hacking. There is no bug in my solution, why should I be hacked? And why should the guy get 100 points for hacking me? He didn't crack my solution, he abused CF 'Run' tab.

And for me it looks like authors didn't think about that bug/feature and now they try to protect themselves in comments. For me it could be a good enough reason not to use this problem on CF round. This problem would be a good problem in ACM contest and I know that these guys do ACM contests. But maybe there were a way to prevent such abuse of hack system?

What about forbidding hacking this particular problem? It has two obvious flaws (maybe more).
1. After this post it can give a hint that you should use randomized solution — Yes, this is a problem.
2, All problems should be equal! You are taking away our sacred right to hack!!!1! — Are they? There are a lot of problems with no hacks on CF. There can be many reasons: the problem was too easy, or too hard, or it has no corner cases, or it can be solved only in one way, or, or... You can say that I propose unnatural way to prohibit hacking and in those cases it was prohibited by the problem itself. But (in my opinion) such randomized problem also naturally prohibits hacks because hacks can ruin the problem.

And it is also not true that all problems were 'equal' in this sense before. There were some problems with multitests which allow to hack with only one test in multitest. There can be a bug in handling multitesting but we cannot hack this bug.

This brings us to less cardinal solution: make some bounds on hacks. Like n ≤ 100 or (in this particular problem) let only choose values in list, but not their order.

Anyway, I think that problemsetters and coordinator should think about these matters in the future.

cgy4ever, when will the round be? clist.by says that it will be tomorrow in 19:00 (MSK), but three days ago it was 18:00 (MSK) and I also cannot find anything related on TopCoder itself. For example, there is no such competition in Web Arena calendar.

Я получил футболку с надписью "CODEFORCES THREADS 2017", но я не помню такого контеста.
С другой стороны, за Good bye 2016 обещали футболки.

Возможно, я не знаю какого-то перевода слова thread.

Так или иначе, MikeMirzayanov (или gKseni), можете рассказать, что это за футболка?)

Suppose we want to solve a problem by doing binary search on answer. Then the answer will be checked against jury's answer by absolute or relative error (one of them should be smaller then ε). For simplicity we will assume that our answer is always greater than 1 and smaller than B. Because of that, we will always use relative error rather than absolute.

Suppose we have made n iterations of our binary search — what information do we have now? I state that we know that real answer is lying in some segment [x_i, x_i + 1], where 1 = x₀ < x₁ < ... < x_i < ... < x_2ⁿ = B. And what is great — we can choose all x_i except for x₀ and x_2ⁿ.

Now, for simplicity, we will also assume that we will answer x_i + 1 for segment [x_i, x_i + 1] and the real answer was x_i — it is the worst case for us. It is obvious that we will not do that in real life, any other answer would be better, but you will get the idea.

So, what is our relative error? It is . Worst case for us is when relative error is maximal. It is logical to make them equal — exactly what we do by binary search with absolute errors. . We can assume that so . Now we have , but , so . How large should be n to get error less than ε? . Much smaller than .

How to write such binary search? We want to choose m in such a way that or simply .

Now I want to deal with some assumptions I made.

How to choose answer in the end? Again, (it is basically the same as dividing the segment in binary search).

What to do if the answer can be smaller than 1? Try 1; if answer is smaller than 1~--- use standard binary search (because absolute error smaller than relative); is answer is bigger than 1~--- use the binary search above.

P.S. I have never heard about this idea and come up with this while solving 744D - Hongcow Draws a Circle. I'm sorry if it is known for everyone except for me.

Если вы зарегистрированы на тимусе, то вы должны были получить письмо с приглашением на этот контест. Контест состоится в субботу (19 ноября) в 11 МСК.

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

Контест проводится по стандартным правилам ACM, длительность — 5 часов. К участию приглашаются как команды (до трех человек), так и одиночные участники. На этих же задачах проводился отбор на чемпионат Урала для уральских команд, поэтому, пожалуйста, не принимайте в нём участие, если вы писали этот отбор.

Контест готовили Um_nik, sivukhin, kb., Tinsane и crassirostris.

Hello!

October Clash on HackerEarth has started and you have 23 more hours to go.

I am the author of this problemset and niyaznigmatul is a tester. I want to thank sivukhin who helped me a lot with preparation.

I hope you find the problems interesting and wish you good luck!

Q1: I'm a newbie. What should I do to become great coder?
A1: Stop doing competetive programming Solve problems.

Q2: I'm doing CP for two months and I'm still not red green. What should I do?
A2: You are lazy and impatient Solve more problems.

Q3: You became a red in less than two years, it is unbelievable!
A3: No, it isn't. You can do it too if you will solve fucking problems.

Q4: You became a red blah-blah-blah such a huge fan blah-blah. Oh, and what should I do to become as great as you?
A4: ... right. You already know the answer. Solve problems. I hate you.

Q5: I'm not good at DP [or something]. What can you suggest?
A5. Maybe you should try to stop asking stupid questions and solve some problems on DP? Or read some blogs and editorials.

Q6: I can't solve a problem / understand your code. Can you help me?
(Well, it is not a bad question in general. It is a good (if you really want me to explain something not to write the solution instead of you) question. But...)
A6: Sure. Can you provide the link to the problem / code?
(I'm not joking, it is a real story).

Bonus!
Q0: Hello bro/sir.
A0: Stop doing this please.

Access to the specified resource has been forbidden.

Codeforces said 20 minutes ago when I was trying to login. The same was about two weeks ago. In both cases I was unable to login for about 10 minutes.
And I constantly logout. Sometimes I can't read 3-4 blog posts before logout.

There were a post about logouting two or three days ago but I can't find it now because search is not working too.

I've noticed during the contest that we can see all the hacks in our room.

Now MikeMirzayanov says that it was a bug and will be fixed soon.

I think it really will be bad if there are tons of hacks. But it is very useful to know which problems can be hacked (I mean which problems was already hacked by someone). Can you add number of successfull and unsuccessfull hacks on each problem to the PROBLEMS page?

Допустим, вы проводите соревнование для очень разной по силе аудитории. Например, у нас завтра отбор на ВКОШП.

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

Можно рассказывать в порядке A, B, C ... Правда, если в середине встретится сложная задача, то слабые участники могут забить и перестать слушать.

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

Что бы вы сделали?

Приглашаю принять участие в онлайн-версии уральской региональной командной олимпиады по программированию.

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

Контест состоится в субботу 17.10 в 11:00 МСК одновременно с самой олимпиадой.

Авторы задач — Um_nik, sivukhin, kb., hx0, Merkurev, KuchumovIlya, droptable (спойлер: задача не имеет отношения к палиндромам!)

Продолжительность контеста — 5 часов, правила ACM ICPC. Условия будут на русском и английском языках. Ссылка на вход

Пользуетесь ли вы prewritten-кодом на раундах OpenCup?)
Разделю вопрос на два:
1) Если вы используете шаблон, пишите ли вы его каждый раз в начале контеста? (понятно, что это не влияет на результаты почти никак, просто интересно)
2) Пользуетесь ли вы заранее написанными стандартными алгоритмами (поток, венгерка, суфструктуры, что-нибудь ещё)?

Про нас (Ural FU Dandelion): Мы пишем шаблон каждый раз в начале контеста (может, за редкими исключениями), стандартные алгоритмы не копируем.

Ни в коей мере не хочу никого пристыдить или в чём-то обвинить, тем более что использование prewritten-кода разрешено правилами. Всем добра :)

Тест:
{1}
{1}
Ответ жюри: 2
Количество перестановок с каким-то свойством больше, чем количество перестановок вообще.
UPD: Они уже заметили.

569A - Music

Пусть перед очередным запуском прогружено S секунд песни, найдем, сколько будет прогружено перед следующим запуском. . Отсюда x = qS.

Тогда решение: будем умножать S на q пока S < T. Количество таких умножений — это ответ.

Сложность —

569B - Inventory

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

Такую задачу можно решать жадным алгоритмом. Если мы встретили число, которого ещё не было, при этом оно от 1 до n, то мы его оставим. Для реализации можно завести массив used, в котором отмечать уже использованные числа.

Затем нужно ещё раз пройти по массиву и распределить неиспользованные числа.

Сложность — O(n).

568A - Primes or Palindromes?

Известно, что количество простых чисел, не превосходящих n, — число порядка .

Если мы зафиксируем длину числа k, то количество палиндромных чисел такой длины будет порядка . Это .

Таким образом, количество простых чисел асимптотически больше количества палиндромных чисел, а значит для любой константы A найдётся ответ. И для такого ответа . В нашем случае n будут не больше 10⁷.

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

При A ≤ 42 ответ не превышает 2·10⁶.

Сложность — .

568B - Symmetric and Transitive

Давайте сначала разберёмся, в чем же конкретно неправ Вовочка. В доказательстве хорошо всё, кроме того, что мы сразу взяли a, b такие, что . Если такие есть, то действительно . А если их нет? Если для a нет такого b, что , то, очевидно, не (иначе мы бы взяли b = a).

Отсюда понятно, что наше бинарное отношение — это какое-то отношение эквивалентности, к которому присоединили такие элементы a, что для всех них не существует таких b, что .

Тогда решение можно разбить на две части:

1. Посчитать количество отношений эквивалентности на множествах размеров 0, 1, ..., n - 1

2. Посчитать, сколькими способами туда можно добавить недостающие "пустые" элементы.

Отношение эквивалентности можно задать разбиением на классы эквивалентности.

Тогда первую часть задачи можно решить динамическим программированием: dp[elems][classes] — кол-во способов разбить elems первых элементов на classes классов эквивалентности. Переход — каждый элемент мы можем либо отнести в один из уже существующих классов, тогда их количество не изменится, либо же создать новый класс, тогда их количество увеличится на 1.

Вторая часть задачи. Зафиксируем m — размер множества, над которым мы посчитали количество отношений эквивалентности. Тогда нам нужно добавить к нему ещё n - m "пустых" элементов. Позиции для них можно выбрать C[n][n - m] способами, где C[n][k] — биномиальные коэффициенты. Их можно заранее посчитать треугольником Паскаля.

Тогда ответ — .

Сложность — O(n²)

568C - New Language

Пусть мы зафиксировали буквы на каких-то позициях, как проверить, что на остальные позиции можно расставить буквы так, чтобы получилось слово из языка? Ответ — 2-SAT. Действительно, для каждой позиции есть два взаимоисключающих варианта (гласная и согласная), а правила языка — это импликации. Таким образом, такую проверку мы можем сделать за O(n + m).

Будем уменьшать длину префикса, который мы оставляем таким же, как у слова s. Тогда следующая буква должна быть строго больше, чем в s, а весь дальнейший суффикс может быть любым. Переберём эту букву и проверим с помощью 2-SAT, есть ли решения. Как только мы обнаружили, что решения есть, мы нашли правильный префикс лексиграфически минимального ответа. Затем будем обратно наращивать префикс, какая-то из букв точно подойдёт. Мы получили решение за O(nmΣ ). Σ из решения можно убрать, заметив, что каждый раз нам нужно проверять только минимальные подходящие гласную и согласную буквы.

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

Сложность — O(nm)

568D - Sign Posts

Предположим, что решение есть. Если n ≤ k, то мы можем на каждую дорогу поставить по столбу. Иначе рассмотрим любые k + 1 дорогу. По принципу Дирихле среди них найдутся две, для которых будет общий указатель. Переберём эту пару дорог, поставим столб на их пересечение, уберем дороги, которые тоже проходят через эту точку. Мы свели задачу к меньшему числу столбов. Таким рекурсивным перебором мы решим задачу (если решение существует).

Решение это работает за . Если написать аккуратно, это может зайти.

Но это решение можно ускорить. Заметим, что если у нас есть точка, через которую проходит хотя бы k + 1 дорога, то мы обязаны поставить столб в эту точку. При достаточно больших n (у меня в решении отсечка n > 30k²) такая точка точно есть (если решение существует), причём её можно искать вероятностным алгоритмом. При условии, что решение существует, вероятность, что две произвольные дороги пересекаются в такой точке не меньше , поэтому если попробовать 100 раз, то с вероятностью такая точка найдется, и мы сможем уменьшить k.

Все проверки можно делать в целых числах.

Сложность — .

568E - Longest Increasing Subsequence

Будем поддерживать массив c: c[len] — минимальное число, на которое может заканчиваться возрастающая подпоследовательность длины len (Одно из двух стандартных решений задачи о наибольшей возрастающей подпоследовательности). Элементы этого массива возрастают и добавление очередного элемента v к обработанной части последовательности сводится к нахождению такого i, что c[i] ≤ v и c[i + 1] ≥ v. При обработке пропуска нам нужно попробовать вставить все числа из множества b. Предварительно их отсортировав и двигаясь двумя указателями вдоль массивов b и c мы можем проделать нужные обновления за O(n + m).

Авторами подразумевалось использование O(n) памяти для восстановления ответа. Этого можно добиться следующим образом: 1. Параллельно с массивом c будем хранить массив c_index[len] — индекс элемента, на который заканчивается оптимальная НВП длины len. Если она заканчивается в пропуске — будем хранить, например,  - 1. 2. Также сохраним для каждого не пропуска — длину НВП(lenLIS[pos]), заканчивающейся в этой позиции (это несложно делается в процессе вычисления массива c) и позицию(prevIndex[pos]) предыдущего элемента в этой НВП (если это пропуск, опять же  - 1).

Теперь приступим к восстановлению ответа. Пока мы не наткнулись на пропуск — можно спокойно восстанавливать НВП с конца. Сложность обнаруживается, когда несколько следующих элементов последовательности попали в пропуски. Но можно несложно определить что это за пропуски и чем их заполнить. А именно: пусть сейчас мы стоим в позиции r. Нам нужно найти такую позицию l (не пропуск), что мы сможем заполнить ровно lenLIS[r] - lenLIS[l] пропусков между l и r возрастающими числами в интервале (a[l]..a[r]). Позицию l можно итеративно перебирать от r - 1 до 0, параллельно насчитывая число пройденных пропусков. Проверку условия описанного выше можно несложно сделать с помощью пары бинпоисков.

Немного подробнее и с деталями:

1. Как узнать, что между позициями l и r можно заполнить пропуски так, чтобы не ухудшить генерируемый ответ?
   Пусть countSkip(l, r) — количество пропусков на интервале (l..r), а countBetween(x, y) — количество различных чисел из множества b, лежaщих в интервале (x..y). Тогда позиции l и r хорошие тогда и только тогда, когда lenLIS[r] - lenLIS[l] = min(countSkip(l, r), countBetween(a[l], a[r])). countSkip можно насчитывать в процессе уменьшения границы l, countBetween(x, y) = max(0, lower_bound(b, y) - upper_bound(b, x)).

2. Что делать, если НВП заканчивается или начинается в пропуске (тогда мы не знаем, откуда начать/где закончить)?
   Наиболее простым решением будет добавить  - ∞ и  + ∞ в начало и конец нашего массива соответственно. Это позволит избежать проблем с такими крайними случаями.

Сложность — времени, O(n + m) памяти

Всем доброго времени суток.

Скоро состоится Codeforces Round #315, авторами которого являются студенты УрФУ sivukhin и Um_nik. Это второй наш раунд, первый пришелся на черные дни Codeforces, и мы надеемся, что второй наш раунд не вызовет таких катаклизмов :)

Мы хотим поблагодарить команду Codeforces за эту замечательную платформу и Polygon. Особенно хотим отметить Zlobober за помощь в подготовке задач.

Желаем всем удачи!

UPD1:
Разбалловка.
div2 : 500-1000-1500-2250-2750
div1 : 500-1000-1500-2250-2500
Настоятельно рекомендуем прочитать условия всех задач. Мы постарались подготовить достаточно разнообразные задачи, вполне возможно, что сложные для нас задачи будут простыми для вас.

UPD2:
Разбор

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

div1:
1. KAN
2. Petr
3. enot110
4. tonyjjw
5. Konijntje

div2:
1. Lost
2. loser21
3. fyiwxp221
4. hqpwca
5. LazyWolfLin

Всем спасибо за участие.

More precisely: How to generate large inputs?

А пока все радуются фантастической возможности поучаствовать в Я.Алгоритме, у меня назрел вопрос по VKCup.

В официальной группе ВК была информация о том, что онсайт будет 24-27 июля.
Может быть, я что-то пропустил, но на кф я ничего такого не видел.

"Лучшие 20 команд по результатам отборочных интернет-этапов будут приглашены в финал соревнования, который состоится в июле 2015-го года в Санкт-Петербурге. Компания ВКонтакте покроет расходы на проезд и проживание финалистов, которые будут бороться не только за звание лучших из лучших, но и призовой фонд чемпионата." (c)
С кем связаться по поводу билетов и проживания?

Может, я не прав, но мне кажется, что годик назад сильно-красных было от силы человек 15-20, да и красных было сотни три.

Обычно когда происходит инфляция, с этим что-то делают.

Можно, например, поднять границы до 2300 и 2700 соответсвенно.

There was a tag search in the upper-right part of the page and now there is not.

What has happened?

Пару раз сталкивался с такой ситуацией: добавление комментария в код меняет вердикт проверки.

Сегодня удаление одних комментариев и вставка других меняют вердикт с TL 9 на RTE (access violation) 9.

Год назад комментирование cin >> n; в конце программы меняло вердикт с RTE (access violation) 34 на RTE (access violation) 13.

Дело происходит на тимусе, компилятор Visual C++ 2010.

Можете помочь с этим? Что может вызывать такое поведение?

UPD: Второй пример.
http://pastebin.com/41yqH6BF
http://pastebin.com/7PE31Erm
Условие