[ > ]
[ < ] /sg/ - steins;gate  [Каталог]        [Главная] [Фрейм] [Однопоток] [FAQ] [Борды] [Настройки] [Поиск]
Перейти:
Поиск:

[Назад] [Весь тред] [Последние 50 постов]
Ответ

Имя
Тема   (reply to 150452)
Текст
Прикрепить
Файл
Captcha image
Смайл CatHead EmoAnime RedFox BoardFaces Other
Опции     Предпросмотр поста
Пароль  (для удаления постов и файлов)
  • Поддерживаемые типы файлов: GIF, JPG, MP3, OGG, PNG, WEBM
  • Максимальный размер файла 35673 KB.
  • Максимальный размер поста 30 KB.
  • Запрещен постинг ЦП.
  • Запрещены вайп и реклама.
  • Шитпостинг не нужен. Это не /b/.
  • Обо всём остальном смотри FAQ.
  • ?????
  • El Psy Congroo.

Файл 153523411446.png — (817.16KB, 600x340) Искать картинку в гуглеИскать картинку в iqdbИскать картинку в TinEye
150452 No. 150452 Скрыть тред [ 1 ] quickreplyquickedit
Первый тред математиков и программистов-теоретиков. Здесь мы проверяем свои навыки аналитического мышления и мифической необходимой теоретической базы, оставляем интересные задачи или задачи, с которыми не справились, возможно, учим новое. Курису явно предпочитает эксперименты, а общество — полезную практику, однако здесь у всех есть свобода заниматься абстрактными и малополезными вещами. Просьба писать по теме.
No. 150457 Скрыть пост [ 2 ] quickreplyquickedit
>>150441
>Хотя так уже неинтересно, ты рассказал, как она называется, и когда в решении будет момент «ээ, что блядь», уже знаешь, куда смотреть.
Я тебя умоляю. Одной суммы на префиксах тебе явно не хватит.
Просто без неё и думать нечего. Я просто слегка помог.

Такая штука. Дан массив целых чисел длины n (каждый элемент больше 0). Также дано число k. Надо найти количество непрерывных подпоследовательностей (т.н. подотрезков), сумма всех элементов которых равна k. Решение должно быть не медленнее O(nlogn), память — не больше O(n). Или же считайте, что n <= 100000, Ограничение памяти — 64мб. Времени выполнения — одна секунда (в секунду выполняется около пары сотен миллионов операций).

Ваши предложения.

Ответы: >>150959
No. 150959 Скрыть пост [ 3 ] quickreplyquickedit
>>150457
https://play.golang.org/p/pW93RuDhcdn

бенчей я конечно же не делал, но если бы мне сказали, что куда-то не укладывается, то я бы поменял мапу на более быструю(а такие есть) и забил писос

алгоритм с какими-то префиксными суммами = сложна, долго делать и потом ещё дебажить, для глупого мальчика(тоесть меня) это перебор

а теперь: я правильно понимаю, что префиксные суммы = просто суммы между a[i] и a[j]? если да, то причем тут вообще префиксы?

зочем ты сюда вашу ссаную калитку впихнул?
ебаный виабушник


Ответы: >>150974, >>150976, >>150977
No. 150974 Скрыть пост [ 4 ] quickreplyquickedit
>>150959
>https://play.golang.org/p/pW93RuDhcd
В Крыму не работает, кстати.

Молодец. Решил. Кстати, не так, как я предполагал. Мапы — это шаг в сторону лени, но я ничего против них не имею. Хотя мапы сами по себе имеют логарифмическую сложность с нехилой константой. А префиксные суммы — это просто.
p[-1] = 0 (условно)
p[0] = a[0]
p[i] = a[i] + p[i-1] для всех i.

То есть, p[i] — сумма элементов массива от 0-го до i-того. И короче, сумма элементов от l до r равна p[r]-р[l-1]. Вот. И для каждого p[r] я двоичным поиском искал такую p[l-1], чтобы она была равна p[r]-k, т.е. чтобы p[r]-p[l-1] = k. Двоичным поиском пользоваться можно, потому что все элементы в массиве а положительные, а значит массив р монотонно возрастает.

Пользуясь этим же фактом, можно придумать штуку ещё круче. Есть два указателя l и r. l = r = 0. Текущая сумма sum = a[0]. Вот. И если текущая сумма меньше k, то мы увеличиваем r на 1 и добавляем a[r] к сумме. Если текущая сумма больше k, удаляем a[l] из суммы и увеличиваем l на 1. Если сумма равна k, запоминаем это и увеличиваем l на 1. Можно повертеть это в голове и понять, что эта штука работает и работает за чисто линейное время. Такие дела. Но для обоих решений нужен тот факт, что все числа в массиве положительные.

Тут вообще-то вся борда о нашей ссаной колитке. В Риме веди себя по-римски. Или как-то так.

Ответы: >>151021
No. 150976 Скрыть пост [ 5 ] quickreplyquickedit
>>150959
Как это работает, почему от текущей суммы отнимается нужная?

Ответы: >>150982, >>151021
No. 150977 Скрыть пост [ 6 ] quickreplyquickedit
>>150959
И как долго думал над этим, кстати?

Ответы: >>151021
No. 150982 Скрыть пост [ 7 ] quickreplyquickedit
>>150976
Префикс длины i — это первые i элементов в массиве, чтобы ты понимал.
А сумма элементов массива с индексами от l до r — это сумма элементов префикса длины r вычесть сумму элементов префикса длины l-1.

M[x] отвечает на вопрос «Сколько есть префиксов с суммой элементов в нём, равной x?» Поэтому, для префикса длины i с суммой элементов currSum есть М[currSum-sum] префиксов с длинами, меньшими i и суммой элементов currSum-sum. Значит, мы можем вычесть из префикса длины i любой из M[currSum-sum] префиксов и получить непрерывный отрезок на массиве с суммой элементов currSum-(currSum-sum) = sum, т.к. сумма элементов текущего префикса длины i равна currSum. Таким образом, есть M[currSum-sum] непрерывных отрезков чисел, сумма которых равна sum и конец которых лежит на i. Перебираем все i и находим ответ. Хорошее решение.

Ответы: >>150983
No. 150983 Скрыть пост [ 8 ] quickreplyquickedit
>>150982
Хватит пост обновлять, мешает читать..
Ну я понял, спасибо.
>currSum-(currSum-sum)
Вот это конечно дико помогло. Не знаю как правильно надо было думать о таком, по всякому визуализировал и пытался сэмулировать в голове, но никак не мог добраться до этой идеи.
Не знаю, надо думать более математично.

Ответы: >>150985
No. 150985 Скрыть пост [ 9 ] quickreplyquickedit
>>150983
Просто так организм на задачки не настроишь. Во-первых, надо иметь терпение и понимать, что порой задачи прокручиваются в подсознании даже если ты о них сейчас не думаешь. Не можешь понять решение или решить задачу — пойди попей чаю, прогуляйся, поиграй в компьютер, а потом возвращайся со свежими идеями. Во-вторых, для того, чтобы решить задачу, нужно иметь какой-то опыт в решении похожих. Кстати, анализ чужих решений помогает сильно, если закрепить практикой. Вот ты посмотрел, а через месяц с другой задачей вспомнил, что так вообще можно. В этом и заключается успех всех крутых математиков, программистов и вообще точнонаучников, решающих задачи. Не скажу, что я так крут в этом, я ещё учусь, но так и Станкевич говорил, и Лопатин говорил, и мой тренер говорил, да и я на своём и чужом примерах замечал.
No. 150986 Скрыть пост [ 10 ] quickreplyquickedit
Есть вариант Теру найти мне задачку, чтобы я порешал (или не порешал). Я не настаиваю и не тороплю, просто вариант такой есть.
Можешь кинуть те, которые ты решить не можешь или кто-то попросил решить.

Ответы: >>151021
No. 150988 Скрыть пост [ 11 ] quickreplyquickedit
>>150987
«Гений — это 1% таланта и 99% труда».
No. 150990 Скрыть пост [ 12 ] quickreplyquickedit
>>150989
Сложно здесь судить о цифрах, но посыл, думаю, ясен. Чтобы выжать всё из своего таланта, работать надо тоже пропорционально таланту. Думаю, что работать надо столько, что даже с посредственным талантом о потолке задумываться желание отпадает. Лично меня одолевают такие мысли тогда, когда я лежу после того, как где-то проиграл и хандрю. А когда трудишься, становится не до этого. Вера в себя просто появляется из необходимости.
No. 150993 Скрыть пост [ 13 ] quickreplyquickedit
>>150991
Да. Когда ты делаешь что-то, к чему у тебя нет никакой склонности, даже тройное усердие не спасёт.
No. 150996 Скрыть пост [ 14 ] quickreplyquickedit
>>150991
Хотя то, что ты не понял решения Теру, ничего не говорит. Я сам некоторое время впирал, да и к тому же это алгоритм, который написал не ты, а та часть была реально неочевидной.
No. 150997 Скрыть пост [ 15 ] quickreplyquickedit
>>150994
А сколько ты уже программированием занимаешься?
No. 150999 Скрыть пост [ 16 ] quickreplyquickedit
>>150998
В любом случае, лучше не меланхолить, а заниматься, как по мне.
No. 151021 Скрыть пост [ 17 ] quickreplyquickedit
Файл 153549658991.png — (305.07KB, 604x402) Искать картинку в гуглеИскать картинку в iqdbИскать картинку в TinEye
151021
>>150974
>В Крыму не работает, кстати.
лол что, почему официальный сайт ЯП не работает в Крыму?
го рефку на впн дам, будет работать всё

>мапы сами по себе имеют логарифмическую сложность с нехилой константой
э, нет, O(1) в лучшем, O(n) в худшем, так скозатб. Где там логарифмические?

>эта штука работает и работает за чисто линейное время
да, согласен

>>150976
шарик ниже сделол объяснение с префиксами (я так и не понял почему [0:i] называются префиксами), но даже мне объяснение не оч очевидно, поэтому вот так:

делоем мапу, каждый ключ = сумма подмассивов. значение = к-во раз, когда эта сумма повторяется.
currSum = текущая сума, в начале это нуль
нулевая сумма уже есть 1 раз, это важно, так что мапу дополняем

итерируем эл-ты, типа i = currentIndex:
прибавляем текущий к currSUm

делаем абракадабру:
отнимаем currSum-sum. ответ = столько, сколько «перевес» для того, чтобы подмассив [0:currentIndex] вкладывался в sum. но прикол в том, что у нас есть мапа со всеми уже пройденными [0:Index] до нашего currentIndex. раскрываем карты так скозатб, и смотрим, где у нас сзади есть такие подмассивы с нужным нам весом, которые можно заюзать. визуальненко это выглядит так:



0-4=-4, -4-7=-11, сложна

-4+0=-4, -4-7=-11, сложна

-4+1=-3, -3-7=-10, сложна

-3+3=0, 0-7=-7, сложна

0+0=0, 0-7=-7, сложна

0+4=4, 4-7=-3, ОПА В МАПЕ ЕСТЬ -3 БИНГО, это значит, что наш самый большой на текущий момент подмассив [0:5], те {-4, 0, 1, 3, 0, 4} всего весит 4, а 4-7=-3, и вес -3 присутствоет, значит, если его выкинем, т.е. сделаем из того подмассива {3, 0, 4}, то впишемся в 7. и к-во минус-троек, тоесть значение ключа «-3» в мапе это как раз к-во таких вот подмассивов от нуля до какого-то j, j<i, которое можно выкинуть, чтобы вписаться в хату, и если можно это ещё более визуальненько представить как мы берем элементы с правой стороны с currentIndex и едем влево, делоя нужные нам подмассивчики, типа в обратную сторону.



вписываем в мапу currSum разумеется, если уже такая сумма была, инкремент.

ну и так далее......

>>150977
увидел позавчера, сегодня сел думоть где-то в час дня, запостил в 4

>>150986
ну такого рода задачки сам по себе я не решаю, если честно, только когда тут их вижу чтобы подумоть и от саморазвития не отупеть, я за компутером занимаюсь немного другими вещами пик
ты кидай, я по желанию и свободному времени буду думать

Ответы: >>151028, >>151029
No. 151028 Скрыть пост [ 18 ] quickreplyquickedit
>>151021
>э, нет, O(1) в лучшем, O(n) в худшем, так скозатб. Где там логарифмические?
Если мапа реализована деревом, то будет логарифмической.

> (я так и не понял почему [0:i] называются префиксами)
ну вот как со словами тут. префикс — просто первые i букв-чисел.

>0+4=4, 4-7=-3, ОПА В МАПЕ ЕСТЬ -3 БИНГО, это значит, что наш самый большой на текущий момент подмассив [0:5], те {-4, 0, 1, 3, 0, 4} всего весит 4, а 4-7=-3, и вес -3 присутствоет, значит, если его выкинем, т.е. сделаем из того подмассива {3, 0, 4}, то впишемся в 7. и к-во минус-троек, тоесть значение ключа «-3» в мапе это как раз к-во таких вот подмассивов от нуля до какого-то j, j<i, которое можно выкинуть, чтобы вписаться в хату, и если можно это ещё более визуальненько представить как мы берем элементы с правой стороны с currentIndex и едем влево, делоя нужные нам подмассивчики, типа в обратную сторону.

ясненько, спасибо.
No. 151029 Скрыть пост [ 19 ] quickreplyquickedit
>>151021
>э, нет, O(1) в лучшем, O(n) в худшем, так скозатск*. Где там логарифмические?
Просто в плюсах map написан на eval-дереве, а она считается чуть ли не самой надёжной из деревьев поиска. Поэтому и асимптотика O(logn) почти всегда. А то, что map в Go написан так медленно, говорит плохо о самом языке. Хотя тот мап-побыстрее может и работает на хороших деревьях.

>я так и не понял почему [0:i] называются префиксами
Ну тип префиксы и суффиксы. Просто терминология такая.

>ты кидай, я по желанию и свободному времени буду думать
Кей. Найдётся — кину. Графы решать умеешь? Просто на будущее спрашиваю.

Ответы: >>151032, >>151041, >>151042
No. 151032 Скрыть пост [ 20 ] quickreplyquickedit
>>151029
>Просто в плюсах map написан на eval-дереве
Нет, там есть как ordered_map, так и unordered_map.
На деревьях написан первый.

Второй же реализован массивами бакетов, где индексы образуются из хеширования ключей. При хорошей стратегии против коллизий сложность будет O(1). При хреновой, в бакетах для одного и того же хэша будет несколько значений, которые придется обойти в худшем случае со сложностью в O(k), где k — размер бакета. В самом худшем случае все ключи будут хешироваться в одно и тоже значение и такая мапа станет тупо списком.

Ответы: >>151038
No. 151038 Скрыть пост [ 21 ] quickreplyquickedit
>>151032
Вот это кстати интересно. Я о таком не знал. Хотя в моей сфере хешами вообще лучше не пользоваться, потому что если автор тестов будет пидором, то он включит в тесты что-то, что хеши сломает. Для каждой популярной хеш-функции есть контртесты. Просто ordered_map в плюсах map называется.
No. 151041 Скрыть пост [ 22 ] quickreplyquickedit
>>151029
>Графы решать умеешь?
Если не умеет, все равно кинь на всякий случай. Хочется тоже поучаствовать.
No. 151042 Скрыть пост [ 23 ] quickreplyquickedit
>>151029
в го мап = хешмап. у хешмапа сложности = пост выше. мы же изночально мою реализацию обсуждаем, не?

могу только сказать, что в идеале через О() говорить про хешмапы это говно говна, значение имеет практический бенч(результаты которого на архитектурах разных могут быть разные), ключ(точнее его тип) и то какую хешфункцию юзаешь, точнее её устойчивость к колиззиям

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

> Графы решать умеешь?
ну типа я знаю, что это такое, задач конечно же я на них вне лаб (тоесть двух предметов) я не решал и всё такое

Ответы: >>151046
No. 151046 Скрыть пост [ 24 ] quickreplyquickedit
>>151042
могу ещё добавить, что лучше конечно же задачи приближенные к реальности гонять, а не чёт вообще спортивное, это неинтересно

Ответы: >>151047, >>151052
No. 151047 Скрыть пост [ 25 ] quickreplyquickedit
>>151046
Смысл с твоими-то способностями бояться спортивного?
No. 151052 Скрыть пост [ 26 ] quickreplyquickedit
>>151046
Что-то неспортивное? Короче, вам задача — вывести строку из 1000000 букв латинского алфавита так, чтобы каждая буква встречалась не больше, чем 40000 раз, каждое сочетание из двух соседних букв встречалось не больше, чем 2000 раз, каждое сочетание из трёх соседних букв встречалось не больше, чем 100 раз.

Эта задача такая неспортивная, что в своё время взорвала мне пердак. Удачи. Сильно налегать на неё не советую, а то перегорите. Завтра вечером решение скину.

Ответы: >>151055, >>151170
No. 151055 Скрыть пост [ 27 ] quickreplyquickedit
>>151052
нитраль, я даже второй раз читать это не буду, не говоря о решении

Ответы: >>151057
No. 151057 Скрыть пост [ 28 ] quickreplyquickedit
>>151055
Мог бы оригинал кинуть, но там подсказки. Если захотите проверить решение, киньте мне. Или попросите оригинал, но там придётся регистрироваться, а ещё подсказки.
No. 151060 Скрыть пост [ 29 ] quickreplyquickedit
Но на «нет» и суда нет.

http://acm.timus.ru/problem.aspx?space=1&amp;num=1220

Вот вам такая. Практически-ориентированная. Прежде чем заявить о решении, попробуйте его заслать. И не подсматривайте.

Ответы: >>151074
No. 151074 Скрыть пост [ 30 ] quickreplyquickedit
>>151060
Делаешь класс стека, интерпретируешь файл
Парсишь команду, если пуш, если стека нет, инстанс мутишь, и на инстансе Push(v)
Если поп, на инстансе метод Pop()

Это типа упражнение на считывание файла? Зачем кво команд дано?

Ответы: >>151079
No. 151079 Скрыть пост [ 31 ] quickreplyquickedit
>>151074
Лимит памяти 750кб. А динамические структуры в элементе хранят как минимум одну перменную кроме самого числа. Вот размер int — 4 байта, их в элементе 2, а чисел — 100000. Такие дела. Приходится выкручиваться.

Ответы: >>151080, >>151095
No. 151080 Скрыть пост [ 32 ] quickreplyquickedit
>>151079
Стек можно выделить на стеке!

Ответы: >>151082
No. 151082 Скрыть пост [ 33 ] quickreplyquickedit
>>151080
Память стека тоже учитывается в ограничениях.

Ответы: >>151083
No. 151083 Скрыть пост [ 34 ] quickreplyquickedit
>>151082
Как именно? 4 * 100000 это примерно 390кб памяти.

Ответы: >>151084
No. 151084 Скрыть пост [ 35 ] quickreplyquickedit
>>151083
Сможешь организовать стек с элементом в 4 байта?

Ответы: >>151085
No. 151085 Скрыть пост [ 36 ] quickreplyquickedit
>>151084
Да, но это будет просто массив с очень неэффективными методами вставки. зато вписывающийся в пространственные ограничения. Но сложность вставки будет не хуже O(1000).

Ответы: >>151087
No. 151087 Скрыть пост [ 37 ] quickreplyquickedit
>>151085
Окей. Мне интересно. Сейчас писать не советую, потому что я смогу прочитать только утром. У меня у самого есть идея, я ей поделюсь завтра.

Ответы: >>151088
No. 151088 Скрыть пост [ 38 ] quickreplyquickedit
>>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 всё понятно. Но наверное это будет слишком медленно, раз, судя по всему, ты не воспринял это как верное решение сразу?

Ответы: >>151094, >>151095
No. 151094 Скрыть пост [ 39 ] quickreplyquickedit
>>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 байт памяти.
No. 151095 Скрыть пост [ 40 ] quickreplyquickedit
>>151079
Ну лан, срез срезов интов. Новый стек = добавляем к срезу срез. Существующий срез — ищем нужный по индексу. Аппенд = пуш, v =s[len(s)] и s = s[0:len(s)] = поп

Это самое лоу лвл которое я могу придумать, если соблюдать одну вещь — стеки в проге должны быть именно нормальными стеками, а не какими то маняврированиями или многоходовочками чтобы сохранить память.

>>151088
> сдвигаем все элементы вправо
Rip
Массово двигать элементы в срезе/массиве это плохо, очень плохо.

Ответы: >>151098
No. 151098 Скрыть пост [ 41 ] quickreplyquickedit
>>151095
Динамическая структура данных. К тому же, на эту задачу ограничение языков: только С, С++ и Pascal. На других решения может тебе не быть. Мне пришлось поменять компилятор на Visual C++, потому что g++ зажирается и отдельно инициализирует себе 100 килобайт, из-из-иа чего моё решение не проходило по памяти.

Ответы: >>151109, >>151110
No. 151109 Скрыть пост [ 42 ] quickreplyquickedit
>>151098
Моё решение не сработало. Я пытался выделить на элемент в структуре 48 бит (6 байт), но это слишком неоптимально. Нужно ровно 47. Сейчас думаю, как бы это организовать.
No. 151110 Скрыть пост [ 43 ] quickreplyquickedit
>>151098
вот поетому я и говорю, давайте нормальные хоть скольк-т реалистичные задачки, байтоебство на 100кб или ограничение в 750кб это нереалистично в 95% случаев, заказчику дешевле планку или диск купить, чем платить гребцам, чтобы они тужились над такими вещами или тратили время на переключение блядь компилятора ради 100кб

кароч я понял что мне надо чет самому делоть, так сказатб

есть сервак, который в каждый момент времени может обрабатывать 1 мемес, или не обрабатывать мем вообще

есть школьники, которые срут на сервак мемчики (тоесть заявки, если научно так сказать), и серваку нужно мемы обработать

обработка мема = загрузка сервака на 100% на какое-то время, которое называется временем обслуживания заявки.

заявки скидываются в 1 очередь с дисциплиной fifo

входной поток заявок пуассоновский с интенсивностью λ, поток обслуживания тоже пуассоновский с интенсивностью μ. потоки стационарны, т.е. те 2 интенсивности не меняются (что конечно же нереалистично но неважно)

ваша задача — имитационно смоделить такую штуку и найти коеф.загрузки такой системы, среднюю длинну очереди, среднее время нахождения в системе (ожидание+обслуживание), вероятность того что на момент прихода мемеса в очереди будет n задач

имитационно = время дискретная величина, есть квант

по научному так скозатб эта штука(тоесть система) по классификации кендалла М/М/1

это очень существенно упрощенная 1-я лаба из предмета в шараге, так ее закодить просто
чуть сложнее = серваков может быть несколько, больше 1-го, тогда они берут из общей очереди
сделать несколько дисциплин, не только fifo/lifo
поток обслуживания может быть не пуассоновским

>ты хочешь чтобы мы делали за тебя лабы
да
нет, я её уже давно сдал

>нипрактична
нет, очень даже практична, и не только в ит

>имитационное моделирование говно говна
нет, юзается когда моделить дорого/долго
если хочешь не имитационное, каждый сервак = тред, система многопоточная, слушоешь по порту, с другой проги шлешь заявки, так даже интереснее будет, кек

Ответы: >>151124
No. 151111 Скрыть пост [ 44 ] quickreplyquickedit
Как поменять количество бит в байте?
No. 151123 Скрыть пост [ 46 ] quickreplyquickedit
Спасибо. Вопрос снят.
No. 151124 Скрыть пост [ 47 ] quickreplyquickedit
>>151110
>750кб это нереалистично в 95% случаев
А если запросов не сто тысяч, а несколько миллиардов? И тогда 750кб плавно перерастают в 10-15гб. А это уже вполне реальные ограничения. Я думаю, что эта задача практична хотя бы потому что сейчас идёт эпоха BigData и поэтому работать с ограниченными ресурсами приходится нередко.
No. 151141 Скрыть пост [ 48 ] quickreplyquickedit
Так её надо как решить? Смоделировать какое-то большое количество запросов или теми формулами всё? Если формулами, то это довольно скучно получается. А если моделировать, я смогу даже не один сервер реализовать, а сеть.

Ответы: >>151152
No. 151152 Скрыть пост [ 49 ] quickreplyquickedit
>>151141
Имитационно моделировать конечно же, я там так и написал.
Да, заявки офк, тысячу-две, но это неважно в принципе.
Формулы для понимания ситуации и ответов на вопросы, ну и для распределений конечно же.

Ответы: >>151154
No. 151154 Скрыть пост [ 50 ] quickreplyquickedit
>>151152
Кстати говоря, "практические твои значения с формулами должны совпадать

Ответы: >>151157
No. 151157 Скрыть пост [ 51 ] quickreplyquickedit
>>151154
А если я скажу, что запрос всегда идёт в самый быстрый доступный свободный сервер, это будет оптимально?

Ответы: >>151161
No. 151161 Скрыть пост [ 52 ] quickreplyquickedit
>>151157
в задаче интенсивность потока обслуживания на всех серверах одинаковая, поэтому если несколько серваков свободны, то заявку обслуживает рандомный, не имеет значения какой.
No. 151167 Скрыть пост [ 53 ] quickreplyquickedit
Короче, что-то сделяль.
https://ideone.com/zw49Sm

Порядок ввода таков: количество серверов, скорость выхода запросов, скорости обработки одного запроса серверами, дальше идут m-1 строк, на i-той список серверов, в которые запрос может попасть из сервера i. M-тый сервер замыкающий. На последней строке количество запросов. Я не уверен в правильности решения, но и проверять не на чем.

Ответы: >>151168
No. 151168 Скрыть пост [ 54 ] quickreplyquickedit
>>151167
Больше ничего не сделаю, потому что в этой теме не разбираюсь.
No. 151170 Скрыть пост [ 55 ] quickreplyquickedit
>>151052
Так вот. Я под катом оставлю решение.

РазвернутьПросто рандомно буквы выводите

No. 151584 Скрыть пост [ 56 ] quickreplyquickedit
Ребят, привет. Такая вам задача:

Есть 2 <= n <= 100000 отрезков, i-тый начинается в x_i и заканчивается в y_i. Как минимум n-1 из них имеют общую точку (может быть, и не одну). Выбрать из этих n отрезков n-1 так, чтобы их общая часть имела максимальную длину.

Если задача для вас слишком простая, скажите. Я стану кидать сложнее, мне не трудно.

Если скучная — скиньте задачу, которую считаете интересной.

Ответы: >>151594, >>151596, >>152163, >>154099
No. 151594 Скрыть пост [ 57 ] quickreplyquickedit
Файл 153597100387.jpg — (25.25KB, 400x400) Искать картинку в гуглеИскать картинку в iqdbИскать картинку в TinEye
151594
>>151584
>Ребят, привет.
Привет, внучок!
No. 151596 Скрыть пост [ 58 ] quickreplyquickedit
>>151584
Все отрезки лежат на одной прямой?

Ответы: >>151600
No. 151600 Скрыть пост [ 59 ] quickreplyquickedit
>>151596
Да
No. 152163 Скрыть пост [ 60 ] quickreplyquickedit
>>151584
Секунду, нам нужно выбрать n-1 отрезков из n. И известно что n-1 из n имеет общую точку. Но разве это не значит что мы должны тупо взять все отрезки кроме одного единственного который не имеет никаких общих точек? И из этих n-1 общая длина и будет максимальной среди n-1

Ответы: >>152245
No. 152245 Скрыть пост [ 61 ] quickreplyquickedit
>>152163
Последний может иметь общие точки. Но не со всеми. Нужно его быстро найти.
No. 153798 Скрыть пост [ 62 ] quickreplyquickedit
Ещё одна задачка: у вас на доске написан набор чисел. Они могут быть отрицательными и неотрицательными. Дальше идёт такая игра: за одно действие вы можете стереть любые два числа на доске и написать на той же доске их произведение. Также можно в любой момент просто стереть одно число, но не более одного раза. В любом случае, в какой-то момент на доске останется одно число. Нужно его максимизировать. Опишите свой алгоритм действий.

Если хотите, объясню решение последней задачи.
No. 154099 Скрыть пост [ 63 ] quickreplyquickedit
>>151584
вот в общем.
https://pastebin.com/t0tFnArf
на питоне потому что для мелких вещей проще.

Ответы: >>154150
No. 154150 Скрыть пост [ 64 ] quickreplyquickedit
>>154099
Опиши значение переменных, пожалуйста.

Ответы: >>154152
No. 154152 Скрыть пост [ 65 ] quickreplyquickedit
>>154150
solution возвращает индекс отрезка, у которого количество отрезков с общими с ним точками меньше чем n — 1
target и otherTarget — потенциальные кандидаты
common — текущее значение общей части

Ответы: >>154157
No. 154157 Скрыть пост [ 66 ] quickreplyquickedit
>>154152
Жадное решение, но вполне вероятно, что сработает. У меня было другое. Тип p[i] — общий отрезок отрезков от 0-го до i-того, а s[i] — от i-того до последнего. Короче, для каждой i мы проверяем общие точки p[i-1] и s[i+1], то есть как бы проверяем отрезок, если из него выкинуть i-тый. Но если понять, что у «лишнего» максимальный a_i или минимальный b_i, задача становится ещё проще.

Ответы: >>154161
No. 154161 Скрыть пост [ 67 ] quickreplyquickedit
>>154157
вроде должно сработать, ответы полностью совпадают с реализацией в лоб тупым и надежным перебором O(n^2).
100000 отрезков проходит за 0.2 секунды, хотя я не знаю какие ограничения, они не уточнялись.

понятно.

Ответы: >>154179
No. 154179 Скрыть пост [ 68 ] quickreplyquickedit
>>154161
Вообще, когда линейный алгоритм работает с такой скоростью, это печально. 500000 уже едва пройдёт в таймлимит. Учитывая, что разработчики могут линейному алгоритму и 10 миллионов скармливать, получается не по-олимпиадному как-то. Очень медленный язык. Поэтому когда на таких тяжеловесных задачах стоит длинная арифметика, я плачу кровью, потому что джаву я не учил, а в крестах её нет.

Ответы: >>154180
No. 154180 Скрыть пост [ 69 ] quickreplyquickedit
>>154179
не понял, проблема в языке или самом алгоритме. или и там и там.

Ответы: >>154184
No. 154184 Скрыть пост [ 70 ] quickreplyquickedit
>>154180
Алгоритм нормальный, язык плохой.

Ответы: >>154195
No. 154195 Скрыть пост [ 71 ] quickreplyquickedit
>>154184
ну питон всё же не очень предназначен для суперскоростных олимпиадных штук, увы.
No. 155892 Скрыть пост [ 72 ] quickreplyquickedit
Файл 153892610674.jpg — (131.96KB, 865x516) Искать картинку в гуглеИскать картинку в iqdbИскать картинку в TinEye
155892
Вот вам классика:

Ответы: >>155893
No. 155893 Скрыть пост [ 73 ] quickreplyquickedit
>>155892
Как бы вы её решили? Желательно за O(n).

Ответы: >>155895, >>155896
No. 155895 Скрыть пост [ 74 ] quickreplyquickedit
>>155893
Второй левел — решить эту задачу в двумерном варианте.
No. 155896 Скрыть пост [ 75 ] quickreplyquickedit
Файл 15389265373.png — (5.20MB, 2048x2048) Искать картинку в гуглеИскать картинку в iqdbИскать картинку в TinEye
155896
>>155893
никак, сосу, у тебя ничего по проще нет, 2+2 = ? или типа того ?

Ответы: >>155898
No. 155898 Скрыть пост [ 76 ] quickreplyquickedit
>>155896
Каков шанс того, что при броске двадцатигранного кубика выпадет число, которое делится на 3?
No. 158898 Скрыть пост [ 77 ] quickreplyquickedit
Есть ли вообще смысл поддерживать этот тред? Не хотелось бы на него забивать, но и распинаться перед стеной тоже не хочется.

Ответы: >>158939
No. 158939 Скрыть пост [ 78 ] quickreplyquickedit
>>158898
Нет смысла говорить со стенкой, но и удалять/убивать тред смысла нет. Пости задачи, которые считаешь интересными, если кому-то из нас будет интересно, начнется дискуссия, как начиналась и тогда.
Хотя сделаю небольшую ремарочку на то, что сейчас учебный год, а, значит, у некоторых посетителей треда времени и желания думать может быть меньше, это уж так сложилось, ничего не поделаешь.
No. 162420 Скрыть пост [ 79 ] quickreplyquickedit
Вот теперь такая задача: у вас есть город, который можно представить в виде таблицы NxM, каждая ячейка таблицы — жилой дом. У каждого дома есть стоимость — целочисленное значение, чем дом дороже, тем больше это число. Нужно этот город поделить на К районов так, чтобы границы каждого района можно было представить в виде одной неразрывной фигуры если слишком непонятно, то, короче, чтобы из любого дома в районе можно было перейти в любой другой в том же районе, не выходя из этого района. Но чтобы избавиться от внутрирайонного неравенства, было решено ввести для каждого района уровень неравенства: стоимость самого дорогого здания в районе вычесть стоимость самого дешёвого здания в районе. Требуется разделить город на районы так, чтобы наибольший уровень неравенства из всех районов был как можно меньше.

Примечание: эта задача не решается каким-то быстрым 100% методом, поэтому приветствуются эвристические подходы.

Ответы: >>162458
No. 162458 Скрыть пост [ 80 ] quickreplyquickedit
>>162420
сначала делим город на районы по числу домов, т.е. один район — один дом. потом на каждом шаге объединяем два соседних района в городе по принципу наименьшего роста самого большого неравенства до тех пор, пока районов не станет K. по сути задача на объединение соседних вершин графа с наименьшим весом ребра, где веса рёбер пересчитываются после каждого объединения.
хз насколько оптимальным будет результат, и как лучше выбирать из альтернативных шагов с одинаковым значением роста неравенства, дальше думать лень

Ответы: >>162461
No. 162461 Скрыть пост [ 81 ] quickreplyquickedit
>>162458
Алгоритм Крускала, значит? Тоже о нём думал. Хороший, но пересчитывать рёбра долго. Ещё могут быть случаи, когда район берёт «в кольцо» дом, который ну никак не подходит. Но это пока лучший вариант, как по мне.
No. 162464 Скрыть пост [ 82 ] quickreplyquickedit
Можно добавить алгоритм «высвобождения» здания из кольца, где ты соединяешь каким-то путём этот проблемный дом с областью, куда он подходит лучше. Могут юыьб проблемы территориальные. Думал ещё над таким решением, чтобы сначала разделить город на прямоугольники площадь примерно n/k(округлять в меньшую), а потом оставшиеся распределять по областям примерно оптимальным алгоритмом и параллельно разбивать области на змейки длиной n/k, но там нужен +/- хороший алгоритм поиска нужного пути (и быстрый). При пересечении худший вариант разбивать на две части как в змейке. Два разных решения в итоге сравнить и вывести лучший. Вообще, когда есть запас времени, стоит решать такие задачи несколькими противоположными алгоритмами.
No. 162976 Скрыть пост [ 83 ] quickreplyquickedit
Вот вам задачи трёх разных уровней.

Высокий: Есть у вас 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).

Могу подсказать, если что. Удачи.
No. 168845 Скрыть пост [ 84 ] quickreplyquickedit
Файл 154691488481.jpg — (8.61KB, 175x288) Искать картинку в гуглеИскать картинку в iqdbИскать картинку в TinEye
168845
Хочу рассказать немного о сайте 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, особенностью их школы программирования вроде геометрии в России, кододрочерства в Китае и идейности и рандомизаций головного мозга в Польше. Конструктив — их достояние. Только недалеко он их заводит, как шутили над ними, так и шутят. А перебор решений в голове — удел мартышек, если вы спросите моё мнение. Вот так. Вот вам и индийская школа.
 ●  Причина:
Пароль: []