Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/04687.jsonl.gz/6

Первый тред математиков и программистов-теоретиков. Здесь мы проверяем свои навыки аналитического мышления и мифической необходимой теоретической базы, оставляем интересные задачи или задачи, с которыми не справились, возможно, учим новое. Курису явно предпочитает эксперименты, а общество — полезную практику, однако здесь у всех есть свобода заниматься абстрактными и малополезными вещами. Просьба писать по теме.
>>151083Сможешь организовать стек с элементом в 4 байта?
>>151084Да, но это будет просто массив с очень неэффективными методами вставки. зато вписывающийся в пространственные ограничения. Но сложность вставки будет не хуже O(1000).
>>151085Окей. Мне интересно. Сейчас писать не советую, потому что я смогу прочитать только утром. У меня у самого есть идея, я ей поделюсь завтра.
>>151087Так тут писать даже нечего.естьint stack[100000] = {-1};у нас есть индекс последнего элемента (изначально это 0)если при PUSH A B у нас A == 1, то просто stack[index++] = Bесли A > 1, сдвигаем все элементы вправо начиная с index — A и по index, а затем stack[index — A] = BС POP A всё понятно. Но наверное это будет слишком медленно, раз, судя по всему, ты не воспринял это как верное решение сразу?
int stack[100000] = {-1};
>>151088>С POP A всё понятно.Вот как раз с POP A ничего не понятно. Если ты добавил элемент в index-4, а потом в index-2, то первый добавленный элемент будет уже в index-5. А если сначала в index-4, а потом в index-6, то первый элемент останется в index-4. Поэтому ты и не знаешь, где последний элемент одного из стеков находится. К тому же, эта программа не сможет обработать два последовательных запроса POP на один и тот же стек.СПОЙЛЕРМоя идея такая: в один массив всех элементов пихаю структуру из числа и индекса предыдущего элемента стека. Ну и ещё держу массив индексов последних элементов стеков. Получается 1000 связных списков, сваленных в один массив. Но суть в том, что для того, чтобы хранить число от 0 до 10^9, нужен минимум 30 бит памяти, а чтобы хранить индекс (от 0 до 100000) требуется минимум 17 бит. Поэтому для числа я завожу в структуре unsigned int, а для индекса предыдущего — short int, но при этом, 17-ый бит индекса храню в 31-ом бите числа, а в самом числе 31-ый бит игнорирую. Таким образом, один элемент у меня занимает 6 байт памяти.
>>151079Ну лан, срез срезов интов. Новый стек = добавляем к срезу срез. Существующий срез — ищем нужный по индексу. Аппенд = пуш, v =s[len(s)] и s = s[0:len(s)] = попЭто самое лоу лвл которое я могу придумать, если соблюдать одну вещь — стеки в проге должны быть именно нормальными стеками, а не какими то маняврированиями или многоходовочками чтобы сохранить память.>>151088> сдвигаем все элементы вправоRipМассово двигать элементы в срезе/массиве это плохо, очень плохо.
>>151095Динамическая структура данных. К тому же, на эту задачу ограничение языков: только С, С++ и Pascal. На других решения может тебе не быть. Мне пришлось поменять компилятор на Visual C++, потому что g++ зажирается и отдельно инициализирует себе 100 килобайт, из-из-иа чего моё решение не проходило по памяти.
>>151098Моё решение не сработало. Я пытался выделить на элемент в структуре 48 бит (6 байт), но это слишком неоптимально. Нужно ровно 47. Сейчас думаю, как бы это организовать.
>>151098вот поетому я и говорю, давайте нормальные хоть скольк-т реалистичные задачки, байтоебство на 100кб или ограничение в 750кб это нереалистично в 95% случаев, заказчику дешевле планку или диск купить, чем платить гребцам, чтобы они тужились над такими вещами или тратили время на переключение блядь компилятора ради 100кбкароч я понял что мне надо чет самому делоть, так сказатбесть сервак, который в каждый момент времени может обрабатывать 1 мемес, или не обрабатывать мем вообщеесть школьники, которые срут на сервак мемчики (тоесть заявки, если научно так сказать), и серваку нужно мемы обработатьобработка мема = загрузка сервака на 100% на какое-то время, которое называется временем обслуживания заявки.заявки скидываются в 1 очередь с дисциплиной fifoвходной поток заявок пуассоновский с интенсивностью λ, поток обслуживания тоже пуассоновский с интенсивностью μ. потоки стационарны, т.е. те 2 интенсивности не меняются (что конечно же нереалистично но неважно)ваша задача — имитационно смоделить такую штуку и найти коеф.загрузки такой системы, среднюю длинну очереди, среднее время нахождения в системе (ожидание+обслуживание), вероятность того что на момент прихода мемеса в очереди будет n задачимитационно = время дискретная величина, есть квантпо научному так скозатб эта штука(тоесть система) по классификации кендалла М/М/1это очень существенно упрощенная 1-я лаба из предмета в шараге, так ее закодить просточуть сложнее = серваков может быть несколько, больше 1-го, тогда они берут из общей очередисделать несколько дисциплин, не только fifo/lifoпоток обслуживания может быть не пуассоновским>ты хочешь чтобы мы делали за тебя лабыданет, я её уже давно сдал>нипрактичнанет, очень даже практична, и не только в ит>имитационное моделирование говно говнанет, юзается когда моделить дорого/долгоесли хочешь не имитационное, каждый сервак = тред, система многопоточная, слушоешь по порту, с другой проги шлешь заявки, так даже интереснее будет, кек
Как поменять количество бит в байте?
>>151116https://www.percona.com/live/17/sites/default/files/the-essential-guide-to-queueing-theory.pdf
Спасибо. Вопрос снят.
>>151110>750кб это нереалистично в 95% случаевА если запросов не сто тысяч, а несколько миллиардов? И тогда 750кб плавно перерастают в 10-15гб. А это уже вполне реальные ограничения. Я думаю, что эта задача практична хотя бы потому что сейчас идёт эпоха BigData и поэтому работать с ограниченными ресурсами приходится нередко.
Так её надо как решить? Смоделировать какое-то большое количество запросов или теми формулами всё? Если формулами, то это довольно скучно получается. А если моделировать, я смогу даже не один сервер реализовать, а сеть.
>>151141Имитационно моделировать конечно же, я там так и написал.Да, заявки офк, тысячу-две, но это неважно в принципе.Формулы для понимания ситуации и ответов на вопросы, ну и для распределений конечно же.
>>151152Кстати говоря, "практические твои значения с формулами должны совпадать
>>151154А если я скажу, что запрос всегда идёт в самый быстрый доступный свободный сервер, это будет оптимально?
>>151157в задаче интенсивность потока обслуживания на всех серверах одинаковая, поэтому если несколько серваков свободны, то заявку обслуживает рандомный, не имеет значения какой.
Короче, что-то сделяль.https://ideone.com/zw49SmПорядок ввода таков: количество серверов, скорость выхода запросов, скорости обработки одного запроса серверами, дальше идут m-1 строк, на i-той список серверов, в которые запрос может попасть из сервера i. M-тый сервер замыкающий. На последней строке количество запросов. Я не уверен в правильности решения, но и проверять не на чем.
>>151167Больше ничего не сделаю, потому что в этой теме не разбираюсь.
>>151052Так вот. Я под катом оставлю решение.РазвернутьПросто рандомно буквы выводите
Ребят, привет. Такая вам задача:Есть 2 <= n <= 100000 отрезков, i-тый начинается в x_i и заканчивается в y_i. Как минимум n-1 из них имеют общую точку (может быть, и не одну). Выбрать из этих n отрезков n-1 так, чтобы их общая часть имела максимальную длину.Если задача для вас слишком простая, скажите. Я стану кидать сложнее, мне не трудно.Если скучная — скиньте задачу, которую считаете интересной.
>>151584>Ребят, привет.Привет, внучок!
>>151584Все отрезки лежат на одной прямой?
>>151596Да
>>151584Секунду, нам нужно выбрать n-1 отрезков из n. И известно что n-1 из n имеет общую точку. Но разве это не значит что мы должны тупо взять все отрезки кроме одного единственного который не имеет никаких общих точек? И из этих n-1 общая длина и будет максимальной среди n-1
>>152163Последний может иметь общие точки. Но не со всеми. Нужно его быстро найти.
Ещё одна задачка: у вас на доске написан набор чисел. Они могут быть отрицательными и неотрицательными. Дальше идёт такая игра: за одно действие вы можете стереть любые два числа на доске и написать на той же доске их произведение. Также можно в любой момент просто стереть одно число, но не более одного раза. В любом случае, в какой-то момент на доске останется одно число. Нужно его максимизировать. Опишите свой алгоритм действий.Если хотите, объясню решение последней задачи.
>>151584вот в общем.https://pastebin.com/t0tFnArfна питоне потому что для мелких вещей проще.
>>154099Опиши значение переменных, пожалуйста.
>>154150solution возвращает индекс отрезка, у которого количество отрезков с общими с ним точками меньше чем n — 1target и otherTarget — потенциальные кандидатыcommon — текущее значение общей части
>>154152Жадное решение, но вполне вероятно, что сработает. У меня было другое. Тип p[i] — общий отрезок отрезков от 0-го до i-того, а s[i] — от i-того до последнего. Короче, для каждой i мы проверяем общие точки p[i-1] и s[i+1], то есть как бы проверяем отрезок, если из него выкинуть i-тый. Но если понять, что у «лишнего» максимальный a_i или минимальный b_i, задача становится ещё проще.
>>154157вроде должно сработать, ответы полностью совпадают с реализацией в лоб тупым и надежным перебором O(n^2).100000 отрезков проходит за 0.2 секунды, хотя я не знаю какие ограничения, они не уточнялись.понятно.
>>154161Вообще, когда линейный алгоритм работает с такой скоростью, это печально. 500000 уже едва пройдёт в таймлимит. Учитывая, что разработчики могут линейному алгоритму и 10 миллионов скармливать, получается не по-олимпиадному как-то. Очень медленный язык. Поэтому когда на таких тяжеловесных задачах стоит длинная арифметика, я плачу кровью, потому что джаву я не учил, а в крестах её нет.
>>154179не понял, проблема в языке или самом алгоритме. или и там и там.
>>154180Алгоритм нормальный, язык плохой.
>>154184ну питон всё же не очень предназначен для суперскоростных олимпиадных штук, увы.
Вот вам классика:
>>155892Как бы вы её решили? Желательно за O(n).
>>155893Второй левел — решить эту задачу в двумерном варианте.
>>155893никак, сосу, у тебя ничего по проще нет, 2+2 = ? или типа того ?
>>155896Каков шанс того, что при броске двадцатигранного кубика выпадет число, которое делится на 3?
Есть ли вообще смысл поддерживать этот тред? Не хотелось бы на него забивать, но и распинаться перед стеной тоже не хочется.
>>158898Нет смысла говорить со стенкой, но и удалять/убивать тред смысла нет. Пости задачи, которые считаешь интересными, если кому-то из нас будет интересно, начнется дискуссия, как начиналась и тогда.Хотя сделаю небольшую ремарочку на то, что сейчас учебный год, а, значит, у некоторых посетителей треда времени и желания думать может быть меньше, это уж так сложилось, ничего не поделаешь.
Вот теперь такая задача: у вас есть город, который можно представить в виде таблицы NxM, каждая ячейка таблицы — жилой дом. У каждого дома есть стоимость — целочисленное значение, чем дом дороже, тем больше это число. Нужно этот город поделить на К районов так, чтобы границы каждого района можно было представить в виде одной неразрывной фигуры если слишком непонятно, то, короче, чтобы из любого дома в районе можно было перейти в любой другой в том же районе, не выходя из этого района. Но чтобы избавиться от внутрирайонного неравенства, было решено ввести для каждого района уровень неравенства: стоимость самого дорогого здания в районе вычесть стоимость самого дешёвого здания в районе. Требуется разделить город на районы так, чтобы наибольший уровень неравенства из всех районов был как можно меньше.Примечание: эта задача не решается каким-то быстрым 100% методом, поэтому приветствуются эвристические подходы.
>>162420сначала делим город на районы по числу домов, т.е. один район — один дом. потом на каждом шаге объединяем два соседних района в городе по принципу наименьшего роста самого большого неравенства до тех пор, пока районов не станет K. по сути задача на объединение соседних вершин графа с наименьшим весом ребра, где веса рёбер пересчитываются после каждого объединения.хз насколько оптимальным будет результат, и как лучше выбирать из альтернативных шагов с одинаковым значением роста неравенства, дальше думать лень
>>162458Алгоритм Крускала, значит? Тоже о нём думал. Хороший, но пересчитывать рёбра долго. Ещё могут быть случаи, когда район берёт «в кольцо» дом, который ну никак не подходит. Но это пока лучший вариант, как по мне.
Можно добавить алгоритм «высвобождения» здания из кольца, где ты соединяешь каким-то путём этот проблемный дом с областью, куда он подходит лучше. Могут юыьб проблемы территориальные. Думал ещё над таким решением, чтобы сначала разделить город на прямоугольники площадь примерно n/k(округлять в меньшую), а потом оставшиеся распределять по областям примерно оптимальным алгоритмом и параллельно разбивать области на змейки длиной n/k, но там нужен +/- хороший алгоритм поиска нужного пути (и быстрый). При пересечении худший вариант разбивать на две части как в змейке. Два разных решения в итоге сравнить и вывести лучший. Вообще, когда есть запас времени, стоит решать такие задачи несколькими противоположными алгоритмами.
Вот вам задачи трёх разных уровней.Высокий: Есть у вас N двумерных коробок (N <= 200000). Для каждого известна длина и ширина. Коробки можно поворачивать на 90 градусов (менять местами высоту и ширину) и ставить друг на друга. Нужно таким образом выстроить башню из всех коробок так, чтобы высота была максимальной. Но для того, чтобы башня не упала, должно выполняться условие, что ширина каждой коробки должна быть строго больше ширины всех коробок, которые находятся над ней. Гарантируется, что башню выстроить получится.Средняя: У тебя есть n (<= 10^9) монеток, одна из них — фальшивая. Есть весы, которыми можно взвесить две горсти монет, но они сломаны: каждый раз, когда вес двух горстей неравенства, стрелка отклоняется в случайную сторону. Тебе даётся M (<= 10^9) взвешиваний. После того, как попытки кончатся, вам придётся выбирать монетку наугад. Какая наибольшая вероятность угадать фальшивую монетку, учитывая, что ситуация будет оборачиватьсч всегда не в вашу пользу. Пример: у вас 3 монеты и 1 взвешивание. Мы берём случайные две и взвешиваем. Если веса равны, то оставшаяся монета фальшивая, но так как ситуация всегда против нас, веса будут неравны. Тогда мы сможем взять одну из двух монет и с вероятностью 0.5 она окажется фальшивой. Итого, ответ — 0.5.Низкая: На научной конференции вы представляете новый язык программирования и решили доказать, что сложение строк в нём коммутативно. Но так как вы прекрасно понимаете, что сложение двух строк — операция некоммутативная, вам для примера придётся специально подобрать две строки a и b, состоящие из заглавных букв латинского алфавита, с длинами N и М соответственно так, чтобы выполнялось условие a+b=b+a (где + означает объединение двух строк, «ab»+«cd» = «abcd»). При этом, вы знаете ещё одно слабое место своего нового языка: вы имеете на бумажке две строки s и t с длинами N и M соответственно и знаете, что если в строке a в какой-либо позиции i стоит символ s[i] и/или в строке b в какой-либо позиции j стоит символ t[j], ваша программа выдаст фатальную ошибку деления на ноль. Ваше задание: зная N, M, s и t выведите строки a и b или же выведите «-1», если таких строк не существует.(1 <= N, M <= 100000).Могу подсказать, если что. Удачи.
Хочу рассказать немного о сайте codechef.comКогда-то там были интересные задачи, длинные 10-тидневные контесты, над которыми приходилось поломать голову. Но сейчас, когда очередной контест написали индусы (которые являются основной аудиторией таких сайтов), я просмотрел типичные индские сборы иибудто паззлы в моей голов сложились в одну картину. О мастерстве индусов-программистов можно говорить долго, но сейчас я увидел, на каких задачах растут спортивные программисты в Индии.У них абсолютно отсутствуют многие базовые подходы к решению задач. Из шести задач на индском соревновании ни одна не является на какой-либо алгоритм или оптимизационную идею. Лишь конструктив и чистая математика школьного уровня. Задача на конструктив — это, по факту, задача уровня «раскрасьте клетчатую доску в минимальное количество цветов так, чтобы никакие клетки не имели одинаковый цвет, если у них есть общая клетка-сосед». Это не задача на раскраску графа и не динамика. Ты просто сидишь и подбираешь узор, а потом ищешь частные случаи. Второй их любимый тип задач — это чистой воды математика, т.е. когда ты решаешь задачу на листочке, а потом в код выписываешь одну формулу и расписываешь к тому ряд исключений. Их высший пилотаж — соединение двух тяжеловесных структур данных (а потом постоянно ограничения меняют, потому что, оказывается, люди не только на С++ пишут) вкупе с чем-то из области университетской дискретной математики. Опять же, никакой уникальной задумки. Пустая зубрёжка. О качестве и однозначности поставленных условий и регулярных изменениях в этих условиях со словами «we changed ... in our problem .. due to ... Problems were rejudged, time was added. Sorry for inconvenience!» я молчу. Я понимаю, они начинают, развиваются, все дела, но хуже всего то, что, сидя на таких сборах и на сайтах вроде codechef.com, они считают это нормой и, получив ранг кандидата в мастера или мастера, думают, что преуспели, хотя те же кандидаты и мастера из сайта codeforces.com в соревновании не дадут им шанса. Слышал, они это называют Indian School, особенностью их школы программирования вроде геометрии в России, кододрочерства в Китае и идейности и рандомизаций головного мозга в Польше. Конструктив — их достояние. Только недалеко он их заводит, как шутили над ними, так и шутят. А перебор решений в голове — удел мартышек, если вы спросите моё мнение. Вот так. Вот вам и индийская школа.