Хотелось бы узнать решение 2-х задач с тимуса↵
↵
1)http://acm.timus.ru/problem.aspx?space=1&num=1677 ↵
Знаю, как её решать неоптимально (проблемы с ML, но не с TL). Можно получить точную дробь-ответ в длинной арифметике. У нас цепь маркова, переходы задаются с помощью граней префикса строки, состояния- префиксы длины 0,1,2,...n=len(s). Переход из состояния i в состояние j происходит с P=1/A (A-мощность алфавита), i<n и с P=1 из n в n. Можно написать соответствующие матожидания и получить СЛАУ. Решать СЛАУ можно за O(n), введя коэффициенты a[i],b[i] и с начального значения их пересчитывать. Проблема возникает с тем, что они быстро растут и потому ML.↵
Код: https://ideone.com/41LFtk ↵
↵
↵
2)http://acm.timus.ru/problem.aspx?space=1&num=1849↵
Думаю, что мой алгоритм верный, но где-то кроется баг (скорее всего в модулярной арифметике). Вначале утверждение: пусть есть прямая l x=xo+ut, y=yo+vt. Тогда точка x,y принадлежит l <=> xv-yu=xo*v-yo*u. Отсюда сделаем предпосчёт: фиксируем всевозможные направления векторов стрельбы vx,vy и каждой точке xk,yk сопоставим 2 числа:(e,t), где e=xk*v-yk*u и t=xk,если u=0, иначе t=yk. Получим класс cl[u][v]: {e1,t1}, {e2,t2}, ... , {en,tn}, который отсортируем по e, а при равных e по t.↵
Теперь, получая луч (xo,yo,u,v), можно за O(logn) найти все точки лежащие на этой прямой (прямой, а не луче): нужны те точки, у которых e=xo*v-yo*u. Бинпоиском найдём в классе cl[u][v] границы alpha и beta. Среди этих точек нужны те, которые лежат на луче. Тут возможны случаи: если луч наклонный (например v>0), то тогда нужны точки с ординатой >= yo-ищем на [alpha, beta] бинпоиском по t, если луч горизонтальный (например u>0), то тогда нужны точки с абсциссой >= xo-ищем на [alpha, beta] бинпоиском по t (др. 2 случая аналогичны).↵
Код: https://ideone.com/0Fm1CG
↵
1)http://acm.timus.ru/problem.aspx?space=1&num=1677 ↵
Знаю, как её решать неоптимально (проблемы с ML, но не с TL). Можно получить точную дробь-ответ в длинной арифметике. У нас цепь маркова, переходы задаются с помощью граней префикса строки, состояния- префиксы длины 0,1,2,...n=len(s). Переход из состояния i в состояние j происходит с P=1/A (A-мощность алфавита), i<n и с P=1 из n в n. Можно написать соответствующие матожидания и получить СЛАУ. Решать СЛАУ можно за O(n), введя коэффициенты a[i],b[i] и с начального значения их пересчитывать. Проблема возникает с тем, что они быстро растут и потому ML.↵
Код: https://ideone.com/41LFtk ↵
↵
↵
2)http://acm.timus.ru/problem.aspx?space=1&num=1849↵
Думаю, что мой алгоритм верный, но где-то кроется баг (скорее всего в модулярной арифметике). Вначале утверждение: пусть есть прямая l x=xo+ut, y=yo+vt. Тогда точка x,y принадлежит l <=> xv-yu=xo*v-yo*u. Отсюда сделаем предпосчёт: фиксируем всевозможные направления векторов стрельбы vx,vy и каждой точке xk,yk сопоставим 2 числа:(e,t), где e=xk*v-yk*u и t=xk,если u=0, иначе t=yk. Получим класс cl[u][v]: {e1,t1}, {e2,t2}, ... , {en,tn}, который отсортируем по e, а при равных e по t.↵
Теперь, получая луч (xo,yo,u,v), можно за O(logn) найти все точки лежащие на этой прямой (прямой, а не луче): нужны те точки, у которых e=xo*v-yo*u. Бинпоиском найдём в классе cl[u][v] границы alpha и beta. Среди этих точек нужны те, которые лежат на луче. Тут возможны случаи: если луч наклонный (например v>0), то тогда нужны точки с ординатой >= yo-ищем на [alpha, beta] бинпоиском по t, если луч горизонтальный (например u>0), то тогда нужны точки с абсциссой >= xo-ищем на [alpha, beta] бинпоиском по t (др. 2 случая аналогичны).↵
Код: https://ideone.com/0Fm1CG
