Here is the statement https://wcipeg.com/problem/coi08p3

I found it very interesting, because restrictions are big. I was thinking about using array d[i] — number of cells with distance i to them, but I cannot recalculate it for one rectangle quickly.

So if you have any ideas, please share them

Дана скобочная последовательность из круглых скобок

нужно отвечать на запросы:

1. Определить, является ли скобочная последовательность с индекса l до r правильной

1. Изменить значение скобки под индексом i

Нужно реализовать ДО с запросами:

запрос (pos, x)

Найти

1. Ближайший к pos элемент, больший либо равный х

2. Изменить значение элемента в массиве

Вопрос в следующем — можно ли решить эту задачу(возможно, с долгим предпосчетом) быстрее, чем за линейное время? Я пока дошёл только до вычисления полиномиального хеша и сравнения двух подстрок за единицу, но перебрать их всё равно нужно O(n) Может, запоминать все позиции букв и идти только по префиксам с концом в букве, на которую заканчивается суффикс?

Есть такая классическая задача: дано N вершин многоугольника и K точек. Проверить для каждой точки, лежит ли она внутри многоугольника. Многоугольник может быть любым. Алгоритмы, представленные здесь и здесьYour text to link here... содержат лишь пару слов о том, что при использовании деревьев в предпроцессинге ответ на запрос можно сделать logN. Сам алгоритм я понимаю как нахождение количеств пересечений луча, направленного строго вправо из нашей точки. Для нахождения такого количества мне нужно знать количество отрезков, начало которых выше луча, а конец ниже или наоборот. а также количество отрезков где ровно одна вершина лежит на луче.

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

Недавно передо мной встала задача — найти цикл минимального веса в взвешенном графе на 20 вершин и 100 ребер. Используя обычный dfs-подход(смотрим исходящие рёбра из текущей вершины, рекурсивно запускаемся от детей), и оптимизацию, что если текущий путь больше минимального найденного, то продолжать нет смысла, я получил TL Прошу вашего совета — какие ещё оптимизации тут можно применить?

In this short article, I want to introduce you Python and provide some basic steps to start learning.
First of all, consider the advantages of Python:
Crossflatformed, easy-to-read, popular, contains lots of methods to make web-apps, games(include Android) and, of course, you can do Python for a living, Python-developers are needed to work in Google, Yandex etc.
The main disadvantage of this language is speed. If your project or program requires fast implementation, you have to use C++, C or other fast languages.

After this introduction, you might imagine how it's easy to work in a big company using only Python — of course, it's not true, you should study lots of other things in Computer Science, but Python provides to every person methods to complete their own projects.

Now, consider some tricks which we can use in competitive programming to decrease the time of making your program
1. If your task requires repeat string n times, you don't have to use cycles like "for" or "while", you may only write:

 s = n * s

In this case, if n = 5 and s = "ab", the result of the program will be:

s = "ababababab"

Quite easier than other languages, isn't it?
2. Consider case if you need to replace two variables. Quite simple in every language, isn't it?
For example swap() function in C++. But what if you need to replace 3 or four variables? To make a, b, c, d equal to b, c, d, a.
Quite difficult in C++, but in Python just write:

a, b, c, d = b, c, d, a

That's all!
So, if a was 1, b was 2, c was 3, d was 4 then after this code it will be 2, 3, 4, 1 respectively.

Hope, now you're interested in Python!
Now you can download IDE from https://www.python.org/getit/ and try to complete your first program using such textbooks:
https://drive.google.com/file/d/0B2Y-n6IlHYliSXZxMk0xT0NSY1E/preview
In Russian this one: https://pythonworld.ru/samouchitel-python

I hope I made you interested in Python because I am going to make such posts every week, consider some interesting tasks and provide useful books or notes.
See you soon :)

Зашел я недавно в википедию, посмотреть информацию про Petr, и оказалось, что она только на английском языке.

Непорядок! Ведь Пётр — программист из Москвы.

Вот я и перевел английскую статью на русский.

ссылка

Заходите, исправляйте ошибки.

Можете еще скинуть статей, которых не хватает в руВики, а я постараюсь их перевести :)

Предлагаю поздравить Petr с заслуженным первым местом на площадке Codeforces!

Напомню, по результатам Codeforces Round #363 (Div. 1) Petr занял первое место, решив все задачи.

Всем привет!

Через два дня, в 19:35 состоится Codeforces Round #339 (Div. 1 & Div. 2) Этот раунд необычен тем, что мы, его составители — обычные школьники, объединенные тем, что вместе занимаемся на кружке в 179 школе. Для нас этот раунд — первый опыт и мы постарались сделать его максимально интересным и безошибочным. Я приглашаю вас всех писать этот раунд, потому что задачи будут решаемы, но при этом даже tourist-у придётся подумать над некоторыми :)

Под началом и полным контролем Михаила Тихомирова(Endagorion) задачи для вас готовили: Егор Чунаев(ch_egor), Василий Алферов(platypus179), Дмитрий Саютин(cdkrot), Тимофей Гутор(Tigutor), Мария Федоркина (crossopt). Кроме того, задачи придумывали: Михаил Сорокин(themikemikovi4), Сергей Алейкин(Derrior). Отдельное спасибо Глебу Евстропову(GlebsHP) за помощь в подготовке контеста, Маше Беловой(Delinur) за перевод условий на английский язык, AlexFetisov и winger за тестирование, и, конечно, (MikeMirzayanov) за уникальные системы CodeForces и Polygon.

Раунд будет проведен по стандартным правилам Codeforces, сначала — претесты, потом финальное тестирование, внимательно продумывайте все случаи в своём решении.

Удачи всем на контесте!

UPD Разбалловка: Div 2. 500-1000-1750-2250-2250, Div 1. 750-1250-1250-2000-2500

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

Div1:

1. TankEngineer

2. KAN

3. Petr

4. Um_nik

5. snuke

6. matthew99

7. jcvb

8. superpear

9. pashka

10. fsouza

Div2:

1. mingaleg

2. Ronnoc

3. BoQiR

4. maks1906

5. zloyplace35

6. huansuz1

7. 2016

8. Danlark

9. MrPapaya

10. bohuss

UPD Разбор

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