Про дейкстру сначала правильно пишите, что отрицательные ребра его ломают. Потом, почему-то пишите:
Обратите внимание: наш алгоритм умеет работать с графами, содержащими ребра отрицательного веса.
Это тоже не правда. И еще даже тест приводите. Так что это не опечатка. То, что алгоритм на одном каком-то тесте отработал - не доказывает что она работает на всех возможных графах.
Про Флойда Урошелла тоже напутали:
Алгоритм Флойда-Уоршелла сравнивает все возможные пути через граф между каждой парой вершин.
Нет, алгоритм считает динамическое программирование d[k][i][j] - минимальное расстояние из вершины i в вершину j если промежуточные вершины могут быть 0..k-1. При чем, считается только последняя 2d матрица в этой 3d матрице.
У вас там дальше даже что-то вроде правильного объяснения дается, только формула не отображается целиком.
Разница между обходом дерева и обходом графа состоит в том, что в случае графа начальный узел выбирается произвольно. Это обуславливает необходимость отслеживания посещенных узлов:
Ну это же не правда вообще. Разница в том, что в дереве нет циклов и в любую вершину можно прийти только одним способом. Поэтому во время обхода из вершины есть ровно одно ребро к уже посещенному предку, а все остальные ребра ведут в новые вершины. Поэтому, кроме предка ничего запоминать не надо. В произвольном же графе могут быть разные пути в вершину, поэтому надо содержать множество уже посещенных вершин.
Еще раз, задачи утекают. Троечники еще могут зазубренный цикл написать, но если задача другая - нет. Поэтому задачи постоянно меняются. Когда-то давали задачи прям с прода, насколько это возможно. Потом скатились к немного искуственным задачам.
Аналогия с водительскими правами вам не понятна? Вы же не ругаетесь на инспектаров, что они заставляют вас ездить по тем дорогам, по которым вы ездить вообще никогда не собираетесь? Но вы при этом демонстрируете те же навыки, что вам понадоятся в настоящей езде. Так и тут, на этой, может и не самой классной, задаче кандидат показывает навыки, которые от него хотят увидеть - решает что-то не совсем тривиальное.
Или не удивляйтесь, что работник будет через пень-колоду вымучивать странные алгоритмы там, где троечник сложит 2 числа через bigInt.
Ваш аргумент звучит как: никогда не берите бегунов марафонцев в качестве курьеров. Там, где можно просто спокойно дойти до двери, он будет бежать! Нет же. Наличие сложных навыков не исключает наличие простых. И, продолжая аналогию, если у вас в городе иногда попадаются бродячие собаки, а всякие перцовые балончики запрещены из-за активистов, требовать от кандидата в курьеры способностьи хоть 20 метров до машины добежать - необходимость.
Какая же каша. У вас там то множества множеств, то множества элементов.
И потом, математики же не потому что вредные такие или от скуки понапридумывали всякое. Ваша "теория" неконсистента и противоречива, а значит и бесполезна на практике.
Во-первых, не всегда степени двойки. Во-вторых, скачет как ему вздумается. Для большего количества скобочек там еще более запутанная ситуация будет. Начало и конец, действительно более менее регулярны, потому что там весьма локальные изменения около центра происходят. Но потом они разрастаются и изменения происходят по всей строке.
Закономерность я описал выше, но ее не описать так просто в терминах битов. Там надо найти последний 0, где баланс левее положителен. Тут фигурирует что-то вроде popcnt от части числа.
Тут что-то вроде алгоритма Найораны можно получить, чтобы по одной битовой последовательности получать следующую. Но там весьма сложная операция: последний ноль, перед которым больше 0, чем 1, заменяем на 1, и в конце ставим все оставшиеся 1 в конец. Но уж закономерность по битам получать номер и обратно - это что-то совсем незаписываемое.
Если делать с длинной арифметикой, то тут будет O(n^2) по времени и O(n) по памяти. Ибо там умножения/деления на короткие и n сравнений длинных чисел. И, если уж делать с длинной арифметикой, то можно первую половину решения выкинуть. Там мы считаем, сколько надо поставить '(' сначала, и таким образом выбрасываем огромное количество последовательностей, чтобы количество оставшихся с данным префиксом было мелким. Но, если мы большие числа считаем, этого делать не надо. Тогда выбрасываем первый цикл, считаем вместо него число каталана (общее количество последовательностей из n пар). А потом остается основной цикл while (n > num_opening). Выбрасываем все Safe функции и там остается только IncreaseK и Replace.
Это вообще абсолютно другая ситуация. Были чуваки, кажется с визами, но у них что-то не так с другими документами. Если бы у них не было визы, то они бы просили убежище и писали бы, что им отказали в убежище, а не во въезде. Кроме визы надо еще как-то доказать цель поездки и все такое: вроде брони на гостиницу, письма с приглашением, билетов назад. Вот с этим у них оказались проблемы.
Потом, это 6 человек в день. Не 1000. С недостаточными документами, а не вообще без документов.
Не знаю, почему российсикие власти такую же атаку на эстонию не проводят. Может, хотят оставить тонкую щелку для выпуска пара, чтобы всякие недовольные могли свалить. Может, чьему-то бизнесу важно, чтобы граница работала и грузы ходили.
Гарантирую вам, как только там на границе появятся тысяча чуваков на велосипедах, границу закроют очень быстро.
Основаная идея даже проще вашего решения. Не надо искать закономерности и структуру последовательностей, это простой и универсальный принцып, как поиск в словаре. Вы знаете, сколько слов начинается на 'А'. Если их больше рано искомому k вы знаете, что ваше слово начинается на 'А' Иначе вы все эти строки вычеркиваете из расмотрения и пересчитваете k. Продолжаете с 'Б' и т.д. пока не найдете первую букву. Потом вы фиксируете ее и смотрите на вторую. Все что вам надо уметь, это считать сколько у вас бывает последовательностей с таким началом.
Дальше чуть-чуть логики и математики, чтобы научиться считать сколько последовательностей есть с кажым началом.
Вот если вы хотите сделать без длинной арифметики, да за O(N) с O(1) памяти (как у меня ниже, посмотрите, если интересно), вот там придется уже побольше математики нагородить, чтобы пересчитывать количество объектов быстро и без переполнения. Переполенение потому, что объектов-то экспоненциально много, и если вы попросите 10000000-ую последовательность из 100 скобок, то можно неаккуратно попробовать подсчитать, например, сколько их всего, а это ни в какое 64-битное число не влезет никак.
Вот сделал свое решение O(n) c O(1) памяти. БОльшая часть кода для счета без переполнения. Если входной номер большое число, то все придется считать в длинной арифметике и будет O(n^2), но кода может чуть поменьше. Моя F - это сколько последовательностей с n пар скобками с k открвающимеся в начале. Думаю, что-то подобное с пересчетом через домножение можно сделать и с вашими F.
код
// F(n,k) = Сколько последовательностей из n пар начинаются с k '('
// F(n,k) = F(n, k+1) + F(n-1, k-1)
// 1
// 1 1
// 2 2 1
// 5 5 3 1
// 14 14 9 4 1
//
// Это же числа каталана! Только отраженные.
// Вот формула
// F(n, k) = (2*n-k)!(k+1)/((n-k)!(n+1)!)
//
// Научимся пересчитывать внутри строки:
// k++ => mult by (k+2)*(n-k)/(2*n-k)/(k+1)
// k-- => mult by (2*n-k+1)*k/(k+1)/(n-k+1)
//
// А если мы заменяем последнюю '(' на ')':
// k-=2 --n => mult by /(k+1) /(n-k+1) *(n+1) *(k-1)
// Считаем a*n/d без переполнения (мы знаем, что влезет).
int64_t SafeMult(int64_t a, int n, int d) {
// a = (q*d + r)
// a / d * n = q*n + r*n/d
int64_t q = a / d;
return q * n + (a - q * d) * n / d;
}
// Проверка a*n/d < b без переполнения.
bool SafeCompare(int64_t a, int n, int d, int64_t b) {
// Проверяем a/d < k/n
// Сначала целые части
if (d == 0) return false;
if (n == 0) return 0 < b;
int64_t int_l = a / d;
int64_t int_r = b / n;
if (int_l < int_r) return true;
if (int_l > int_r) return false;
// Целые равны, проверим дробные
// a % d / d < b % n / n
// Числа маленькие, можно перемножить.
return (a % d) * n < (b % n) * d;
}
// Можно ли сдвинуться влево в строке не перескочив через t?
bool CanDecreaseK(int64_t count, int n, int k, int64_t t) {
int den = (k+1)*(n-k+1);
int num = (2*n-k+1)*k;
return SafeCompare(count, num, den, t);
}
// Замена последней '(' на ')'.
void Replace(int64_t &count, int &n, int &k) {
int den = (k+1)*(n-k+1);
int num = (n+1)*(k-1);
k -= 2;
n--;
count = SafeMult(count, num, den);
}
// Поставили '('.
void IncreaseK(int64_t &count, int n, int &k) {
int num = (k+2)*(n-k);
int den = (2*n-k)*(k+1);
++k;
count = SafeMult(count, num, den);
}
// Убрали последнюю '('.
void DecreaseK(int64_t &count, int n, int &k) {
int den = (k+1)*(n-k+1);
int num = (2*n-k+1)*k;
--k;
count = SafeMult(count, num, den);
}
// Построить k-ую (считая с 1) последовательность из n пар скобок.
string Generate(int n, int64_t k) {
string answer;
if (k == 1) {
for (int i = 0; i < n; ++i) {
answer += '(';
}
for (int i = 0; i < n; ++i) {
answer += ')';
}
return answer;
}
// Поддерживаем инваринант:
// answer содержит начало искомой строки.
// count - сколько всего строк с таким началом есть.
// Сколько '(' будет в начале?
// Начинаем с максимального количества.
int64_t count = 1;
int num_opening = n;
while (CanDecreaseK(count, n, num_opening, k)) {
DecreaseK(count, n, num_opening);
}
for (int i = 0; i < num_opening; ++i) {
answer += '(';
}
// Сейчас у нас минимальное количество '(', которых еще мало.
// Надо последнюю убрать.
// Все такие строки мы пропускаем, значит надо вычесть из номера.
k -= count;
// Заменяем '(' на ')'
answer.back() = ')';
Replace(count, n, num_opening);
while (n > num_opening) {
// Пробуем сначала поставить '('
IncreaseK(count, n, num_opening);
answer += '(';
// Если таких строк мало, надо их пропустить и ставить ')'
if (count < k) {
k -= count;
Replace(count, n, num_opening);
answer.back() = ')';
}
}
for (int i = 0; i < num_opening; ++i) {
answer += ')';
}
return answer;
}
Но при чем тут северная корея, если вы говорите про обязанность турагентства пасти туристов в России?
Это вы сказали, что вы много где ездили и не видели. Вот я вам и посоветовал посмотреть на страны, более близкие к россии по государственному строю.
Ну или попробуйте пригласить к себе какого-нибудь иностранца в россию.
То есть есть железобетонные доказательства что все это было сделано умышленно и именно государством?
Не все так однозначно! Всей правды мы не узнаем! Даже если это выглядит, крякает и плавает как утка, может быть это все-таки медведь! /s
Но даже если власти это не организовывали, прикрыть этот поток человечины могли бы запросто в один день. Но закрытие границы со стороны ЕС российские власти вполне устраивает.
так автобусы прямо к пограничному пункту ходили.. купил билет и..
Так их на подъезде останавливают и проверяют. Ладно, допустим первая волна у пункта в ленобласти сама образовалась. А какие автобусы оттуда ездят к пограничным пунктам в Карелии и Мурманской область? А мигранты массово добирались и туда.
И да, вас за рубежом хоть когда-нибудь хоть одно турагентство пасло? Сколько ни бывал - ни разу не было замечено..
Попробуйте в северную корею сгонять. Заметите. Россия - не далеко от нее ушла.
но как?
В смысле, как? Как прекратить свое умышленное и активное действие по гибридной атаке на соседнее государство? Тут не просят как-то прекратить действия третьих лиц, тут просят прекратить свои собственные действия.
Например, выслать указание консульствам перестать массово выдавать визы в специальном порядке под операцию по перевозке мигрантов. Перестать организовывать чартерные рейсы, отменить указ об организации перевозки их с аэропорта до границы. Отменить указание погранцам игнорировать это безобразие и даже способствовать ему.
То можно заметить, что все числа тут - это числа каталана, только выписаные по диагоналям и с кучей лишних 0. Четность n, k для не нулевых значений всегда будет совпадать и F(n,k) = Cat((n+k)/2, n-k). Если обозначить m=(n+k)/2, t =n-k, то F(n,k) = (m+t)!(m-t+1)/(t!(m+1)).
Для самого начала мы можем это число подсчитать за линию умножений и делений, а потом при постановке символа у нас m и t уменьшаются на 1 или остаются прежними. В любом случае, можно пересчитать новое число каталана просто домножив и поделив на что-то за константу.
Это все, конечно, если считать что у нас значения помещаются в целые числа. Тут нельзя ничего считать по модулю, потому что нам нужно точное значение количества последовательностей. Если считать с длинной арифметикой, тут числа порядка O(n) и решение будет за O(n^2) и O(n) памяти. Но если у вас считать с длинной арифметикой, то у вас будет O(n^3) предподсчет и само решение за O(n^2 log n).
Но минус у этого решения тоже есть: нельзя все считать в маленьких числах, даже если искомый номер последовательности в целые числа влезает. Но в этом случае можно просто считать все F через сложения, не считая левый нижний угол, ибо там слишком большие числа будут.
Практически все такие комбинаторные задачи на k-ый лексикографический объект решаются примерно одинаково: вам надо научиться считать, сколько таких объектов есть с заданным перфиксом, а потом перебирать префикс по одному символу. Тут не надо даже бинарного поиска.
Все последовательности начинаются или с '(' или с ')'. Мы можем посчитать, сколько их и тех и других. Если первых хотя бы k - то мы знаем, что k-ая последовательность будет среди них, и зафиксировать первый символ как '('. Вообще тут все пока очеивдно, ибо вторых 0, ведь все последовательности начинаются с открывающей скобки. Но дальше интереснее: зафиксировали мы первый символ. Есть последовательности в которых второй символ '(' или ')', подсчитали каждые, сразу поняли какой символ будет вторым, ведь мы знаем какая по счету из них нам нужна. Зафиксировали второй символ. И т.д.
Назовем балансом разность количества '(' и ')'. В правильной скобочной последовательности баланс в каждом перфиксе не отрицателен а в конце 0.
Вот есть у вас какой-то префикс. Нам не важно, что именно в нем, от него нам важен лишь баланс. Именно это определяет, какие скобочки можно ставить дальше. Пусть его баланс k. Осталость n символов дополнить. Надо научиться считать сколько последовательностей можно сюда дописать. Это динамика: F(n,k) = F(n-1,k-1) + F(n-1, k+1). И база F(n, -1) = 0, F(0,0) = 1, F(0,k) = 0. Опять же, все искомые последовательности начинаются или с '(' или с ')'. Считаем сколько каждых, для чего новый символ добавляем в перфикс. Вообще, это F можно интерпретировать как количество правильных последовательностей длиной n+k, начинающихся с k '('. Почти то же что и у вас.
Вот уже решение с O(n^2) предподсчетом работающее за O(n). Ну, и памяти тоже O(n^2) надо на таблицу.
Но его можно соптимизировать, кажется до линии, если научиться считать F(n, k) через комбинаторику как-то быстрее, но тут надо выписать числа и помедетировать над ними.
Жил в Финляндии пока был в аспирантуре в 2010-2017 годах (перехал по работе, так бы и остался там). Могу практически все в статье подтвердить. \
Все говорят по английски, потому что там фильмы не переозвучивают, только добавляют субтитры. Переозвучивают только совсем уж десткие мультики. Поэтому, кастати, тут и в кино можно ходить не зная финский и телевизор смотреть.
Интересный факт - тут почти в каждом доме есть сауна. Даже в многоквартирных. Обычно она в подвале и есть расписание, у каждой квартиры есть слот раз в неделю.
Если вы без семьи, то Финляндия не лучшее место по заработку денег из-за налогов и не очень больших зарплат. Но финляндия - это не про зарабатывание всех денег мира. Это рай для выращивания детей.
Я думаю сейчас там все напряженнее, чем когда я там жил, но в мое время на главных страницах газет можно было встретить новости о том, что в центральном парке Хельсинки какая-то птичка вывела птенцов. С фотографиями и умилением. И просьбой не беспокоить птичку. Не случайно финляндия много лет подряд признается самой счастливой страной, если в стране такие новости.
Не согласен с автором по поводу пробок. В час пик кольцо 1 вокруг хельсинки ползло с черпашей скоростью, вместо обычных 90 км/ч. И поездка, которая обычно занимает 20 минут, будет длиться все 60. Но я никогда не жил в городах миллионниках, поэтому мое понятие о пробках может сильно отличаться от того, что имел в виду автор. Но эти пробки не мешают автобусам и такси, ибо у них отдельная полоса. И час рассасываются довольно быстро, достаточно на час позже свалить с работы и никаких проблем не будет.
С дискриминацией не сталкивался ни разу.
Местные полицейские: прям смотришь на них и чувствуешь безопасность. А не российсикие менты, о которых единственная мысль "только бы не привязался". Один раз украли велосипед - можно отправить заявление полностью через интернет. Один раз поцарапал машину о стену, страховая выплатила почти всю стоимость моего подерженного автомобиля без вопросов и волокиты. И с ней тоже все через интернет можно было сделать.
Из минусов можно сказать, что финляндия в целом провинциальная. Это маленькая страна и даже весь большой Хельсинки меньше миллиона человек. Это конечно откладывает некоторый отпечаток на поведение финов: например, они никуда не торопятся, а если из-за какого-нибудь ремонта в ОТ образуется толкучка, они даже не понимают, что надо отойти от двери и готовиться к выходу заранее. Тут, конечно, есть и клубы и всякие группы даже выступают и всякие комик-коны устраивают, но кому-то может будет не хватать движухи.
Финский - ужасен. Я его так выучить и не смог. Дополнительная проблема была в том, что все местные сразу переключаются на английский, как только слышат ломанный финский. Так что для практики надо специально заводить друзей/коллег и просить их говорить с вами по фински.
Еще минус - климат. Это северная страна. Совсем не Калифорния. Помню как один студент из африки грязно ругался и недоумевал, какого хрена ночь на дворе в 3 часа дня.
Все плюсы и минусы, конечно, субъективны, но на мой взгляд минусы тут ничтожны.
Вы хоть представляете, как сложно негражданину въехать в россию (из дальнего зарубежья, но эти мигранты были не из стран с безвизом в россии)? У меня как-то друг из японии хотел туристом въехать. Я так натрахался с бюрократией и всякими миграционными службами. Въехать же для транзита - вообще никто не даст. Чуть проще если въезжать с помощью большого турристического агенства. Но агенства должны этих туристов пасти.
И вообще, еще на подъезде к границе проверяют документы, и каких-то левых туристов сразу скрутят. Вдруг шпионы какие-нибудь? Вы вообще знаете, что вся приграничная зона в РФ - особая?
И тут тысячи странных людей в день как-то въезжают в россию и добираются до границы. Без государственной помощи такой поток человечины невозможен.
От властей РФ ожидают прекращение умышленного злоупотребления гуманистическими законами ЕС.
Про дейкстру сначала правильно пишите, что отрицательные ребра его ломают. Потом, почему-то пишите:
Это тоже не правда. И еще даже тест приводите. Так что это не опечатка. То, что алгоритм на одном каком-то тесте отработал - не доказывает что она работает на всех возможных графах.
Про Флойда Урошелла тоже напутали:
Нет, алгоритм считает динамическое программирование d[k][i][j] - минимальное расстояние из вершины i в вершину j если промежуточные вершины могут быть 0..k-1. При чем, считается только последняя 2d матрица в этой 3d матрице.
У вас там дальше даже что-то вроде правильного объяснения дается, только формула не отображается целиком.
Ну это же не правда вообще. Разница в том, что в дереве нет циклов и в любую вершину можно прийти только одним способом. Поэтому во время обхода из вершины есть ровно одно ребро к уже посещенному предку, а все остальные ребра ведут в новые вершины. Поэтому, кроме предка ничего запоминать не надо. В произвольном же графе могут быть разные пути в вершину, поэтому надо содержать множество уже посещенных вершин.
А почему тогда 2+3=5 а не {2, 3}?
Еще раз, задачи утекают. Троечники еще могут зазубренный цикл написать, но если задача другая - нет. Поэтому задачи постоянно меняются. Когда-то давали задачи прям с прода, насколько это возможно. Потом скатились к немного искуственным задачам.
Аналогия с водительскими правами вам не понятна? Вы же не ругаетесь на инспектаров, что они заставляют вас ездить по тем дорогам, по которым вы ездить вообще никогда не собираетесь? Но вы при этом демонстрируете те же навыки, что вам понадоятся в настоящей езде. Так и тут, на этой, может и не самой классной, задаче кандидат показывает навыки, которые от него хотят увидеть - решает что-то не совсем тривиальное.
Ваш аргумент звучит как: никогда не берите бегунов марафонцев в качестве курьеров. Там, где можно просто спокойно дойти до двери, он будет бежать! Нет же. Наличие сложных навыков не исключает наличие простых. И, продолжая аналогию, если у вас в городе иногда попадаются бродячие собаки, а всякие перцовые балончики запрещены из-за активистов, требовать от кандидата в курьеры способностьи хоть 20 метров до машины добежать - необходимость.
Не всегда. Во множестве натуральных чисел лежат натуральные числа.
Какая же каша. У вас там то множества множеств, то множества элементов.
И потом, математики же не потому что вредные такие или от скуки понапридумывали всякое. Ваша "теория" неконсистента и противоречива, а значит и бесполезна на практике.
Это только для маленьких чисел. Вот вам "приращения" для всех скобочных последовательностей длины 10:
Скрытый текст
Во-первых, не всегда степени двойки. Во-вторых, скачет как ему вздумается. Для большего количества скобочек там еще более запутанная ситуация будет. Начало и конец, действительно более менее регулярны, потому что там весьма локальные изменения около центра происходят. Но потом они разрастаются и изменения происходят по всей строке.
Закономерность я описал выше, но ее не описать так просто в терминах битов. Там надо найти последний 0, где баланс левее положителен. Тут фигурирует что-то вроде popcnt от части числа.
Тут что-то вроде алгоритма Найораны можно получить, чтобы по одной битовой последовательности получать следующую. Но там весьма сложная операция: последний ноль, перед которым больше 0, чем 1, заменяем на 1, и в конце ставим все оставшиеся 1 в конец. Но уж закономерность по битам получать номер и обратно - это что-то совсем незаписываемое.
Если делать с длинной арифметикой, то тут будет O(n^2) по времени и O(n) по памяти. Ибо там умножения/деления на короткие и n сравнений длинных чисел. И, если уж делать с длинной арифметикой, то можно первую половину решения выкинуть. Там мы считаем, сколько надо поставить '(' сначала, и таким образом выбрасываем огромное количество последовательностей, чтобы количество оставшихся с данным префиксом было мелким. Но, если мы большие числа считаем, этого делать не надо. Тогда выбрасываем первый цикл, считаем вместо него число каталана (общее количество последовательностей из n пар). А потом остается основной цикл
while (n > num_opening). Выбрасываем все Safe функции и там остается только IncreaseK и Replace.Обратите внимание, сирии и юар в списке стран для которых это спец-предложение действует - нет.
Это вообще абсолютно другая ситуация. Были чуваки, кажется с визами, но у них что-то не так с другими документами. Если бы у них не было визы, то они бы просили убежище и писали бы, что им отказали в убежище, а не во въезде. Кроме визы надо еще как-то доказать цель поездки и все такое: вроде брони на гостиницу, письма с приглашением, билетов назад. Вот с этим у них оказались проблемы.
Потом, это 6 человек в день. Не 1000. С недостаточными документами, а не вообще без документов.
Не знаю, почему российсикие власти такую же атаку на эстонию не проводят. Может, хотят оставить тонкую щелку для выпуска пара, чтобы всякие недовольные могли свалить. Может, чьему-то бизнесу важно, чтобы граница работала и грузы ходили.
Гарантирую вам, как только там на границе появятся тысяча чуваков на велосипедах, границу закроют очень быстро.
Основаная идея даже проще вашего решения. Не надо искать закономерности и структуру последовательностей, это простой и универсальный принцып, как поиск в словаре. Вы знаете, сколько слов начинается на 'А'. Если их больше рано искомому k вы знаете, что ваше слово начинается на 'А' Иначе вы все эти строки вычеркиваете из расмотрения и пересчитваете k. Продолжаете с 'Б' и т.д. пока не найдете первую букву. Потом вы фиксируете ее и смотрите на вторую. Все что вам надо уметь, это считать сколько у вас бывает последовательностей с таким началом.
Дальше чуть-чуть логики и математики, чтобы научиться считать сколько последовательностей есть с кажым началом.
Вот если вы хотите сделать без длинной арифметики, да за O(N) с O(1) памяти (как у меня ниже, посмотрите, если интересно), вот там придется уже побольше математики нагородить, чтобы пересчитывать количество объектов быстро и без переполнения. Переполенение потому, что объектов-то экспоненциально много, и если вы попросите 10000000-ую последовательность из 100 скобок, то можно неаккуратно попробовать подсчитать, например, сколько их всего, а это ни в какое 64-битное число не влезет никак.
Вот сделал свое решение O(n) c O(1) памяти. БОльшая часть кода для счета без переполнения. Если входной номер большое число, то все придется считать в длинной арифметике и будет O(n^2), но кода может чуть поменьше. Моя F - это сколько последовательностей с n пар скобками с k открвающимеся в начале. Думаю, что-то подобное с пересчетом через домножение можно сделать и с вашими F.
код
Это вы сказали, что вы много где ездили и не видели. Вот я вам и посоветовал посмотреть на страны, более близкие к россии по государственному строю.
Ну или попробуйте пригласить к себе какого-нибудь иностранца в россию.
Не все так однозначно! Всей правды мы не узнаем! Даже если это выглядит, крякает и плавает как утка, может быть это все-таки медведь! /s
Но даже если власти это не организовывали, прикрыть этот поток человечины могли бы запросто в один день. Но закрытие границы со стороны ЕС российские власти вполне устраивает.
Не имею доступа к секретным указам.
Так их на подъезде останавливают и проверяют. Ладно, допустим первая волна у пункта в ленобласти сама образовалась. А какие автобусы оттуда ездят к пограничным пунктам в Карелии и Мурманской область? А мигранты массово добирались и туда.
Попробуйте в северную корею сгонять. Заметите. Россия - не далеко от нее ушла.
В смысле, как? Как прекратить свое умышленное и активное действие по гибридной атаке на соседнее государство? Тут не просят как-то прекратить действия третьих лиц, тут просят прекратить свои собственные действия.
Например, выслать указание консульствам перестать массово выдавать визы в специальном порядке под операцию по перевозке мигрантов. Перестать организовывать чартерные рейсы, отменить указ об организации перевозки их с аэропорта до границы. Отменить указание погранцам игнорировать это безобразие и даже способствовать ему.
Добавлю про оптимизацию до O(n). Если выписать F:
То можно заметить, что все числа тут - это числа каталана, только выписаные по диагоналям и с кучей лишних 0. Четность n, k для не нулевых значений всегда будет совпадать и F(n,k) = Cat((n+k)/2, n-k). Если обозначить m=(n+k)/2, t =n-k, то F(n,k) = (m+t)!(m-t+1)/(t!(m+1)).
Для самого начала мы можем это число подсчитать за линию умножений и делений, а потом при постановке символа у нас m и t уменьшаются на 1 или остаются прежними. В любом случае, можно пересчитать новое число каталана просто домножив и поделив на что-то за константу.
Это все, конечно, если считать что у нас значения помещаются в целые числа. Тут нельзя ничего считать по модулю, потому что нам нужно точное значение количества последовательностей. Если считать с длинной арифметикой, тут числа порядка O(n) и решение будет за O(n^2) и O(n) памяти. Но если у вас считать с длинной арифметикой, то у вас будет O(n^3) предподсчет и само решение за O(n^2 log n).
Но минус у этого решения тоже есть: нельзя все считать в маленьких числах, даже если искомый номер последовательности в целые числа влезает. Но в этом случае можно просто считать все F через сложения, не считая левый нижний угол, ибо там слишком большие числа будут.
Практически все такие комбинаторные задачи на k-ый лексикографический объект решаются примерно одинаково: вам надо научиться считать, сколько таких объектов есть с заданным перфиксом, а потом перебирать префикс по одному символу. Тут не надо даже бинарного поиска.
Все последовательности начинаются или с '(' или с ')'. Мы можем посчитать, сколько их и тех и других. Если первых хотя бы k - то мы знаем, что k-ая последовательность будет среди них, и зафиксировать первый символ как '('. Вообще тут все пока очеивдно, ибо вторых 0, ведь все последовательности начинаются с открывающей скобки. Но дальше интереснее: зафиксировали мы первый символ. Есть последовательности в которых второй символ '(' или ')', подсчитали каждые, сразу поняли какой символ будет вторым, ведь мы знаем какая по счету из них нам нужна. Зафиксировали второй символ. И т.д.
Назовем балансом разность количества '(' и ')'. В правильной скобочной последовательности баланс в каждом перфиксе не отрицателен а в конце 0.
Вот есть у вас какой-то префикс. Нам не важно, что именно в нем, от него нам важен лишь баланс. Именно это определяет, какие скобочки можно ставить дальше. Пусть его баланс k. Осталость n символов дополнить. Надо научиться считать сколько последовательностей можно сюда дописать. Это динамика: F(n,k) = F(n-1,k-1) + F(n-1, k+1). И база F(n, -1) = 0, F(0,0) = 1, F(0,k) = 0. Опять же, все искомые последовательности начинаются или с '(' или с ')'. Считаем сколько каждых, для чего новый символ добавляем в перфикс. Вообще, это F можно интерпретировать как количество правильных последовательностей длиной n+k, начинающихся с k '('. Почти то же что и у вас.
Вот уже решение с O(n^2) предподсчетом работающее за O(n). Ну, и памяти тоже O(n^2) надо на таблицу.
Но его можно соптимизировать, кажется до линии, если научиться считать F(n, k) через комбинаторику как-то быстрее, но тут надо выписать числа и помедетировать над ними.
Вся молочка в Финляндии - высочайшего качества. Незря в лучшие времена многие ездили в финку из питера/карелии и закупались там, в том числе, и сыром.
Жил в Финляндии пока был в аспирантуре в 2010-2017 годах (перехал по работе, так бы и остался там). Могу практически все в статье подтвердить. \
Все говорят по английски, потому что там фильмы не переозвучивают, только добавляют субтитры. Переозвучивают только совсем уж десткие мультики. Поэтому, кастати, тут и в кино можно ходить не зная финский и телевизор смотреть.
Интересный факт - тут почти в каждом доме есть сауна. Даже в многоквартирных. Обычно она в подвале и есть расписание, у каждой квартиры есть слот раз в неделю.
Если вы без семьи, то Финляндия не лучшее место по заработку денег из-за налогов и не очень больших зарплат. Но финляндия - это не про зарабатывание всех денег мира. Это рай для выращивания детей.
Я думаю сейчас там все напряженнее, чем когда я там жил, но в мое время на главных страницах газет можно было встретить новости о том, что в центральном парке Хельсинки какая-то птичка вывела птенцов. С фотографиями и умилением. И просьбой не беспокоить птичку. Не случайно финляндия много лет подряд признается самой счастливой страной, если в стране такие новости.
Не согласен с автором по поводу пробок. В час пик кольцо 1 вокруг хельсинки ползло с черпашей скоростью, вместо обычных 90 км/ч. И поездка, которая обычно занимает 20 минут, будет длиться все 60. Но я никогда не жил в городах миллионниках, поэтому мое понятие о пробках может сильно отличаться от того, что имел в виду автор. Но эти пробки не мешают автобусам и такси, ибо у них отдельная полоса. И час рассасываются довольно быстро, достаточно на час позже свалить с работы и никаких проблем не будет.
С дискриминацией не сталкивался ни разу.
Местные полицейские: прям смотришь на них и чувствуешь безопасность. А не российсикие менты, о которых единственная мысль "только бы не привязался". Один раз украли велосипед - можно отправить заявление полностью через интернет. Один раз поцарапал машину о стену, страховая выплатила почти всю стоимость моего подерженного автомобиля без вопросов и волокиты. И с ней тоже все через интернет можно было сделать.
Из минусов можно сказать, что финляндия в целом провинциальная. Это маленькая страна и даже весь большой Хельсинки меньше миллиона человек. Это конечно откладывает некоторый отпечаток на поведение финов: например, они никуда не торопятся, а если из-за какого-нибудь ремонта в ОТ образуется толкучка, они даже не понимают, что надо отойти от двери и готовиться к выходу заранее. Тут, конечно, есть и клубы и всякие группы даже выступают и всякие комик-коны устраивают, но кому-то может будет не хватать движухи.
Финский - ужасен. Я его так выучить и не смог. Дополнительная проблема была в том, что все местные сразу переключаются на английский, как только слышат ломанный финский. Так что для практики надо специально заводить друзей/коллег и просить их говорить с вами по фински.
Еще минус - климат. Это северная страна. Совсем не Калифорния. Помню как один студент из африки грязно ругался и недоумевал, какого хрена ночь на дворе в 3 часа дня.
Все плюсы и минусы, конечно, субъективны, но на мой взгляд минусы тут ничтожны.
Вы хоть представляете, как сложно негражданину въехать в россию (из дальнего зарубежья, но эти мигранты были не из стран с безвизом в россии)? У меня как-то друг из японии хотел туристом въехать. Я так натрахался с бюрократией и всякими миграционными службами. Въехать же для транзита - вообще никто не даст. Чуть проще если въезжать с помощью большого турристического агенства. Но агенства должны этих туристов пасти.
И вообще, еще на подъезде к границе проверяют документы, и каких-то левых туристов сразу скрутят. Вдруг шпионы какие-нибудь? Вы вообще знаете, что вся приграничная зона в РФ - особая?
И тут тысячи странных людей в день как-то въезжают в россию и добираются до границы. Без государственной помощи такой поток человечины невозможен.
От властей РФ ожидают прекращение умышленного злоупотребления гуманистическими законами ЕС.