Доброго времени суток всем кто читает этот пост. Читая одну книжку по ДП столкнулся с очень сложной проблемой. Для того чтобы эффективно решать одну задачу, нужно за линейное время находить для массива A(N) L[i] — количество подряд идущих чисел до i-го которые больше или равны A[i]. Автор толком не показывает как это сделать, но говорит что стек поможет. Я думал-думал, ничего не выходит придумать. Помогите пожалуйста, объясните как же за линию такой массив насчитать и реально ли это вообще.

Пример

A = {3 1 2 4 5 3 4}

L = {0 1 0 0 0 2 0}

Для тех кто не очень возможно понял суть задачи — для каждого i-го числа мы встаем в позицию i-1 и пока это число >= a[i] то прибавляем 1 в L[i](но это за квадрат решение, а нам линия нужна).

Всем привет. Знакомый математик предложил решить такую интересную задачу.

Есть квадратная матрица N*N, каждую клетку можно покрасить в один из N цветов. Нужно найти количество матриц, таких что в каждой строке и каждом столбце все цвета разные.

Есть ли какие-то комбинаторные формулы для решения этой задачи? За какое адекватное время можно решить эту задачу? Мне в голову ничего не пришло кроме тупого перебора, но асимптотика ужасная.

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

Всем привет. Решил отправить одну задачу 82A - Double Cola. С решением проблем нет. Но падает на 8 тесте, причем не из-за того что ответ неправильный, а из-за формата вывода. Что я делаю нет так? 18847038

Привет CodeForces! Решаю простую задачу на реализацию кучи(приоритетной очереди). Условие здесь(страница 12, задача 5). Если коротко то мы должны обработать m запросов, каждый запрос может быть трех типов:

1 — извлечь максимальный элемент, вывести его и вывести позицию последнего элемента после просеивания

2 — добавить элемент, вывести его индекс после просеивания

3 — удалить элемент с индексом и вывести сам элемент

Если мы не можем выполнить какую-то операцию надо выводить -1. После выполнения запросов нужно вывести массив в котором хранится куча. До этого я решал такую же задачу где нужно было обрабатывать только запросы 1, 2 и она прошла. Добавил удаление произвольного элемента и не проходит. Я использую такой алгоритм удаления произвольного элемента: ставлю на место этого элемента последний элемент и выполняю sift_up(i) и sift_down(i), где i — индекс удаляемого элемента. Вроде должно работать, но на многих тестах WA. Вот код. Мне кажется алгоритм правильный и у меня есть подозрения что ошибка в коде. Помогите найти ошибку.

Привет Codeforces! Изучаю метод двух указателей. Решаю 279B - Books. Алгоритм понятен. Но когда доходит до реализации постоянно не учитываю какие-то случаи, криво как-то выходит. Подскажите что может быть не так в этом коде или скажите как лучше/правильнее писать метод двух указателей чтоб не было так криво(и кода много и учитывается не все)? 16825421

Всем привет. Решаю 339D - Xenia and Bit Operations Написал все вроде правильно, но почему-то по времени задача падает, хотя update сделал за O(N). Из-за чего мое решение превышает лимит времени? Помогите разобраться. Спасибо. 16749695

Всем привет. Решаю несложную геометрию. Решаю вот как: считываю xi, yi, составляю уравнение прямой которое проходит через x0, y0, xi, yi пользуясь формулой (x — x1) / (x2 — x1) = (y — y1) / (y2 — y1). И добавляю уравнение в множество (std::set). И потом просто вывожу размер множества. Коэффициенты прямой храню в виде пар чисел которые представляют несократимую дробь. К сожалению на 8 тесте получаю WA. Где может быть баг? 16591043