LINUX.ORG.RU
Форум — Development  

Помощь с олимпиадной задачей.

 , , ,


0

2

Доброго времени суток, Решаю такую задачку с регионального этапа. Кроме локальной пдфки, её описание находится по этой ссылке: task. Я нашел её разбор на ютьюбе и в текстовом виде. На ютьюбе - link

Из всех обьяснений(и текст и ютьюб) я не понимаю как определяется «некоторое число m», для двоичного поиска я полагаю это elements[size/2], но я не понимаю как дальше двигать это m и делать это «вещественное приближение». Для себя я решил это задачу через определение позиции каждой дроби через бинарный поиск внутри в каждой группы дробей одного делителя (поскольку дроби под одним делителем отсортированы). Но это не вещественное приближение. Был бы рад если бы кто то сбросил решение этой задачи на python или c++. Хотел бы для себя понять как всё таки это решать правильно. В интернете решений не нашел.

P.S. Текстовый разбор : ссылка (пдф файл большой, можно найти по оглавлению «Сортировка дробей»)

★

Последнее исправление: xionovermazes (всего исправлений: 2)
← Языки системного уровня
dmsetup message - вывод строки результата →
  1 2 →
Ответ на: комментарий от no-such-file

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

ya-betmen ★★★★★
()
Ответ на: комментарий от ya-betmen

Для рандомных дробей - да, но у тебя ограниченный набор

Какая разница? У тебя 2 массива [1, 10] и [3, 20]. Они отсортированы. Дроби получаются 1/3, 1/20, 10/3, 10/20, т.е. не отсортированы. Для перебора и подсчёта не важно отсортированы исходные массивы, или нет.

no-such-file ★★★★★
()

о, не сразу заметил что там еще и ограничение на n*q. Ну тогда все совсем просто. Сортируем оба массива и для каждого запроса делаем бинпоиск «количество дробей меньше заданной» по вещественному значению дроби (меньше 10**6). На каждой итерации бинпоиска проходим по всем знаменателям и находим, на какой позиции находится первый (или последний) подходящий числитель. Это можно сделать двумя указателями.

Итоговая сложность n*q*log(10**6) без выделения дополнительной памяти - должно пройти. Если не пройдет из-за точности, то авторов задачи следует скормить мелкозявру айронбага.

Lrrr ★★★★★
()
Последнее исправление: Lrrr (всего исправлений: 1)
Ответ на: комментарий от no-such-file

тут n упорядоченных в отдельности наборов дробей - каждый набор для каждого b - у Станкевича это используется в одном из решений (для уменьшения сложности поиска порядковой статистики)

в том и засада как не мерджа в явном виде n упорядоченных списков - быстро находить порядковую статистику

qulinxao3 ★★
()
Ответ на: комментарий от xionovermazes

?! это статистика с вашего же сайта

просто очевидно что https://github.com/python/cpython/blob/main/Lib/fractions.py#L203

явно много медленнее явного аппаратного деления

собственно Fractions изначально прикрутил что бы не заморачиваться с math.gcd для приведения к несократимому виду

qulinxao3 ★★
()
Ответ на: комментарий от no-such-file 
как минумум даёт большое ускорение упорядочение a - ибо тогда для каждого b можно бинпоиском определять количество меньшее probe 'm'


если же и b упорядоченны


то очевидно что если для b[i] разрез по позиции j в a - то для b[i+1] разрез не меньше j
qulinxao3 ★★
()
Последнее исправление: qulinxao3 (всего исправлений: 1)
Ответ на: комментарий от qulinxao3

А, т.е. не тупо считать, а внутри набора тоже искать дробь бинарно? Ну ок. Я бы сразу в лоб считал, а уже если не уложился по ограничениям, то кумекал бы.

no-such-file ★★★★★
()
Последнее исправление: no-such-file (всего исправлений: 1)
Ответ на: комментарий от xionovermazes

Можно не аллоцировать, а реализовать мега-йоба-mergesort, просто проходя по сортированному массиву, и выводить результат, если был запрос по данному индексу. Но тогда по времени вроде бы всё равно не пройдёт, n^2*log(n)

TheAnonymous ★★★★★
()
Ответ на: комментарий от Softwayer

там ещё более «прямое»

если упорядочив a И b (по отдельности)

представить квадратную табличку с числителями по x a0, a1 a2 a3 ... an и знаменателями по y b0 ....bN

представляющую собой все дроби

для любой(как в медианах медиан) клетки относительно нею в нулевом квадранте(с не меньшими а и не большими b) заведомо большие чем она а во втором( с не меньшим b и не большим a) заведомо меньшие

т.е для любого произвольного числа граница меньше большести будет некая кривая вдоль(типо паралельно но вкривь и вкось)главной диагонале т.е за n можно всегда разбить отсительно некоторой дроби

qulinxao3 ★★
()
  1 2 →
← Языки системного уровня
Development
dmsetup message - вывод строки результата →