В голове засела задача:

Найти математическое ожидание количества точек на выпуклой оболочке(Точки как-то брошены на плоскость).

Не подскажите откуда она? (Я не уверен, что эта задача существует)

Есть задачка:

http://acm.timus.ru/problem.aspx?space=1&num=1557

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

В комментариях я прочитал, что можно это сделать за n + m.

Я научился делать только за n * n.

Мое решение:

Рассмотрим дерево обхода dfs. Ребра разбились на 2 типа.(прямые и обратные)

Удалять 2 обратных нет смысла(Граф останется связным).

Удаляем прямое ребро и обратное. Это можно сделать, как при поиске мостов, только поддерживаем не только самую высокую ссылку на верх, а еще и вторую по высоте.

Удаляем 2 прямых ребра. Здесь мы просто перебираем два прямых ребра и смотрим разбился граф на два или нет.(Это делается, опять же при помощи поддержания нужных ссылок на верх.)

Это краткое описание моего решения. Но как делать быстрее?

Изначально потенциалы равны кратчайшим расстояниям.

Вопрос 1: Как обновлять потенциалы?

Вопрос 2: Как доказывать, что при таком обновлении потенциалов не возникнет ребер отрицательной стоимости?

Говорят, что надо к старым потенциалам надо просто прибавить новое расстояние. Верно ли это?

Надо от вершины v до u найти реберно непересекающийся путь минимального веса.

Веса на ребрах могут быть отрицательными.

Умею делать за m * m. Надо быстрее.

Помогите пожалуйста!

Команда из 2 человек (skrydg, haku) ищет сокомандника для решения задачек.

Единственное требование — это желание и умение решать сложные задачи.

Для связи пишите на почту: skrrydg@yandex.ru

или на этом сайте.

UPD: За сутки нам никто не написал :(, поэтому мы вносим некоторые уточнения в требования -- нам не нужен человек, решающий гробы на полуфинале, нам нужен кто-то уровня жёлтого на CF или уровня призёра РОИ.

Встеретил задачу http://mirror.codeforces.com/gym/100197

Суть в том что надо n колец перетащить с одной ячейки на другую. Надо найти мин. количество перекладываний. Всего ячеек m. В обычных башнях n колец и 3 ячейки.

Решение,вероятно, такое:

Рассмотрим перекладывание самого большого кольца. Оно естественно будет одно, с начальной позиции на конечную. У нас останется n — 2 ячейки с какими-то кольцами. Если доказать, что в каждой ячейки будет последовательный отрезок колец (тоесть 1-2-3 или 10-11-12-13), то можно придумать динамику. Я просмотрел решения, примерно такое и пишут. Но как доказать этот факт?

Есть 2 решения, который принципиально ничем не отличаются.

1) http://mirror.codeforces.com/contest/375/submission/5504829

2) http://mirror.codeforces.com/contest/375/submission/11947758

Одно ловит TL, другое нет. Причем разница примерно в 2 раза.

Совершенно непонятно в чем проблема.

Задача King and Roads

Даны пары чисел(упррядоченные), каждое от 1 до n. Всего m штук. У каждой пары есть стоимость.

Надо выбрать сколько-нибудь пар чисел, так, чтобы :

Для каждого числа i от 1 до n должна существовать выбранная пара, такая что ее левое (правое) число равно i;

Тоесть все левые числа покрывают множество 1..n и тоже с правыми.

Надо минимизировать сумму всех выбранных пар.

n < 300; m < 300 * 300;

Вроде написал задачку, но нехороший spoj говорит что за нее 0 баллов.

Помогите, второй раз пишу, вроде все работает, не знаю где беда.

Задача: http://www.spoj.com/problems/QTREE3/ Решение: http://ideone.com/1U5Ruy

Не могу посмотреть вердикт. Если пишу бесконечный цикл, то он говорит что время все равно 0.00

Я не уверен что так должно быть http://mirror.codeforces.com/problemset/tags/2-sat

There are two solutions:

(1) http://mirror.codeforces.com/gym/100395/submission/8702299 Compiler : GNU C++ time: 3000 ms

(2) http://mirror.codeforces.com/gym/100395/submission/8702312 Compiler : MS C++ time: 670 ms

Why is visual studio so fast working with double?

http://mirror.codeforces.com/contest/484/submission/8617714

http://mirror.codeforces.com/contest/484/submission/8617627

различие этих решений только в выводе и вводе

Поясните что здесь не так?

Условие :

http://mirror.codeforces.com/gym/100285/attachments/download/2011/20132014-acmicpc-neerc-eastern-subregional-contest-en.pdf

Я умею решать за n * n / 32. Сначала, идем и ищем маленький массив как подстроку, потом битсетами берем xor и все хорошо.

После 25 попыток я понял что мне не загнать такую асимптотику ;)

На timus писали что-то про FFT, но как его туда впихнуть, не понятно.

Прошу помощи.

Как посмотреть таблицу результатов SRM на TC ??

Решаю задачку 2004 года с ограничениями MAXK <= 2000 MAXN <= 20000

Умею решать её за O( MAXK * MAXN )

Зашла бы такая асимптотика в 2004? И умеете ли вы ее решать быстрее?

Задача IOI 2004 Гермес. https://yadi.sk/i/oF7CX1tEaSsSX

Помогите решить задачку.

Есть массив чисел. Надо разбить его на n отрезков, так чтобы минимизировать суммарный риск для всех отрезков. Риск для одного отрезка это произведение длины отрезка на сумму чисел на нем.

Ограничения: Длина массива < 8000

n < 800

Числа в массиве < 1e9

Ссылка на задачу https://www.hackerrank.com/contests/ioi-2014-practice-contest-2/challenges/guardians-lunatics-ioi14