Сравнение производительности разных реализаций дерева отрезков Иногда я задумываюсь, какую реализацию дерева отрезков написать в задаче. Обычно я при помощи метода "пальцем в небо" выбираю какую-то и в большинстве случаев она проходит ограничения. Я решил подвести основу, так сказать базу, под этот выбор и протестировал на производительность 4 разные реализации: <ul> <li> Простой рекурсивный "Разделяй и властвуй" <spoiler summary="Код"> ~~~ struct SimpleRecursiveSegmentTree { unsigned size; private: std::vector<long long> t; void _build(const std::vector<int> &v, unsigned p, unsigned l, unsigned r) { if (r == l + 1) { t[p] = v[l]; return; } unsigned m = (l + r) / 2; _build(v, 2 * p + 1, l, m); _build(v, 2 * p + 2, m, r); t[p] = t[2 * p + 1] + t[2 * p + 2]; } long long _get(unsigned p, unsigned l, unsigned r, unsigned a, unsigned b) const { if (b <= l || r <= a) { return 0LL; ...

Full text and comments »

Codeforces Round 1050 (Div. 4) Фанатский разбор A-G. --- Всем привет! Давно не было разборов, за что я дико извиняюсь. Но сегодня я хочу сделать разбор на недавний контест Div4. Сразу скажу, что для каждой задачи вы сможете просмотреть код для полной ясности идеи. Так что если то-то непонятно, то смело смотрите код. Удачи) <p align="center"> <img src="https://i.ibb.co.com/7tGX7dh1/1705387659-krots-top-p-milie-animeshnie-kotiki-pinterest-43-1.jpg" width="200" height="200"> </p> --- <spoiler summary="Задача A"> **Идея:** Если `n` чётное — все `x` уничтожатся парами, останется `0`. Если `n` нечётное — один `x` останется, значит ответ равен `x`. **Примеры:** * `n = 4, x = 5` → все уничтожились → `0`. * `n = 5, x = 7` → остался один → `7`. <spoiler summary="Code:"> ~~~~~ #include <iostream> #include <bits/stdc++.h> #define ll long long #define pb push_back #define f first #define s second #define all(x) x.rbegin(),x.rend() using namespace std; const ll MOD = 1e9+7; void bruh(){ ll a,b; cin >...

Full text and comments »

Фанатский разбор Codeforces Round 1052 (Div. 2) A-D1. Всем привет! Сегодня раунд получился довольно интересным, поэтому я решил сделать разбор на задачи A–D1. P>S Если вам не понятны какие то части разбора, то смело смотрите код). <p align="center"> <img src="https://i.ibb.co.com/7tGX7dh1/1705387659-krots-top-p-milie-animeshnie-kotiki-pinterest-43-1.jpg" width="200" height="200"> </p> <spoiler summary="Задача A"> **Полное решение:** Пусть `f(x)` — количество вхождений числа `x` в массив. При построении последовательности мы всегда ограничены минимальным `f(x)` среди выбранных элементов. Если взять элемент с частотой `f(x)`, то длина последовательности может увеличиться: ``` mx = max(mx, f(x) * cnt), ``` где `cnt` — количество уже добавленных элементов, включая текущий. Так последовательно обновляем ответ и выводим `mx`. **Алгоритм:** 1. Посчитать частоты `f(x)` для всех чисел. 2. Отсортировать или перебрать их по убыванию. 3. На каждом шаге обновлять `mx`. 4. Вывести максимальный результат. <spo...

Full text and comments »

Еще один фанатский разбор задач:) --- **Всем привет!** Сегодня разбор задач с Codeforces, которые я решил: E1, G (1742), F, C (1739), C (1738), D1, G (1725), G (1722). <spoiler summary="Задача 1 — Делимые числа (простая версия, E1)"> **Ссылка на задачу:** [E1](https://mirror.codeforces.com/contest/1744/problem/E1) **Идея решения:** Перебор x невозможен для полного диапазона y, но x ограничен a < x ≤ c, а y можно вычислять через gcd: x \* y | a \* b. **Алгоритм:** 1. Перебираем $x$ от $a+1$ до $c$. 2. Вычисляем $g = \gcd(a \cdot b, x)$, чтобы выделить общий делитель. 3. Вычисляем $y = \frac{a \cdot b}{g}$. 4. Проверяем, попадает ли y в диапазон b < y ≤ d. 5. Если есть подходящая пара — выводим x, y, иначе — -1, -1. **Особенности:** * Суть в том, что через gcd можно получить минимальное y, которое точно делит a\*b вместе с x. * Не требуется перебирать все пары (x, y), что экономит время. **Вывод:** задача решается перебором x и прямым вычислением y через gcd. </spoiler> --- <spoiler...

Full text and comments »

Фанатский разбор на Educational Codeforces Round 182. A-D. Всем привет! Сегодня я бы хотел написать разбор на вчерашний edu div2. Приятного чтения:) <p align = "center"> <img src = "https://i.ibb.co.com/W4Yj3kfv/anime-cartoon-characters-cute-cats-spring-pictures-happy-cute-art-animals-kittens-pets-grap-1141449.jpg" width = "10" height = "10"> </p> ---- <spoiler summary="Задача A"> **Полное решение:** У этой задачи есть 2 решения: 1. **Простой брутфорс.** Пусть `x` = префикс, `y` = середина, `z` = суффикс. При маленьких ограничениях на `n` можно написать кубический перебор. Поддерживаем `l, r`, где `x = [1,l]`, `y = [l+1,r]`, `z = [r+1,n]`. Перебираем все такие пары `(l,r)` и считаем суммы для `x, y, z`. Это решение работает за `O(n³)`. 2. **Конструктив.** Заметим: сумма `x+y+z` при правильном разбиении должна делиться на 3. Возможные варианты: `[1,1,1]`, `[0,1,2]`, `[1,0,2]`, `[2,1,0]`. То есть условие корректности: либо все три суммы равны, либо все попарно различны. Тогда можно просто взят...

Full text and comments »

Теоретический минимум для программиста [Кросспост] Шарпиц продолжает радовать нас замечательными постами в жж.<br>Предлагаю обсудить сей эпичный пост:<br><a href="http://sharpc.livejournal.com/67583.html">http://sharpc.livejournal.com/67583.html</a><br><br>Многие начинающие программисты, особенно обучающиеся в провинциальных вузах, часто не знают, в какую сторону им развиваться, и что они должны знать для того, чтобы эффективно работать по специальности. Удивительно, но каждый день используя продукты и технологии, созданные другими программистами на основании развитых областей знания, они даже не догадываются о том, как они устроены.<br>[cut]<br><br>Построенные на теории массового обслуживания и протоколе GSM сети мобильной связи; PHP-скрипты, исполняющиеся на удаленных серверах и передающие свою выдачу через Ethernet по TCP/IP на компьютеры с NDIS-драйверами; процессоры, переупорядочивающие и спекулятивно исполняющие наборы инструкций для того, чтобы скомпенсировать вызванную ограничениями полупроводниковой элект...

Full text and comments »

Фанатский разбор Codeforces Global Round 29 (Div. 1 + Div. 2). --- Всем привет! Сегодня я хотел бы представить разбор на вчерашний раунд. Если какая-то часть останется не до конца ясной, смело смотрите код — он полностью прояснит решение. --- <spoiler summary="Задача A"> **Полное решение:** Заметим: - если `a < b`, то ответ всегда равен `2`. Мы можем сначала выбрать `a`, затем `b`. Пример: `a = 2, b = 5 → 2 → 5`. - если `a > b`, то ответ не может быть `2`. Пример: `a = 4, b = 2`. Если взять `4`, то потом выбрать `2` нельзя. Однако есть другой способ: * если `a > b` и `a - 1 > b`, то можно выбрать `1`, затем `b`, и затем `a - (b+1)`. Всего получится `3` хода. * если же `a - 1 == b`, то решение невозможно. Пример: `a = 5, b = 4`. После выбора `1` и `4` придётся снова выбрать `4`, но это запрещено. Ответ: `-1`. **Алгоритм:** 1. Если `a < b` → ответ `2`. 2. Если `a > b` и `a - 1 > b` → ответ `3`. 3. Если `a - 1 == b` → ответ `-1`. <spoiler summary="Code:"> ~~~~~ #include <iostream> #include <...

Full text and comments »

Codeforces Round #757 (Div. 2) Editorial [A. Divan и магазин](https://mirror.codeforces.com/contest/1614/problem/A) <spoiler summary="Решение"> Для того чтобы решить эту задачу, давайте воспользуемся следующим жадным алгоритмом. Отсортируем цены плиток шоколада по возрастанию, после чего будем идти слева направо и брать шоколадки, которые имеют цену не меньшую, чем $l$, но не большую, чем $r$ до тех пор, пока у нас не закончатся деньги. Количество плиток шоколада, которые мы взяли, и будет являться ответом на задачу. Итоговая асимптотика по времени: $\mathcal{O}(n\log{}n)$. </spoiler> [B. Divan и новый проект](https://mirror.codeforces.com/contest/1614/problem/B) <spoiler summary="Решение"> Очевидно, что чем более часто мы должны ходить в $i$ здание, тем более близко оно должно быть к главному офису. Из этого следует жадный алгоритм. Давайте поставим главный офис в точку $0$, а все остальные отсортируем по $a_i$. Тогда самое посещаемой здание поставим в точку с координатой $1$, второй по частоте в $-1$, третье в $2...

Full text and comments »

Белорусская областная олимпиада 2018 Привет всем. На этой неделе (8-12 января 2018 года) проходит областная олимпиада по информатике в Беларуси. Олимпиада проходит во всех областях (а их у нас всего шесть) в одно и то же время с одним и тем же набором задач. Здесь можно обсудить олимпиаду, ознакомиться с уловиями задач (надеюсь, что все участники олимпиады ознакомятся с условиями на самой олимпиаде) и, может быть, если я смогу решить, с решениями. **Всем участникам желаю удачи!** [cut]  _Условия и решения задач для каждого из туров появятся не раньше их завершения._ ## Первый тур #### Задача 1. Два квадрата <spoiler summary="Решение">_Задачу можно решать разными способами, но я попоробую рассказать самое короткое решение, которое только смог придумать._ Найдем bounding box закрашенных клеточек. Пускай мы будем знать его левую границу $l$, правую границу $r$, верхнюю границу $u$ и нижнюю границу $d$. Теперь заметим, что у нас может быть только два случая: 1. Левая верхняя клетка одного квадрата нахо...

Full text and comments »

Time For English _Часто замечаю в CF постах предложения-извинения про плохой английский. Думаю это время пришло!_ # English Resources Полезные сайты, видео, подкасты, книги и прочие ресурсы для изучения английского языка. ### Сайты и приложения для изучения английского языка - https://lingualeo.com/ru - https://skyeng.ru/ - https://ru.duolingo.com/ (есть разные языки) - https://www.italki.com/ (есть разные языки) - http://rachelsenglish.com/ &mdash; описания и примеры произношения звуков и слов - https://lyricstraining.com/ - https://linguatrip.com/ru/ &mdash; языковые школы по всему миру - https://speekify.com &mdash; тренировка разговорного американского английского - http://wlingua.com/ru/ - https://www.lingoda.com/ru - http://www.thesaurus.com/ - https://www.memrise.com/ - https://www.rypeapp.com/ - https://www.oxfordlearnersdictionaries.com/wordlist/english/oxford3000/ &mdash; список слов для запоминания (по частоте употребления) ### Полезные инструменты и ссылки - Gra...

Full text and comments »

Как стать синим Наконец-то я смог это сделать!!! Спасибо моим тренерам [user:BledDest,2024-01-16] и [user:awoo,2024-01-16] за то, что занимались со мной эти полтора года. Пусть для кого-то это достижение звучит неубедительно, но я очень рад, что наконец-то закрыл эту цель, потому что уже полгода считал себя синим по уровню, но никак не получалось сделать это по факту. Я обещал самому себе, что обязательно напишу пост на тему того, как стать синим, потому что и самому не хватало такого, и в целом, на CF много ребят, которые ставят перед собой эту цель. Так что, прошу, подробный план того, как это сделать: Шаг 1: Перейдите на С++, если этого ещё не сделали. Конечно, можно обойтись и Python, но потом будут проблемы, если вдруг Вы захотите выйти на более высокий уровень, решать задачи на сложные структуры. Этот совет мне дал в своё время [user:BledDest,2024-01-16]. На самом деле, если вы не владеете функциональным программированием, Python покажется даже менее удобным, чем C++. Шаблончики всякие, ...

Full text and comments »

Петр Калинин: Про областную олимпиаду **(C) Петр Калинин, 2015-16. Этот текст можно свободно распространять на условиях лицензии Creative Commons Attribution-ShareAlike 2.0 (CC-BY-SA).** Областная олимпиада по информатике (формально — региональный этап Всероссийской олимпиады) пройдет в два тура 4 и 6 февраля в ННГУ им. Лобачевского. Немалая часть статьи конкретно про Нижний Новгород, но информация интересная :) Отбор на область ---------------- Отбор на нее осуществляется следующим образом. Решения районной (она же городская в ряде городов области — Дзержинске, Арзамасе и т.д.) олимпиады от всех школьников, набравших на районе 200 и более баллов, отправляются в жюри областной олимпиады (точнее, я точно не знаю, в жюри ли, или людям, ответственным за район на уровне области, но это не так существенно). Там все эти решения перепроверяются и сводятся по каждому классу в единую таблицу. И в этой таблице проводится граница: для каждого класса выбирается проходной балл, и все, кто набрал столько баллов или больше, ...

Full text and comments »

CodeForces: на стыке времен. <p>Вот уже спал ажиотаж вокруг CodeForces и стали видны основные недостатки в системе. Старые идеи уже не так хороши, как казалось раньше, а новых пока не придумали.</p><p>Много постов в блогах было посвящено различным недостаткам: от мелких багов до формата проведения соревнований. Все они описывают один или несколько аспектов, но не трудно заметить, что все это сводится к одному. Предлагаю взглянуть на формат проведения соревнований не с точки конкретной проблемы, а обратиться к истокам.</p><p>PS. Данный пост содержит идеи которые сейчас активно обсуждаются, но в виде взаимодействующих элементов. Некоторые вещи могут оказаться боянами.</p><p><strong>Сокращения используемые далее:</strong></p><p>CF = CodeForces</p><p>TC = TopCoder</p><p><strong>"В начале было Слово..."</strong></p><p>Предлагаю обратиться к тому, для чего вообще проводятся контесты. Можно выделить 3 основных направления:<strong><br></strong></p><p>1. С целью обучения. Зачастую такие контесты составляются тренерами, что...

Full text and comments »

Codeforces Round #217 (Div. 2): разбор задач ### [problem:370A] К задаче есть два подхода. Первый &mdash; три раза запустить поиск в ширину. Второй &mdash; более легкий, нужно лишь понять, что: * Ладья может достичь любого поля не более, чем за два хода. Если стартовое и конечное поле находятся в одной строке или в одном столбце, то достаточно одного хода. * Слон может достичь только клетки, окрашенные в тот же цвет, что и стартовая, и тоже не более чем за два хода. Если стартовое и конечное поле находятся на одной диагонали, то достаточно одного хода. Чтобы это выяснить, нужно проверить, что $r_1-c_1=r_2-c_2$ ИЛИ $r_1+c_1=r_2+c_2$. * Королю достаточно сделать $max(|r_1-r_2|, |c_1-c_2|)$ ходов. ~~~ int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2; if (r1 == r2 || c1 == c2) cout << 1; else cout << 2; cout << " "; if ((r1 + c1) % 2 != (r2 + c2) % 2) cout << 0; else { if (r1 + c1 == r2 + c2 || r1 - c1 == r2 - c2) cout << 1; else cout << 2; } cout << " "; cout << max(abs(r1 ...

Full text and comments »

15 чемпионат Урала. Отчет <div style="mso-element:para-border-div;border:none;border-bottom:solid #4F81BD 1.0pt; mso-border-bottom-themecolor:accent1;padding:0cm 0cm 4.0pt 0cm"><br> </div><h1>Чемпионат Урала<span style="mso-spacerun:yes">&nbsp; </span>и поездка в Екатеринбург</h1><div style="mso-element:para-border-div;border:none;border-bottom:solid #4F81BD 1.0pt; mso-border-bottom-themecolor:accent1;padding:0cm 0cm 4.0pt 0cm"><br> </div> <p class="MsoNormal"><i style="mso-bidi-font-style:normal"><span style="mso-tab-count:1">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>Кто сможет прочесть данный отчет от начала до конца, тому я пожму руку при встрече</i></p> <h2>Вступление</h2> <p class="MsoNormal" style="text-indent:35.4pt">Про чемпионат мы узнали, как и все, на сборах в Петрозаводске, и тут же про него забыли. Вспомнилось все только после<span style="mso-spacerun:yes">&nbsp; </span>анонса на <span lang="EN-US" style="mso-ansi-language...

Full text and comments »

Парсер контест: разбор архива задачи <p><b>Прием решений участников завершен. Спасибо за участие. В скором времени мы проведем финальное тестирование и подведен результаты.</b></p><p> Всем доброго дня. </p> <p><i>Все что написано ниже не первоапрельская шутка, но тоже мероприятие веселое :)</i> Мы рады анонсировать новое экспериментальное соревнование на Codeforces — "Парсер контест: разбор архива задачи". </p> <p> Вы когда-либо составляли тренировки, используя архивы прошедших контестов? Вы выкачивали из интернета архивы контестов для тестирования своих решений локально? Если да, то вы не могли не заметить, что каждый организатор так и норовит придумать свой собственный формат распространения задач. Да это правда! </p> <p> За свою жизнь я подготовил и провел огромное количество тренировок по прошедшим соревнованиям. Зачастую, это довольно однообразное занятие — часто к каждой задаче надо писать какие-то скрипты, которые переименовывают входные/выходные файлы задачи в стандартный вид. В архивах они называют...

Full text and comments »

Нужны идеи как быстро решать онлайн поиск длиннейшей общей подстроки в тексте Здравствуйте, столкнулся с такой задачей: Текст приходит как набор символов онлайн, алфавит может быть большим (до нескольких байт), вместе с символами приходят запросы (с частотой примерно 1 запрос на 10 символов): найти max длину подстроки между (pointer, cur_pos) которая повторяет строку начинающуюся с (pointer). Например, для строки (abcab[запрос префикса с 0, ответ длина 2, pos 3]cab[запрос префикса с 2, ответ длина 3, pos 5]). Т.е. для первого запроса ищем префикс abcab на участке bcab, находим ab; Для второго запроса ищем префикс cabcab на участке abcab, находим cab. Сейчас решаю ее с помощью хешей, но не устраивает производительность, на больших данных слишком много cache misses. Знает ли кто-то возможно ли решение быстрее? В теории суффиксное дерево позволяет искать max подстроку, но оно тоже кажется медленным, т.е. слишком большая константа в операциях поиска и построения + не совсем ясно как избавиться от вхождений до начала интервала поиска. Хочется алгорит...

Full text and comments »

Частота соревнований по дням Привет всем, т.к. я раньше не видел таблицы частоты соревнований на Codeforces по дням недели, то я решил его сделать. Следующая информация **действительна на 2 декабря 2015 года**. Для большей свежести считал соревнования только этого года. ### Всего было 71 соревнований, из них по дням: - Пн : 6 - Вт : 14 - Ср : 6 - Чт : 10 - Пт : 7 - Сб : 18 - Вс : 10 #### По процентным соотношениям: - `Пн : 8.5 %` - `Вт : 19.7 %` - `Ср : 8.5 %` - `Чт : 14.1 %` - `Пт : 9.9 %` - `Сб : 25.4 %` - `Вс : 14.1 %` #### **Чаще** всего (аж целых 25 %) контесты проводятся в **субботу**(Сб). #### **Реже** всего контесты проводятся по **понедельникам**(Пн) и **средам**(Ср). Может кому пригодится =)

Full text and comments »

C4 в ЕГЭ по информатике Доброго времени суток, CF. Возник вопрос --- просьба. Может ли кто нибудь написать решение задачи С4 из ЕГЭ по информатике на C++ используя map, прокомментировав основные шаги в своем решении? Желательно, чтобы при этом сложность алгоритма была оптимальной, насколько это возможно с map'ом. `Условие.` ------------------------------------------------ _В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет. Перед текстом программы кратко опишите используемый вами алгоритм решения ...

Full text and comments »

Педагогика, или что вы об этом думаете? <p> </p><p style="margin-left: 0.0cm;text-indent: 1.0cm;"><b style=""><span style="font-size: 12.0pt;line-height: 115.0%;font-family: &quot;Times New Roman&quot; , serif;">Задание: исходя из особенностей конкретных дисциплин, создать 2-3 ситуации для иллюстрации действия движущей силы обучения.</span></b> </p><p> </p><p style="text-indent: 1.0cm;line-height: normal;"><span style="font-size: 12.0pt;font-family: &quot;Times New Roman&quot; , serif;">Обучение – непрерывно развивающийся процесс. И для эффективной организации данного процесса необходимо вскрыть источники его развития. Что же является движущей силой обучения? Замечено, что чем больше учитель учит своих учеников, и чем меньше предоставляет им возможностей самостоятельно приобретать знания, мыслить и действовать, тем менее энергичным и плодотворным становится процесс обучения, и наоборот.</span></p> <p style="text-indent: 1.0cm;line-height: normal;"><span style="font-size: 12.0pt;font-family: &quot;Times New Roman&quot; ...

Full text and comments »

Статический анализ исходного кода на примере WinMerge [contest:238] Сегодня я хочу посвятить пост тематике, почему инструменты анализа исходного кода полезны вне зависимости от уровня знаний и опыта программиста. А польза такого анализа будет продемонстрирована на примере инструмента, который известен всем программистам &mdash; WinMerge. Чем раньше ошибка в коде приложения будет обнаружена, тем дешевле стоит ее исправление. Отсюда следует вывод, что наиболее дешево и просто ошибка может быть устранена в процессе написания кода. А еще лучше, если ошибка вовсе не будет написана. Вот только захотел сделать ошибку, так сразу хлоп себя по рукам и код написан уже правильно. Но так как-то не получается. Подход "надо писать без ошибок" все равно не работает. Даже высококвалифицированный программист, который никуда не торопится, совершает ошибки, начиная от простейших опечаток и кончая логическими ошибками в алгоритмах. Здесь срабатывает закон больших чисел. Вот вроде в каждом конкретном операторе "if" сделать ошибку невозможно. А написал 200...

Full text and comments »

Что надо прочитать!!! 17:58 Электромагнитное излучение — Википедия ru.wikipedia.org 17:57 Поле (физика) — Википедия ru.wikipedia.org 17:56 Частота — Википедия ru.wikipedia.org 17:56 Частота — Википедия ru.wikipedia.org 17:56 Частота — Википедия ru.wikipedia.org 17:56 Частота — Википедия ru.wikipedia.org 17:56 Частота — Википедия ru.wikipedia.org 17:56 Время — Википедия ru.wikipedia.org 17:54 https://ru.wikipedia.org/w/index.php?search=%D1%87%D0%B0%D1%81%D1%82%D0%BE%D1%82%D0%B0+%D0%B2%D0%BE%D0%BB%D0%BD%D1%8B&title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%9F%D0%BE%D0%B8%D1%81%D0%BA&go=%D0%9F%D0%B5%D1%80%D0%B5%D0%B9%D1%82%D0%B8&searchToken=6kl6ahnz7gqo5c78f6vuhmmzq ru.wikipedia.org 17:54 Поиск «частота волны» — Википедия ru.wikipedia.org 17:54 https://ru.wikipedia.org/wiki/%D0%94%D0%BB%D0%B8%D0%BD%D0%B0_%D0%B2%D0%BE%D0%BB%D0%BD%D1%8B#Связь_с_частотой ru.wikipedia.org 17:54 Волна — Википедия ru.wikipedia.org 17...

Full text and comments »

Частота контестов <P>Толчком к написанию этого сообщения послужил <A href="http://mirror.codeforces.com/blog/entry/856">пост</A> пользователя gasya о сайте CodeChef.com. Последнее время стал замечать, что становится все больше сайтов, где проводятся регулярные контесты. Вследствие этого начинают перекрываться времена контестов. </P><P>Например, в субботу будет:</P><UL><LI>Школьная командная олимпиада #3 (ЗКШ 201011) в 14:00</LI><LI>Тренировка ИТМО в 16:30</LI><LI>487-й Single Round Match на ТС в 20:00</LI></UL><P>Назрели следующие вопросы:</P><P>Такое было всегда и я это заметил только сейчас (: или же такая тенденция действительно существует?</P><P>Контесты на каких сайтах Вы предпочитаете? Какие решаете регулярно, какие "как получится", а какими пренебрегаете?</P>

Full text and comments »

подведение итогов уходящего года Всем привет! Я был согласен 2. Полностью согласен на финальных баталиях он существенно влияет на рокотеку в Петрозаводске, где в этом официальная часть — наверное, сделано для этого слова, то это всегда пользуется своей правоте. Давайте внимательно выслушивал других. Вот уж необычной схеме. Участников справедливо одарить самых лучших, чем сто раз увидеть, чем "полёт шмеля". =) Но давайте вернёмся к концу соревнования на вклад, а с чисткой комментариев и других номинациях. Тренер года? ;) Мне удалось поглядеть на красоты города, сделать сразу предупреждаю: ограничение на охоту Минотавра. К одиннадцати часам дня — разобраться в своём инструменте. Фурор произвёл pashka, выдав изумительную гитарную партию. Даже после начала случился пожар буквально за соревнованиями и нажимать кнопку Add частотой три с этой возможностью не предусматривалось (а может что-то тупили. На обед мы решили повеселиться и задачи последних оказался не получает и от пятки в своего-в-доску-парня путём надевания во...

Full text and comments »

[Offtopic] Какой процессор лучше? Подскажите, пожалуйста, какой процессор лучше? - Intel Core i5, 2 ядра, частота 2.5 GHz - Intel Core i7, 4 ядра, частота 2.2 GHz Не для игр (кроме Audiosurf и Heroes), больше для повседневной работы (Интернет, программирование, видео, музыка).

Full text and comments »

Частота ошибок в тесте Миллера-Рабина ( Томас Кормен ...) #### В книге "Алгоритмы: построение и анализ" авторы пишут : "_Если n &mdash; нечетное составное число, то количество свидетельств того , что n &mdash; составное , не меньше (n-1)/2_"(**Теорема 31.38**). n &mdash; число которое проходит тест на простоту. Доказательство этой теоремы мне полностью понятно . В конце доказательства говорится : "_... самое лучшее, что можно доказать с помощью улучшенной версии **теоремы 31.38**,- что количество значений оснований, не являющихся свидетельствами, не превышает **(n 1)/4**_". Я долго думал над тем как улучшить теорему ,но к своему сожалению ничего толкового в голову не пришло . Помогите пожалуйста разобраться каким образом нужно улучшить теорему 31.38, чтобы доказать :"_количество значений оснований, не являющихся свидетельствами, не превышает (n-1)/4_" и на ,что (какие факты,свойства) опирается доказательство . Спасибо .

Full text and comments »

Задача с тимуса Здравствуйте ! Я новичёк, хотелось бы узнать каким методом можно решить данную задачу http://acm.timus.ru/problem.aspx?space=1&num=1542 . Пробовал так &mdash; строим префиксное дерево из входных слов. Находим все слова, удовлетворяющие заданному префиксу, сортируем по частоте и выводим. Такое решение вылетало с TLE. Ещё пробовал пару способов, но всё равно получал TLE. Возможно через хеширование или дерево отрезков можно решить. Подскажите, пожалуйста, каким способом можно решить данную задачу

Full text and comments »

Частота проведения контестов. <p>Как всем известно, контесты проводятся раз в неделю. Многие из моих знакомых жалуются на то, что это слишком редко. Есть предложние проводить контест хотя бы два раза  в неделю.</p>

Full text and comments »