Всем привет! Решил все сабтаски кроме последнего. Не получается придумать решение на фулл, есть идеи как решить ?
https://evaluator.hsin.hr/tasks/HONI212245izbori/
Объясни до чего сейчас дошёл, какое у тебя решение на все сабтаски до последнего? После этого я помогу тебе довести решение до фулла
1 лайк
Зафиксируем x как доминантный элемент. Создадим новый массив, где вхождения x-а 1, а все другое -1, мы свели задачу к найти количество отрезков с положительной суммой.
2 лайка
Отлично!
Выпишем условие того что x доминантный элемент на отрезке l…r:
cnt_{x, l, r} >(r - l + 1)/2
2 * cnt_{x, l, r} > (r - l + 1)
Давай распишем :
2 * cnt_{x, 1, r} - 2 * cnt_{x, 1, l - 1} > (r - (l - 1))
2 * cnt_{x, 1, r} - r > 2 * cnt_{x, 1, l - 1} - (l - 1)
Ну терерь давай заметим что есть новый массив вида : d_{x, i} = 2 * cnt_{x, 1, i} - i
Подсказка:
Теперь чтобы ответить на вопрос заданный в задаче для каждого x нужно посчитать кол-во пар i, j(i> j) таких что d_{x, i} > d_{x, j}. Если используем структуры данных вроде фенвика/ДО то на каждый x мы будем тратить O(n\log(n)) времени, суммарное время будет O(n^2\log n), это долго
Осталось придумать как можно для каждого x считать ответ за O(cnt_{x,1,n} * \log n), подумай как это сделать сам
2 лайка
Я ее решил за O(n log n) на каждый x как вы. Дальше нет идей как можно ускорить.
1 лайк
А сорян, думал у тебя квадрат, скинь код, там тл 3 секунды так что все должно заходить
1 лайк
блин, не правильно написал, сорри, можете перечитать коммент
2 лайка
Я в прошлом ответе в последнем предложении написал о том в какую сторону идти для ускорения до норм решения.
Попробуй придумать как на каждый x тратить время пропорциональное количеству элементов равных x (Хотя бы O((\text{кол-во x в массиве})^2)) и дальше уже с этой идеей идти дальше.
Прочитай мой прошлый ответ тебе и подумай как можно применить этот новый массив чтобы получить такое время.
Дополнительная подсказка :
Можно заметить что различных значений cnt_{x, 1, i} всего cnt_{x, 1, n}, и они все идут в возрастающем порядке.
1 лайк
Я решал эту задачу последние два дня, застрял. Объясните пожалуйста решение.
2 лайка
Мне было лень расписывать решение и я прост записал разбор. Когда в следующий раз будешь спрашивать можешь сразу условие задачи(или скрин условия) прикреплять к посту, а то приходится логиниться чтобы получить доступ к условию.
В разборе есть два решения одно за O(n \sqrt{n \log{n}}), другое за O(n \log{n})
upd :
Кстати можно было вместо структуры туп использовать массив и O(n * \sqrt{n\log(n)}) станет O(n * \sqrt{n}), как я понял задачу можно решить за O(n), эта задача(с большими огранами) оказывается уже была на всеросе(2012-2013 day2C), в инете можно разбор поискать.
Вот код решения за O(n\log(n)):
6 лайков