1 Тема от Baur

(0 ответов, оставленных в Problems)

Всем привет! Возникла необходимость написать и протестировать такие программы
1) расстояние от точки до прямой - это просто, просто хочу проверить точность
2) площадь произвольного выпуклого четырехугольника - единственное, что меня смущает и не дает применить метод трапеций - координаты трехмерные, поэтому мне кажется, что сначала надо проецировать четырехугольник на плоскость и потом считать. Но в интернете пишут, что модуль векторного произведения любых двух смежных векторов(двух смежных сторон четырехугольника) и есть искомая площадь - так считать нормально?
3) площадь пересечения двух произвольных 4-х угольников - я знаю, что в сети есть известные алгоритмы нахождения площади пересечения многоугольников, но я хотел бы воспользоваться тем, что у меня всего 4 точки и написать что-нибудь быстрое и хитрое и не такое умное, как площадь пересечения многоугольников=)

Собственно вопрос - кто-нибудь знает задачи на acm.mipt.ru,acm.timus.ru,acm.sgu.ru? подходящие для тестирования вышеуказанных программ?

Перейти к разделу: Problems

2 Ответ от Baur

(12 ответов, оставленных в Algo)

В этой ветке обсуждается взятие числа Каталана (а это тоже биномиальный коэффициент) по модулю-
http://e-maxx.ru/forum/viewtopic.php?id=172 (первый пост в той ветке- идея, последний пост - рассмотрение одного хитрого случая, у тебя то же самое должно пройти)
Единственное отличие: там n,k <=100000 и решение за O(N) проходит, а у тебя это не пройдет - но зато у тебя модуль M=100000 и ты можешь отсечь случай, где n,k>=100000 одним ифом - если n>=m бин коэф делится на M и ответ 0, иначе М<100000 и O(N) проходит.

Перейти к разделу: Algo

3 Ответ от Baur

(6 ответов, оставленных в Problems)

Lugera пишет:

Я думаю, что я написал описано идея, но она получает WA8. Может ли кто мне помочь.

Я тоже получил ВА 8. Написать бфс, который находит ответ (YES или NO) несложно, самое главное - без багов восстановить ответ. Могу дать свой код, может быть, ты найдешь в нем ошибку и скажешь мне:)
Мой код можно посмотреть здесь: http://acm.timus.ru/getsubmit.aspx/3319670.txt
ID и пароль я открыл здесь: http://acm.timus.ru/forum/thread.aspx?i … 5834002500

Перейти к разделу: Problems

4 Ответ от Baur

(6 ответов, оставленных в Problems)

KADR, а как ты реализовал эту идею? Я написал БФС по состояниям получаю ВА6 или ВА8.

Перейти к разделу: Problems

5 Ответ от Baur

(6 ответов, оставленных в Problems)

Спасибо большое! Будем разбираться.

Перейти к разделу: Problems

6 Тема от Baur

(6 ответов, оставленных в Problems)

в обсуждениях кто-то сказал, что можно решить эту задачу (http://acm.timus.ru/problem.aspx?space=1&num=1455) хешами. Как? Мне только полный перебор-расположений суффиксов в голову приходит, но это точно не пройдет:(

Перейти к разделу: Problems

7 Ответ от Baur

(4 ответов, оставленных в Problems)

Для сбалансированного дерева нужен не массив на N, а set<int> на N. Если там хранить неудаленные числа - то, есть в начале все числа от 1 до N, то как раз запрос сводится к нахождению к-того элемента в сете (то есть сет придется писать ручками). Я не знаком с  treap, но это же дерево, разве его не надо хранить в виде массива на N по аналогии с деревом отрезков? или там структура из указателей?

Перейти к разделу: Problems

8 Тема от Baur

(4 ответов, оставленных в Problems)

Как решить эту задачу - http://acm.timus.ru/problem.aspx?space=1&num=1439 за Nlog(N)?; очевидная идея - к-тая порядковая статистика за log(N)*log(N) сумматором или log(N) каким-нибудь сбалансированным деревом не катит из-за ограничения на N = 10^9 - массив такой длины не объявить (. Пытался приспособить сжатие координат, но что-то контрпримеры находятся(.

Перейти к разделу: Problems

9 Ответ от Baur

(4 ответов, оставленных в Problems)

e-maxx пишет:

Хотя непонятно, как это может быть связано с рантаймами - вы же не локально их внутри рекурсивной функции выделяли? Если использовали итераторы, и при этом меняли списки - неаккуратная работа с итераторами может привести к рантайму.

Нет, внутри рекурсивной функции ничего не выделял, только пробегался по элементам. Списки заполнил один раз - в саморм начале программы. Ну что ж, буду иметь в виду, что лист - шштука непредсказуемая и лучше использовать вектор, если возможно:)

Перейти к разделу: Problems

10 Ответ от Baur

(4 ответов, оставленных в Problems)

Блин, сдал, но как то тупо - просто заменил массив листов на массив векторов - а какая разница? может кто-нибудь объяснить? или пуш бак по-разному для них работает?

Перейти к разделу: Problems

11 Тема от Baur

(4 ответов, оставленных в Problems)

Кто-нибудь, сдавший эту задачу может сказать, какой размер стека надо установить, чтобы избежать рантайм еррора?
Я написал там оффлайн тарьяна в чистом виде и постоянно получаю  рантайм на 51. подозреваю на стек, но его увеличение до 16 и 25 мб не помогло. размеры массивов тоже проверил. Может быть такое, что при вставке числа в лист(я граф храню как массив листов, а не векторов, потому то пробежка по элементам быстрее вроде - как-то раз замена вектора листом спасла - но сейчас речь не об этом=) ), выделяется больше памяти чем надо и в итоге прога юзает слишком много памяти?

Перейти к разделу: Problems

12 Ответ от Baur

(8 ответов, оставленных в Problems)

alt пишет:

Надо разложить числитель и знаменатель на простые множители, разделить числитель на знаменатель, после чего перемножить все оставшиеся в числителе простые числа (по модулю).
Пример

С(3) = 6! / (3! * 4!) = (6 *  5 * 4 * 3 * 2) / ((3 * 2) * (4 * 3 * 2)) = (2 * 3 * 5 * 2 * 2 * 3 * 2) / ((3 * 2) * (2 * 2 * 3 * 2)) = (5^1 * 3^2 * 2 ^ 4) / (3^2 * 2 ^ 4) = 5 ^ 1

Спасибо, сдал задачу. Но только разложил не числитель и знаменатель а число К(по модулю которого берем) на простые и ТОЛЬКО ЭТИ простые исключил сначала из знаменателя, а потом из числителя(так пошустрее будет;)). Ну а потом применил метод, который описал в своем первом посте (там как раз уже гарантированно не будет неопределенностей вида
0*ans=0(mod K))

Перейти к разделу: Problems

13 Ответ от Baur

(8 ответов, оставленных в Problems)

alt пишет:

Я считал числа по формуле Catalan(n)  = C(2*n, n) / (n + 1) = (2n)! / (n! * (n + 1)!), где C(n,k) - биномиальный коэффициент

Я тоже считал по этой формуле(когда писал, что С(N)=a/b, я имел в виду a=2n!; b=n!*n!*(n+1)). Но посчитать в лоб, а потом взять по модулю не получится - факториал  слишком огромный получается. Поэтому и пришлось числитель и знаменатель считать отдельно по модулю, а потом уже делать все то, что я писал выше.

P.S Исправил свой первый пост, там действительно непонятно было, что переменные a и b означают.

Перейти к разделу: Problems

14 Тема от Baur

(8 ответов, оставленных в Problems)

Всем привет! Помогите разобраться с одним хитрым случаем в этой задаче: Дан порядковый номер числа каталана N(N<=5*10^5), необходимо посчитать его по модулю К (К не обязательно простое, к<=2*(10^9) ). Я решал так -
число каталана C(n) можно записать как дробь  a/b = c(n);
a=2n!; b=n!*n!*(n+1);
1)  Перепишем это в виде а = b*C(n) и возьмем обе части по модулю к
2)  Получим a%k = b%k*ans (ans = c(n)%k - это и есть ответ на задачу)
3)  chis = a%k и znam = b%k посчитаем одним циклом, не забывая на каждом шаге брать  chis,znam по модулю k
4)  Пришли к сравнению znam*ans==chis(mod k)
5) Поделим chis,znam,K на GCD(znam,K) - теперь znam и k взаимно просты и можно применить теорему Эйлера
znam^phi(mod)==1(mod K);
6) найдем ans - из пункта 4 - ans = chis* (1/znam) (mod K) ,
где 1/znam  = znam^(phi(mod K)-1) (см. пункт 5)
В степень возводим за логарифм, так как она может достигать 2*(10^9)
А теперь, собственно, хитрый случай: этот метод работает, когда chis!=0 && znam!=0, в противном случае возникает неопределенность вида 0*ans==0(mod K). Кажется, этого можно избежать, если заранее перед пунктом 3 сократить числитель и знаменатель на K (факторизовав К и применив формулу Лежандра)  - но как-то не кошерно ради одного случая писать отдельный код, да еще я не уверен на 100%, что это поможет. Кто-нибудь знает, как можно проще обойти этот случай?

Перейти к разделу: Problems

15 Ответ от Baur

(4 ответов, оставленных в Problems)

Всем спасибо! Разобрался.

Перейти к разделу: Problems

16 Тема от Baur

(4 ответов, оставленных в Problems)

У кого-нибудь есть идеи, как решить эту задачу деревом Фенвика? B contest&analysis написаны решения через мультисет и еще какие-то рандомные алгоритмы, но ссылка на эту задачу есть в статье BIT, значит как-то можно её решить Фенвиком. Короткое описание условия: Дана последовательность чисел(n=250.000), вы должны найти медиану каждого "окошка" длиной k (k=5000). Мне приходила идея приспособить нахождение инверсий, но это кажется неверный подход.

Перейти к разделу: Problems

17 Ответ от Baur

(7 ответов, оставленных в Problems)

Не совсем понятно. Возможно я что-то не так понял. Такое паросочетание даст нам - макс. количество пар (черная + белая клетка которые друг-друга бьют, на одной из них должен находиться конь). Но ведь может позникнуть "конфликт" между парами. Клетки одной пары могут бить клетки из другой пары

Перейти к разделу: Problems

18 Тема от Baur

(7 ответов, оставленных в Problems)

Народ, у кого-нибудь есть идеи на задачу: на доске NxN (N<=50) надо раcставить максимальное количество коней так, чтобы они не били друг друга, причем некоторые клетки могут быть вырезаны. Как можно найти число коней максимальным паросочетанием?

Заранее спасибо.

Перейти к разделу: Problems

19 Ответ от Baur

(2 ответов, оставленных в Problems)

Спасибо!

Перейти к разделу: Problems

20 Тема от Baur

(2 ответов, оставленных в Problems)

Подскажите, если кто знает, идею решения этой задачи http://acm.timus.ru/problem.aspx?space=1&num=1527 То, что высоту подбираем бинарным поиском, понятно. Как учесть 2 ограничения на ребро? Если бы было одно, то решалась бы дейкстрой и бинарным поиском, как 1379 на тимусе http://acm.timus.ru/problem.aspx?space=1&num=1379 , а тут два ограничения и непонятно как избежать неопределенности, если пускать дейкстру с двумя параметрами.

Перейти к разделу: Problems

21 Ответ от Baur

(7 ответов, оставленных в Algo)

Zayakin_Andrey пишет:

А как это доказать?

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

Перейти к разделу: Algo

22 Ответ от Baur

(7 ответов, оставленных в Algo)

KADR пишет:

Ну диаметр дерева можно находить и просто 2-мя бфсами.

А как это сделать?

Перейти к разделу: Algo

23 Ответ от Baur

(7 ответов, оставленных в Algo)

Пример задачи на динамику по дереву (была на сайте acm.albertina.ru который в данный момент недоступен):
Дано взвешенное дерево с N вершинами (N = 100000) Найти сумму расстояний между всеми вершинами.
Решение:
Посчитаем, во скольких путях между вершинами участвует какое-либо ребро. Пусть left  - количество вершин слева от ребра, а right - справа от ребра.
Тогда количество путей, проходящих через ребро - (left+1)*(right+1) // концы ребра тоже надо учитывать
И так для каждого ребра считаем эту величину и умножаем на вес ребра и прибавляем к общей сумме. Как это реализовать? В обычном DFS добавим переменную left - (что она означает, сказано выше).  "Наверх" возвращаем left+1. Для вершин, где нет соседей (для листов) возвращаем 1("саму себя"). Соответственно, right = N - left  и "вклад" ребра в сумму считается на лету: left*(N-left)*weight


P.S Если я не ошибаюсь, нахождение диаметра дерева - тоже на эту тему.

Перейти к разделу: Algo

24 Тема от Baur

(1 ответов, оставленных в Algo)

Если кто-нибудь знает задачи на физтехе, тимусе и сгу на эти темы напишите их номера.
Мне кажется, что эти задачи:
     http://acm.timus.ru/problem.aspx?space=1&num=1557
     http://acm.timus.ru/problem.aspx?space=1&num=1671
на эту тему, вот только решить их не получается.

Перейти к разделу: Algo