Блог пользователя abzaloid

nearest neighbour problem
Автор abzaloid, 10 лет назад, По-русски

Всем привет!

Nearest neighbour -- это задача, где есть N точек , нужно в онлайн режиме отвечать на запросы: для новой точки узнать какая точка из N точек самая близкая. Используется Евклидово расстояние

Кто знает где можно сдать задачу на k-nearest neighbour?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

triangles
Автор abzaloid, 11 лет назад, По-русски

Всем привет!

Задача с одной из областных олимпиад: Даны N различных точек (xi, yi). Нужно найти кол-во различных прямоугольных треугольников, вершинами которых являются точки (xi, yi).

Ограничения: N ≤ 5000, |xi|, |yi| ≤ 104

timelimit: 2s, memorylimit = 64MB

Спасибо

Полный текст и комментарии »

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

Жадный алгоритм
Автор abzaloid, 11 лет назад, По-русски

Всем привет!

Скажем у нас есть какая-та задача, которая просит найти что-то мин/макс. Как можно определить(доказать) возможно ли решить эту задачу жадным способом? Либо додуматься, что по-любому придется применить что-то умное вроде динамического программирования.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

SNWS 2nd round
Автор abzaloid, 11 лет назад, По-русски

Всем привет!

Кто может рассказать решение задач А и D? У меня и в А и в D WA2 почему-то.

Спасибо

Полный текст и комментарии »

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

NEERC 2013
Автор abzaloid, 11 лет назад, По-русски

Всем привет!

Будет ли параллельно NEERC 2013 проходить его зеркало?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

Математическое ожидание
Автор abzaloid, 11 лет назад, По-русски

Всем привет!

Недавно задумался как решить такую задачу: Есть корень дерева, за каждый ход игрок может у любого листа дерева создать либо левого потомка (с вероятностью p), либо правого (с вероятностью 1 - p). Какого математическое ожидание высоты дерева после n ходов игрока?

UPD: Лист выбирается равновероятно.

Лист -- эта вершина с количеством потомков меньше 2.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

IOI online contest
Автор abzaloid, 11 лет назад, По-английски

Hi everybody!

Will be it possible to participate in IOI 2013 online?

Thanks

Полный текст и комментарии »

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

ACM ICPC четвертьфинал 2011-2012
Автор abzaloid, 13 лет назад, По-русски
Всем привет!

А когда начнется регистрация на АСМ 1/4 финал, в частности для Казахстана?!
Где и как надо регистрироваться?!
И примерная дата начала, место прохождение и все-такое где можно узнать?!

Спасибо...

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Разбор задач MeetUp Contest #5
Автор abzaloid, 13 лет назад, По-русски

1) Факторизация факториала


Сперва решетом находим все простые числа от 1 до N. Понятно, что все эти числа и есть делители N!,
потому что N! = 1 * 2 * ... * N. 
И записываем простые числа в массив p[]. 
То есть он будет выглядеть так: p[1] = 2, p[2] = 3, p[3] = 5, ...

Требуется посчитать, с какой степенью простой делитель p входит в число N!,
 т.е. найти наибольшее x такое, что N! делится на px.

Теперь как надо искать x для p?

 
Конечно, не до бесконечности, потому что берем только целую часть. 
Сложность нахождения степени делителя факториала O(logpN)

Итоговая сложность  ≈ O(NlogN), если считать грубо.

2) Реккурентное соотношение


Если посмотреть на ограничения, N ≤ 1018, то легко понять, что можно решать эту задачу за O(1) или за O(logN).
  • Можно воспользоваться быстрым возведением матрицы в N-ую степень за O(logN).
  • Можно найти перебором начальные несколько значений функции, затем найти закономерность(период функции). Скажем период равен P. И просто найти ответ за O(1), т.е. взять N по модулю P и вывести последнюю цифру, т.е. взяв f(N%P) по модулю 10.

3) Постройки


Надо найти количество построений дорог между N центрами, где N ≤ 100.
Можно представить сеть центров, как ориентированный граф с N вершинами. 
Максимум дорог(неориентированных) между вершинами такого графа может быть .
И у каждой дороги(u - v) будет три состояния:
  • u → v.
  • v → u.
  • дорог между u и v вообще нет.
То есть ответ: . Так как ответ может быть большим, надо использовать длинную арифметику.

4) Фея


Надо найти количество таких заполнений бланков ответа из N вопросов по K ответов, чтобы ни в одном варианте заполнения не было ни одного правильного ответа.

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

5) Райхан и таблица Менделеева


В данной задаче надо быстро проверять, находиться ли в таблице Менделеева элемент si + si + 1(конкатенация двух символов строки s). 
  • Для этого в C++, можно воспользоваться map'ом. Сложность будет O(NlogM)
  • Так же можно завести буленовый массив 26x26(в паскале можно сделать array['a'..'z', 'a'..'z'] of boolean). И для каждого элемента хранить true, если он есть в таблице Менделеева, иначе false. Или можно просто хранить элементы в хэш-таблице. Тут ограничения не большие и методов много. То есть сложность при таких методах будет O(N)

6) Веревка


Сперва надо отсортировать все окружности по углу(угловая сортировка). Можно было сортировать по тангенсу угла. Дальше надо было придумать формулу для нахождения длины части веревки соединяющей две последовательные окружности. Точную формулу можете вывести сами, для этого нужно знать, как вычислять расстояние между двумя точками в декартовой системе координат, и знать теорему косинусов. 
Сложность будет O(NlogN).

7) Палиндромы


Ограничения в этой задаче N ≤ 102000.
Пусть длина N равна n.
Для длины k, количество палиндромов будет 10[k / 2], где [x] = округленное значение x. Надо сложить все значения для k = 1..n - 1.
 
Теперь рассмотрим палиндромы длины n. Будем считать количество палиндромов так.
если N = abc...xyz, то прибавляем к ответу: 
(a - 1) * 9 * 9 * ... * 9 (до середины, так как это палиндром)
a * (b - 1) * 9 * ... * 9 (так же до середины)
... И так далее.
Cложность будет примерно O(n2).

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Algoprog MeetUp Contest #5
Автор abzaloid, 13 лет назад, По-русски

Всем привет!

Мы рады пригласить всех желающих на MeetUp Contest #5, который пройдет на сайте algoprog.kz
Авторами задач являемся я, Абзал Сереков, и Райхан Хасенова(raykhasenova). 

Тип - АСМ
Время начала - 11 сентября, 11:00 (алматинское время)
Длительность - 3 часа
Количество задач - 7

Задачи предлагаются как на русском, так и на английском языках.

Удачи!
Надеемся, что задачи вам понравятся!


P.S. Кто собирается участвовать в Гран-При Удмуртии, удачи! наш контест начнется на 2 часа раньше, можно и туда и сюда успеть! Как раз приготовить и "взболтать" мозг перед более серьезным соревнованием).

P.P.S. Не судите по окраске)

UPD: В 5ой задаче(Реккурентное соотношение) неправильные ответы в официальных тестах. Мы просим извинения! Надеемся вы поймете, все-таки это наш первый контест.

UPD: Ссылка на разбор появиться после окончания контеста.

UPD: Дорешивание задач доступно! В Архиве задач -> Том 1(последние в списке) 

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится