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

Автор Rodionno, история, 21 месяц назад, По-русски

Легенда: на прекрасной солнечной улице, где-то в Сочи, живут чиселки в своих уютных домиках. Конечно же они любят общаться между собой. А именно есть несколько групп друзей, в каждой из которых состоят одинаковые числа. Но к сожалению числа не довольны тем, что им приходиться проходить мимо домов незнакомых чиселок, чтобы попасть к своим друзьям. Вам поручили снести несколько домов и выселить числа которые там живут (сначала выселить, потом снести), так, чтобы все оставшиеся числа были довольны. Но т.к. выселение чисел и разрушение домов плохо влияют на имидж улицы, то вы решили уничтожить как можно меньше домов.

Задача: есть массив из целых чисел (все числа от 1 до n). Надо удалить как можно меньше чисел, чтобы не было такой тройки индексов, что 1 <= i < j < k <= n и a[i] == a[k] и a[i] != a[j]. 1 <= a[i] <= n. Ограничения на n могут быть наверное почти любыми, т.к. я не смог придумать решение быстрее чем за полином. Возможно это вообще np полная задача и её нельзя решить быстрее.

Вероятно если написать дп вида: маска какие числа есть и на какое число всё это заканчивается, то можно вероятно написать meet in the middle, т.к. если число встречается один раз, то оно нам никак точно не помешает, а иначе оно встречается хотя бы 2 раза, т.е. всего различных "интересных" чисел будет n / 2, а значит если n будет порядка 40, то маска будет до миллиона и решение будет работать.

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

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

Автор Rodionno, история, 21 месяц назад, По-русски

Есть интересная задача (скорее всего хорошо известная), но к сожалению все, у кого я спрашивал, не знают как делать её быстрее чем за O(n ^ 2). Помогите бедному скатившемуся синему.

Задача: есть массив из целых чисел, надо найти отрезок [l, r] где величина sum(l, r) * len(l, r) будет максимальна. sum(l, r)= a[l] + a[l + 1] + ... + a[r], len(l, r) = r — l + 1. 1 <= n <= 10^5, -10^9 <= a[i] <= 10^9.

Ограничения могут быть и менее строгими, если существует какое-то быстрое и интересное решение.

Возможно это решается чем-то вроде кхт. Можно попробовать взять отрезок с наибольшей суммой и расширить его. Можно свести задачу к точкам на плоскости, где надо выбрать прямоугольник с наибольшей площадью, при чём левый нижний и верхний правый угол должны быть в одной из данных точек.

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

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

Автор Rodionno, 22 месяца назад, По-русски

I came up with a simple task, but i can't solve it faster than O(n ^ 2). So I thought that maybe someone will help me with this.

Task: given an array of numbers, you need to find segment [l, r] where value sum(l, r) * len(l, r) will be the biggest for all pairs of l, r such as 1 <= l <= r <= n. sum(l, r) = a[l] + a[l + 1] + ... + a[r], len(l, r) = r - l + 1. 1 <= n <= 10^5, -10^9 <= a[i] <= 10^9

UPD: probably it can be solved with some kind of cht or maybe li chao tree. Also it's intresting to firstly find segment with biggest sum and then try to expand it.

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

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