Пожалуйста объясните алгоритм, не понимаю как сделать.Школьный балВо время проведения школьного бала планируется запустить m одинаковых воздушных шариков. Наполнить их воздухом согласились n старшеклассников с различной силой духа и выносливостью. Известно, что i-ый участник процесса наполняет один шарик воздухом за ai минут, причем каждый раз после надувания bi шариков отдыхает и переводит дух ci минут (i = 1..n). Нужно узнать за какое минимальное время (в минутах) будут надуты все шарики при оптимальной работе всех участников.
>>674231 (OP)Оп - хуй. Задача изи.
>>674239Объясни, или уходи.
Bump
>>674231 (OP)Есть пример входных данных?Смахивает на задачу на упаковку рюкзака, но сходу не могу понять как решить "жадным алгоритмом".Лезет в голову всякая чушь, уровня разбивать их на пары чтобы пока один надувает другой отдыхал и наоборот, для пары считать время, сортировать по минимальному времени их и отправлять надувать таких вот.
>>674305http://www.e-olymp.com/ru/problems/5227
>>674231 (OP)Google: multiple knapsack problem
>>674245Пояснять не буду потому что ты:1. Создал тред.2. Не привёл пример входных данных.
>>674305Жадный алгоритм - это слишком слабо.Для хороших резлуьтатов тебе нужен Dynamic Programming или Branch And Bound.
>>674410https://2ch.hk/pr/res/674231.html#674313
>>674305А чего ты так мудришь-то с жадным алгоритмом? Просто выбирай шар который влезает с минимальной затратой времени. Время отдыха учитвай как затрату на последний шар.
>>674413Задача же олимпиадная, похуй на качество - главное быстрее сделать же.
>>674423Это да. Но ты хочешь слишком хороший результат получить от жадного алгоритма. Я понимаю, что его можно выбрать в качестве первой итерации. Но когда улучшаешь результат лучше выбрать хороший алгоритм, чем пытаться полировать эвристику.
>>674231 (OP)Как же хочется порешать олимпиадочки...Но нет, блять, пиши жабаговно, сука, у тебя ипотека ещё на 10 лет.
>>674434Один хуй, примера данных нет.Может там можно въебать полный перебор и не париться.
>>674439Кстати да. Ни данных, ни ограничений по времени/памяти. О чём мы тут вообще разговариваем?
>>674313Ты промазал, ковбой:ЗадачаВатсон поставил Рыбке простую задачу – найти сумму чисел меньших N, которые должны делиться либо на A, либо на B, и вывести её остаток от деления на 1000000007 (109 + 7). Помогите Рыбке справиться с этой задачей.Входные данныеіВ одной строке задано три целых числа N, A и B.1 ≤ N, A, B < 1018.Выходные данныеВывести остаток от деления искомой суммы на 1000000007.
>>674451Сорян, эта легитимная http://www.e-olymp.com/ru/problems/7227
>>674438Мне 15
>>674548(1000 99) вариантов, перебором не получится.Требуется точное решение - эвристики и локальный поиск сосут.Остаётся Dynamic Programming и Branch and Bound. Ну или Mixed Integer Programming, если делать по-серьёзке, но это не для олимпиады.
>>674612Через Dynamic Programming у меня нихуя не получается доказать какое-то свойство решения m шаров через m-1. Там всё хитро именно из-за пауз.Через Branch and Bound можно так:- в качестве нижней границы используй жадную эвристику или какую-нибудь другую эвристику если найдёшь лучше.- в качестве верхней границы убери эти ёбанные паузы и решай стандартный multiple knapsack problem (это-то, я надеюсь, ты умеешь).
>>674626*ёбаные
>>674626Естественно, когда будешь считать верхнюю границу, учитывай время, которое уже потрачено на паузы.
>>674637>>674626Кароч, не слушай меня, через Branch and Bound хуйня полная получается.Можно через Dynamic Programming через такое соотношения:Решения для k+1 школьников и l шаров - это когда мы хуйнём x шаров новому школьнику + оптимальное решение для k школьнико и l-x шаров.Дальше, я думаю, таблицу для Dynamic Programming ты построишь сам.
>>674640Спасибо попробую
Блять, почему на этом сайте ни одного языка программирования нет?Если уже добавили Java, то могли бы и Clojure добавить, я бы им рассказал как нормально бенчмаркать через Grenchman.И даже Ocaml нет, aleksey ссыт им в ёбыч.
Помоему тут двоичной кучей (минимизирующей) проще всего. В кучу заносятся школьники, ключами служат момент времени в который они завершат надувать очередной шар. Тоесть изначально все ключи в куче равны ai соотвествующего школьника. Потом сверху кучи извлекается школьник, счетчик шаров увеличивается на один, если нужное количество шаров достигается - ответ это ключ вытянутого школьника. Если шаров не достаточно то школьник возвращается в кучу с ключом увеличеным на ai. Из-за того что школьники должны делать перерывы нужно следить за количеством надутых шаров каждым школьником - тоесть в куче нельзя хранить просто чиcла, а должна хранится структура соответсвующая школьнику с помощью который можно ослеживать сколько шаров надул школьник, и если он достиг предела, то школьник возвращается в кучу с ключом увеличены не на ai, а уже на ai + ci (перерыв плюс время необходимое на надутие очередного шара). Сложность этой хуйни полчается равна количеству шаров умноженому на логарифм школьников.Это можно улучшить если придумать способ определить достаточно большой момент времени T, которого однако гарантировано не достаточно для того чтобы надуть все шары. Тогда изменяется начальная процедура заполнения кучи. Для каждого школьника высчитывается сколько шаров он надует за время T (это просто), счетчик шаров увеличивается это количество, и в кучу школьник кладется с ключем равным количеству времени которое осталось ему до надувания следующего шара (оно может не быть равно ai - в зависимости от времени T, может быть даже больше, если момент времени Т попал на отдых школьника). А дальше обычное вытаскивание школьников пока не наберется нужное количество шаров. Сложность получается равна "оставшемуся количеству шаров" умноженому на логарифм школьников. Проблема в способе выбора достаточно большого Т - чем оно больше тем быстрее сработает алгоритм, но при этом нельзя превысить ответ. Я думаю нужно нужно отталкиваться от среднего времени затрачиваемого школьником (с учетем отдыха) - и брать немного меньше от полученого.
>>674662Ты по сути описываешь жадную эвристику. Она не гарантиурует оптимального результата.
>>674670Почему не гарантирует? У школьников есть более оптимальный способ поведения чем начать всем сразу надувать шары, делая перерывы когда выбиваются из сил?
>>674684Может быть.Пример: 3 шара, 3 школьника. Первые 2 надувают за 1 минуту, третий надувает за 100 минут. Оптимально третьего послать нахуй.
>>674957Ну так и будет. Изначально школьники закинутся в кучу с ключами 1, 1, 100. После того как будет вытащен и закинут первый школьник куча будет 1, 2, 100, после следующего 2, 2, 100, на следующем мы наберем нужное количество шаров и ответ - ключ последнего вытянутого школьника, тоесть 2. Подход с кучей моделирует систему школьников. Давать не оптимальный ответ он может только если моделируемое поведение школьников (все сразу начинают надувать шары, делая перерывы когда выбиваются из сил) не оптимально. Естественно я не утверждаю что это идеальный способ решения, я слаб в динамическом программировании, вполне возможно что с помощью ДП можно решить более эффективно.
Есть 95% процентов робочий код, нужно обьяснить как он работает.http://ideone.com/oGjprh
>>675161Вопрос не в эффективности, а в корректности.Бремя доказательства в данном случае лежит на тебе.Читать твои телеги мне немного влом, извини. Как только ты сформулировал чёткое и короткое предложение по типу> У школьников есть более оптимальный способ поведения чем начать всем сразу надувать шарыя тебе сразу привёл контрпирмер.Сможешь так же чётко и коротко сформулировать доказательство корректности - я проверю.
>>675503Вообще, какие ограничения по времени и по размеру входных жанных? Оные вообще есть?
>>675435хз, какой-то жадный алгоритм. На ДП не похоже.
>>675505Оные извольте обозревать под гиперссылкой http://www.e-olymp.com/ru/problems/7227
>>675503Ох лол. Иди нахуй.
>>675524Какие мы важные.Пишешь длинные телеги, в которых смешиваешь в кучу идею с реализацией и даже не думаешь что-то говорить о корректности.Потом ждёшь что кто-то это будет читать, утирать тебе сопли и учить тебя нормально формулировть свои мысли, а потом ещё будет искать контрпример для тебя.Ну ты понял.
>>674231 (OP)пусть есть один школьникнаилучшая стратегия для него начинать дуть сразу после отдыхапусть есть 2 школьникаесть два варианта0 надувают одновременно1 второй начинает дуть с задержкойэто либо даст задержку, либо не даст, но время не улучшит никак, поэтому на хуй не нужнов первом слкучае следующее соотношение будет справедливо для двух и большего числа школьников в виду аддитивности0 посчитаем поток, с которым надувают шарики 1/ai1 сложим потоки надува sum(1/ai)2 надуем с совокупным потоком m/(sum(1/ai))3 учтём время на отдых sum(floor(m/(bi)ci))время надува будет m/(sum(ai))+sum(floor(m/(bi)ci))
>>675512>Источник Житомирская ХХVIII обласная олимпиада по информатикеЧому не по русскому языку?
>>675569Кстати это еще что.Таких организаторов олимпиады в анус без смазки ебать надо, там минимальное время не 8, а 7 минут.
>>675573Как выглядит решение для 7 минут?
>>675577Задача кстати элементарная, если шариков больше надувающих. По сути только итерироваться по времени и считать шарики. Сейчас сфоткаю и выложу графический способ решения, по которому все станет понятно (в том числе и обосрамс с 8, а не 7)
>>675580да ну не может там быть 7 минутв семь минут уложится всего 3 шара от третьего и 2 от второго (по 6 минут), значит первому остаётся 5 шаров. 5 шаров у него займут 11 минут.
>>675584Ты b и c перепутал: первый должен делать 3хминутные паузы после каждых 2х шаров, а не наоборот.
>>675588> за ai минут, причем каждый раз после надувания bi шариков отдыхает и переводит дух ci Таблица по горизонтали, а не по вертикали что ли идет?
>>675580Доказательство оптимальности не забудь.
>>675590Да, по горизонтали. Один ряд - описание одного школьника.
>>675592Щас тогда переделаю.
Таки 8.Но я уже определился с выбором - назовем этот метод "интегрирующим". Для каждого школьника строим числовой ряд - сколько шариков он надувает за текущее время, и суммируем ряды, а дальше ищем искомое время в результирующем ряду.
>>675597В принципе, на скорую руку могу запилить реализацию на дишке.
>>675598Доказательство оптимальности не забудь.
Проверяйте:http://ideone.com/hpdwsVhttp://ideone.com/M4Pmh7
>>675637Это еще зачем, лол?
>>675639Каким образом?Эталонной реализации и набора данных то нет.
>>675640Может ты и задачу рюкзака будешь решать жадной эвристикой и утверждать, что решение оптимально?
>>675641Бля, придётся в той петушатне зарегаться.
>>675644А не похуй, оптимально оно, или нет?Это тебе и доказывать, найди такие наборы данных, которые докажут, что оно неоптимально.Это олимпиадная задача, проверять будут автоматизированно. Даже если оно неоптимально, но таких наборов данных не будет - никого не ебет.
>>675648Как-то так
>>675650Ясно.нахуй из математики - это вон туда
>>675659Ты даун что ли? Мы тут не в математике, теоретическая хуйня не ебет никого. Должно сойтись по тестам за отведенное время - как то так.
>>675657Для той хуйни только на жабе писать надо?
>>675639Правильно,теперь на паскаль перепишу
>>675664Нет, можно даже Хачкиль.
>>675670Суки ебаные, дишечки нет.Набор данных, на котором проверяют - выдрать можно?
>>675674Хуй знает, не пробовал. Stdout твоей программы не показывают, как по другому выдирать - я не знаю.
>>675662Ну может ты в чём-то прав.Численные эксперименты в математике имеют место, и зачастую опережают доказательства.
>>675682А то. Ты же пользуешься классической механикой, и тебя не ебет, что она неправильная.Так как в своей жизни с такими скоростями или прочими условиями, на которых это будет ощутимо - один хуй не столкнешься.
>>675678Кодируй номерами тестов
>>675688номер теста - 1 битпрошёл - единицане прошёл - ноликВ первом прогоне выкидывает первый бит тестовых данныхво втором - второйи т д
>номер теста - 1 битвернее номер теста - это номер тестав исходнике захардкоденное число, инкрементируемоепрограмма смотрит соответствующий бит входных данных, если бит один, то решает тест, если 0 - то фейлит
>>675689По-моему это сложнее, чем решить саму задачу.
>>675691Но он же её уже решил, теперь он хочет выдрать условия тестов чтобы выложить в инет.
>>675693Больший bandwidth можно получить, если использовать память.Также это не потребует решения теста.
Маллоком выделяем памяти столько, сколько нужно.Предварительно прогоняем программу, не выделяющую кодирующей памяти вообще, чтобы иметь базовое значение
А вот время хер заюзаешь, оно обычно заблокированно. но если разблокированно, то действуем аналогично.Для большей эффективности можно добавить zlib
если они станут рандомизировать размер кучи, то его опять же можно легко узнать маллоком и внести поправку
но вообще это всё не имеет смысла, так как большая часть тестов на олимпиадах - случайная
>>675711Если она будет случайная - одно и то же решение на разных наборах может быть правильным и неправильным.
>>675716как будто что-то плохое. Важно ведь общее число пройденных тестов.Зачем они вообще показывают номера тестов, если данные от них не выдают, не понятно.
>>675724Интересно, к ним можно загрузить тест с форк-бомбой, лол?
>>675716И вообще, может тесты детерминированно случайные. То есть у каждого игрока есть случайный seed, на основе которого генерится тестовый набор, фиксированный для каждого игрока.Кстати, seed можно не генерить для каждой задачи, а выводить с помощью хеш-функции
>>675725обычно такие вызовы запрещены. Как и вызовы работы с фс кроме stdin/stdout, и прочие системные вызовы
>>675727Нахрена что то хранить?Со статическими тестами проще всего, так нафига лишние выебоны.
>>675730при выводе с помощью хеш-функции не нужно ничего кроме данных аккаунта и данных задачи, которые хранятся и так
>>675734Проверять решения разными наборами - нечестно, вот и все.
>>675730>Со статическими тестами проще всего, так нафига лишние выебоны. Чтобы нельзя было наплевать на ограничения времени и памяти. Можно неэффективным алгоритмом предпросчитать у себя на cpu/видеокарте/fpga.
>>675739Каким образом? Допустим набор статический - для всех одинаковый, но погромист извне все равно его не знает.
>>675737Я помню мне препод мануал выдал по проведению олимпиад, там было чёрным по белому написано что используются 4 группы тестов: выданные на руки с задачей, граничные случаи, рандомизированные и специально спроектированные жури с целью завалить некоторые решения.
>>675742>и специально спроектированные жури с целью завалить некоторые решения.Это чтоб свои знакомые выиграли, когда оешениям других участников можно подосрать?
>>675745хз
>>675747Я помню, как лет 8 назад после школки возлагал надежды на коколимпиадку вузиковскую. В методичке были примеры заданий и написано что отводится час. По факту - решение требовало не алгоритма, а формулки из матстатистики которую давали на 3м курсе, писать заставили на листке и дали полчаса.Учитывая, что призом был ноут - специально суки под знакомых заточили, пидоры.
>>675745Нет, это чтобы жиды выигравали, а русские нет.
>>675745ну он дал рецепт обхода - рандомизировать входные данные
>>675751ладно, я вот геометрию понял только тогда, когда в вузе курс линейной алгебры прошёл, а до этого мне это казалось какой-то хуйнёйВсе эти олимпиады решаются знанием нескольких вузовских курсов
>>675759Я серьезно - уже на 3м курсе понял, как вспомнил.Требовалась там какая та формула из комбинаторики, сцуко - и все, никакого алгоритма.А я в 11 классе такую знать никак не мог.
>>675759Если конкретно, то курсом "Дискретная оптимизация".Но в рашкинских вузах такого не бывает, насколько я знаю.
Кстати, интересный вопрос - а там оценивается время выполнения проги?В крестах то некоторые вычисления можно в compile-time упрятать.
>>675793сега приклеилась
>>675793В компайл-тайме ты не знаешь входных данных.
>>675745Чтобы частные случаи и эвристику поломать. Бывает, что неправильный алгоритм правильно работает на некотором подмножестве данных.
>>675798Делал на частных случаях и эвристике, прокатывало.
>>675800Везучий засранец.
>>675809Зато тупанул на другой хуйне, вышел уже из кабинета - тут в голову пришло решение, а обратно зайти зассал.
А вот и мое "интегральное" решение. Простое как три копейки.В душе не ебу, "оптимальное" ли оно, но все тесты проходит.http://ideone.com/5uGC5x
чем они там блядь с# компилируют, на dotnetfiddle работает, а у них с этим judge c# меня нахуй шлёт с "Ошибка выполнения"
>>675862Алсо загрузилось только со второго раза - эта олимпиадная ебань сагрилась на кириллицу в комментариях.
проверьте https://ideone.com/rB02rY
>>675913Отправил за тебя твое решение.Говно короче.
>>675913очень простой тест-кейс дополнительныйпросто замени 10 3 на 10 4и следующей строкой добавь "10 1 1" напримертвой вариант уже валится
>>675862Твоё определённо лучше, чем ДП.Но оно специфично для задачи. И ещё нужно хотя-бы самого себя убедить в его корректности (что ты сделал с помощью рисунка, это очень хороший метод).А у меня, так сказать, профессиональная деформация личности, после изучения методов дискретной оптимизации я всё делаю стандартными методами. В данном случае интуиция меня подвела, т.к. я думал что задача связана с задачей рюкзака, в которой эвристики не прокатывают.
>>675945и где он валится?https://ideone.com/2mhQFp
>>675988>следующей строкой >следующей строкой >следующей строкой >следующей строкой >следующей строкой
>>675988вот так действительно валитсяhttps://ideone.com/B5dT1f
>>675503Алгоритм X - каждый сосницкий начинает надувать шары как только может и продолжает до тех пор, пока не устанет.Допустим есть алгоритм Y, позволяющий за то же время надуть больше шаров, чем при использовании алгоритма X.Общее количество надутых шаров складывается из шаров надутых каждым сосницким. Значит в алгоритме Y некоторые сосницкие надувают больше шаров, чем в алгоритме X. А это невозможно. Уж это-то объяснять не надо?
>>676040в оптимальном некоторые сосницкие шары не трогают вообще. Потому что может быть что у одного из них ампутировали 1.5 лёгкого и один шар он надувает теперь за 1000 минут.>каждый сосницкий начинает надувать шарыбудет работать только если твой алгоритм умеет отнимать обслюнявленные шары у медленно-дующих инвалидов
>>676073Но ведь нет ограничения по количеству шариков.Сказано - нужно надуть n шариков. А сколько там резины валяется - не сказано.Ты сам себе ограничения придумываешь.
>>676084Верно. Но даже если бы лишних шаров не было формула никак не поменялась бы.От нас не требуется составлять расписание надувания шаров, так что мы можем предположить, что вокруг сосницких бегает препод и оптимальным образом распределяет шары. При таком раскладе ситуация ровно такая же что и с лишними шарами.
>>676123В любом случае, у нас самый простой вариант - дуют все участники, количество сдутых шаров безлимитно.Так что те, кто хуево дует, как минимум не сделают хуже и никак не влияют на время.
Обоссал всех в этом треде кроме себя.https://ideone.com/Wfj6H2
>>676270> кроме себяНе, на себя ты тоже норм наляпал. Учитывая что выше был анон с соточкой то можно считать что ты себя с головы до ног обоссал.
>>676286Два анона с соточкой было же.
>>676286Ок, разобассываю.
>>674231 (OP)Назовём надувание bi шариков + отдых одним циклом, время выполнения которого ti=ai*bi+ciТогда поделив bi/ti=perfi мы найдём среднюю производительность perfi каждого школьника по времени. Найдём отношение каждого perfi к максимальному max_perf из них и округлив вперёд до целых, мы найдём их соотношения rel_perfi = round(max_perf/perfi) . После чего кидаем каждому школьнику, начиная с самых производительных, количество шакриков, равное rel_perfi
>>676321Кинул свои шарики тебе за щёку.
>>676332не вовремя, он уже вдул 10, и он отдыхает 5 минут.
Я вернулся со 100%, чтобы переобоссать вас!https://ideone.com/Wfj6H2>>676270-кун
С этой уже определились.Какую следующей солвить будем?
>>676359Выбирай. Только посложнее что-нибудь.
>>676352Алгоритм уже не так красиво выглядит, как у >>675862-куна
>>679203У него тупо цикл, а у меня бинарный поиск, понятно что кода побольше.Ну так зато у него сложность O(nT), а у меня O(nlog(T)), где n - число школьников, а T - требуемое время.
>>679240Это как дергать гланды автогеном через анальное отверстие. В рассматриваемой задаче нахуй не нужно, на скорость не влияет, а на простоту понимания - еще как.
>>679322Идёт девушка, видит - парень косит траву в противогазе: - Ты что, с ума сошёл - зачем противогаз надел? - Я комсомолец - не могу без трудностей... - Кончай хуйней страдать, пошли лучше потрахаемся. - Хорошо, но только стоя и в гамаке...
Ну что же:http://www.e-olymp.com/ru/problems/32Мы предлагаем Вам похожую игру, в которой участвуют белая пешка и черный конь. Ходы делаются в соответствии с общепринятыми шахматными правилами. Белые ходят первыми. Белые побеждают, если они смогли провести свою пешку в ферзи и следующим своим ходом черный конь не может уничтожить ферзя. Партия заканчивается вничью, если очередь хода за белыми, но пешка не может продвинуться вперед. Если конь сумел побить пешку или ферзя, то выигрывают черные. Требуется выяснить исход партии при наилучшей игре с обеих сторон.Вопрос таков - что есть "наилучшая игра с обоих сторон", и как она определяется?В голову приходит разве что завершение игры через максимально долгое время. Правда, если проигравший так долго мог защищаться - выходит игра победившего была неоптимальной?
>>680226Хотя, походу наоборот - у коня дохуя способов походить, а у пешки - только вперед. Значит, оптимальный - думаю это когда конь натягивает пешку за минимально короткое время (поскольку пешка не может ходить неоптимально, у нее один путь)
>>680234> натягивает пешку за минимально короткое времяИменно минимальность времени в данном случае не важно, так как нужно сообщить результат, а не количество ходов. Тоесть для коня "наилучшей игрой" будет такая последовательность ходов при которой он берет пешку, если у него такая возможность есть. С ходами пешки не совсем ясно. Свой первый ход пешка может сделать как на одну, так и на две клетки. Следовательно для своей "наилучшей игры" пешка должна просчитать результат при первом ходе на одну клетку, и при первом ходе на две клетки. И выбрать тот вариант при котором она выигрывает. Если такого нет, то разницы что выбирать нет. Выбор есть только если пешка начинает со своей начальной по правилам позиции (второй ряд).
>>680243Я настаиваю на минимальности. Именно игра, которая закончилась минимально быстро - была оптимальной, кмк, так как конь может ее затянуть и просрать в итоге.Непонятно другое - на самом сайтеце есть два варианта развития событий для g3-a1, если пешка ходит на два хода - то ничья, а если один - то съедается конем. Казалось бы, раз пешка может сыграть вничью - то это и есть вариант когда оба играют оптимально. Но с какого то хуя там в результате программы стоит -1 - если выигрывают черные. Как это понимать?
>>680248Хотя, ашибочка. Анимашка с примером для пешки на g2, а там где пример входа и выхода - g3, все верно. А для g2 видимо оптимальна именно ничья.
>>680226Что делать, если пешка изначально на 8-й линии?
>>680317Очевидно, пешка побеждает.
>>680318Хотя, точнее - побеждает, если не находится под ударом коня на следующем ходу.
Сука, какое же говно эта ваша джава.Думаю, как организовать список результатов - нету в этой блядине ни Pair, ни Tuple.
>>680338http://ideone.com/ntTCDt
>>680350А где ее тип то задается? Я ожидал что то вроде Pair<int, double>.Мне вообще то список такой поеботы нужен. Впрочем, я уже плюнул и на кресты перешел.
>>680226CYKA BLYAT, ну и как это дебажить?
Тут такой интересный вопрос - а может ли пешка перепрыгнуть коня, если она стоит на начальной позиции?
>>680394Нет конечно.
>>680411Ты не понел - если конь стоит на следующей, а пешка имеет право в первый раз походить на 2 клетки?
>>680418> имеет право в первый раз походить на 2 клеткиТолько если обе клетки пустые. Пешка не может перепрыгивать фигуры.
>>680425Ну и заебок, это упрощает дело - меньше лишней поеботины обрабатывать.
Посоны, вроде сделал - кроме одного.Как там вход считать? На крестах?Ну как эту ебань g3 и a1 получить?
https://ideone.com/Miu6QCПодскажите, где я проебался?
>>680535Читай в строку. Потом проще всего будет сделать str[0] - 'a' и str[1] - '0' - получишь индексы. Это не сильно надежно, но для олимпиадки пойдет.
>>680560Да я так уже и сделал.Только блять, ищу что не так.
>>680554Родился хохлом.
>>680562В загон, быдло.
>>680566Не стукай, братишка.
>>680570Но я нихуя не ukraine, лол.Хотя и родился в Харькове. Но тогда был еще совок.
>>680561> так уже и сделалУ тебя там какая-то неочевидная хуита. Я бы работал не с координатами фигур, а с растоянием между ними (отдельно растояние по вертикали и по горизонтали) высчитаное из их начальных позиций. Дальше, пешка на каждом своем ходу (кроме первого) увеличивает растояние по вертикали на один. А конь может увеличить/уменьшить растояние по вертикали или горизонтали на 2 и одновременно увеличить или уменьшить растояние по другой координате на 1. Если растояние стало 0 по обоим координатам то конь победил, если один по вертикали перед ходом белых то ничья. Ну и нужно сначала высчитать ограничение по ходам, связаное с тем что пешка дойдет до верха.
>>680570там по умолчанию украха ставится
>>680573Не важно.Я тоже застрял на 97% верных ответов. Хочешь сгенерю ответы своей прогой для всех пар координат?
>>680588Я нихуя не понял.>У тебя там какая-то неочевидная хуита. У меня все очевидно - просчитываются абсолютно все варианты (их 6 штук примерно получается), потом они сортируются (сперва по номеру хода, потом по позиции), а потом берется первый из списка.Я думаю, что у меня проеб с сортировкой, т.е. с критерием "оптимальной игры обоих сторон"
>>680595Дохуя пар координат получается.
>>68059964*63 всего же
>>680601Блжад, если бы можно было из этой украинской ебани выдрать наборы данных, вызывающие неправильное поведение...Я надеюсь, там вход валидировать не нужно? Там, регистр к маленькому приводить?
>>680603Входные данные скорее всего верные.Наборы данных выдрать не проблема, но не хочу этим заниматься т.к. читерство.
>>680606Определенно, дело скорее всего в критерии "оптимальности".Подшаманил сравнение наreturn (a.second != b.second) ? a.first < b.first : a.first < b.first;Но чего то еще не хватает...
>>674231 (OP)Ебать, я даже условия не понимаю. Как вы это решаете, школьники?
>>675862Идея понятна, но я не врубаюсь почему это работает
>>680683Я же выше с рисунками даже блять логику показал, не?
>>680697Просто мне сначала показалось что это слишком наивное решение, которое завалится на каких ни будь изоощерённых тестах
>>680746Ну, не завалилось же?
>>680226Пришлось делать двумя разными способами чтобы отловить ошибки. Но я сделал это! https://ideone.com/V5zFocЧто, соснули, да? А? А?Ха-ха-ха, ещё как соснули! ( ͡° ͜ʖ ͡°)Пользуясь случаем передаю привет маме.
Этот кусок говна с тестами - неправильный.Конкретный пример - b6 c7. 30й тест ожидает что победят белые, хотя - хуй там плавал.b6b7 c7a6b7b8 a6b8 - только пешка прорывается в ферзи, как следующим же ходом ее срезает конь>Белые побеждают, если они смогли провести свою пешку в ферзи и следующим своим ходом черный конь не может уничтожить ферзя.
>>681001Кстати, раз пошла такая пьянка - я выдрал тесты, входные данные и результат. Они таки статические:g3-a1 = -1a7-a6 = 1a7-a5 = 1a7-a1 = 1a7-b5 = 1a7-c6 = 1a7-b8 = 1a7-c8 = 1a7-d6 = 1b7-a8 = 1b7-c8 = 1b7-b6 = 1b7-a5 = 1b7-c5 = 1b7-c6 = -1b7-a6 = -1b7-d7 = -1b7-g2 = 1b7-d3 = 1b7-d4 = 1b6-a6 = 0.5b6-c6 = 0.5b6-d7 = 0.5b6-b7 = 0.5b6-c5 = -1b6-d6 = -1b6-d8 = -1b6-a5 = -1b6-b8 = -1b6-c7 = 1b6-a7 = 1b6-a8 = 1b6-c8 = 1b5-a4 = -1b5-c4 = -1b5-d5 = -1b5-d7 = -1b5-c8 = -1b5-a8 = -1b5-b7 = -1b5-e4 = -1b5-f5 = -1b5-e6 = -1b5-h7 = -1b5-g8 = -1b5-g4 = -1b5-h5 = -1b5-d3 = -1b5-b3 = -1b5-c2 = -1b5-a2 = -1b5-g2 = 1b5-h3 = 1b5-d4 = 0.5b5-d6 = 0.5b5-b4 = 0.5b5-a5 = 0.5b5-e5 = 0.5b5-e7 = 0.5b5-d8 = 0.5a5-b6 = 1a5-c8 = 0.5a5-c6 = 0.5a5-b5 = 0.5a5-a7 = -1a5-a8 = 0.5a5-a6 = 0.5a5-h1 = 1a5-g1 = 1a5-f1 = 1a5-f2 = 1a5-g2 = 1a5-h2 = 1a5-h3 = 1a5-g3 = 1a5-f3 = 1a5-f4 = -1a5-e4 = 1a5-d4 = -1a5-d5 = 0.5d7-d8 = 0.5d7-b7 = -1d7-c6 = -1d7-e6 = -1d7-f7 = -1d7-e7 = 1d6-d7 = 0.5d6-b7 = 0.5d6-c6 = 0.5d6-e6 = 0.5d6-f7 = 0.5d6-g7 = -1d6-h8 = -1d6-f4 = -1d6-f5 = 1c6-a7 = 0.5c6-e7 = 0.5c6-d6 = 0.5c6-c8 = -1c6-g6 = -1g2-a1 = 0.5h2-a1 = 1h3-a1 = 1a2-a3 = 0.5b2-b3 = 0.5c2-c3 = 0.5d2-d3 = 0.5e2-e3 = 0.5f2-f3 = 0.5g2-g3 = 0.5h2-h3 = 0.5a2-b3 = 1b2-c3 = 1c2-d3 = 1d2-e3 = 1e2-f3 = 1f2-g3 = 1g2-h3 = 1h2-g3 = 1a2-a4 = -1b2-b4 = -1c2-c4 = -1d2-d4 = -1e2-e4 = -1f2-a2 = 0.5g2-a8 = 0.5g3-h4 = 1a2-b5 = 0.5b2-a5 = 0.5c2-d5 = 0.5d2-e5 = 0.5e2-d5 = 0.5f2-e5 = 0.5g2-f5 = 0.5h2-h5 = 0.5a3-a7 = -1b3-a4 = 1c3-d8 = -1d3-e6 = -1e3-c6 = 0.5f3-b6 = 0.5g3-c6 = 0.5h3-g4 = 1h3-h7 = -1
>>681001> b6 c7Игра же идет по правилам шахмат, пешка бьет коня. ШАХ И МАТ ОЛИМПИАДНИКИ
>>681007А, блять.В условии такой хуйни (что пешка может бить) - оговорено не было.Ну ок.
Фух, отладил. Заебался баги выцеплять.https://ideone.com/YKN6Dy
Какой у вас рейтинг на кодфорсес?
>>681228Лично я впервые услышал это слово месяц назад на дваче. Смотрел задачи прошедших контестов - за 2 часа могу решить 2, если повезёт - 3.
http://www.e-olymp.com/ru/problems/41Сап, друзья есть одна проблема, просьба рассказать алгоритм.
>>681543http://www.kursovik.com/programming/320360.html
>>681564Спасибо
Забавное наблюдение - если нарисовать матрицу смежности, то искомые группы образуют "ступеньки" на картинке, и графическое решение - поиск наикрупнейшего куска "ступенек".Подумаю, можно ли это использовать в алгоритме решения.
>>681757Если ты заштрихуешь главную диагональ, то тебе бросится в глаза кое-что другое - полностью заштрихованный квадрит в левом верхнем углу.Это более правильное наблюдение. Максимальная клика всегда выглядит как такой квадрат. Проблема в том, что строки и столбцы могут идти в любом порядке, и строки и столбцы квадрата могут быть разрежены полупустыми строками и столбцами.Просто найти такой квадратКогда квадрат выглядит вот так найти его сложнее. В реальности же там ещё и посторонний мусор будет Так что пиши Брона-Кербоша и не выёбуйся.
>>681777Бляяя. Ща оформлю.
>>681777Просто найти такой квадратxxxxxxxxxКогда квадрат выглядит вот такxx xxx xxx xнайти его сложнее. В реальности же там ещё и посторонний мусор будетxx x xx xx x xxxxx
>>681782Ну я собсно ща и проверяю, как оно будет выглядеть - рисую граф повыебистее, а номера позже порандомнее расставлю.>Так что пиши Брона-Кербоша и не выёбуйся.Я про эту хуйню всего лишь 15 минут назад на википедии вычитал. Выглядит слишком замороченно и дрючевно.У меня пока мысль попроще - начинаем со списка пар, как с минимальных групп размером 2.Каждую группу пытаемся "укрупнить", сканируя соседние вершины и ища такие, которые будут принадлежаьб каждой вершине в группе.И так до тех пор, пока не будет получаться увеличить список таких кусков. А дальше - дроп и выбор первого из крупных кусков как результата.
>>681526Как достиг такого навыка? сколько лет тренируешься?
>>681228Я доходил до 1593, потом все слил. Уже месяца два не пишу, ибо в школе напряги
>>681814В универе я осознал, что мне нравится писать проги для курсача по дискретной математике. Это было лет 7 назад. Потом решал головоломки и олимпиадные задачи из разных источников. Несистематично и с большими перерывами. Читал какие-то статьи про динамическое программирование.Недавно взялся за project euler, решил первые 100 задач, дальше пока ломает. Пару раз участвовал в Code Jam, проходил во 2-й раунд, но не показал особо выдающихся результатов.А вообще что такого в том, чтобы решить 2-3 задачи?Посмотри на http://codeforces.com/contest/631/problem/A и http://codeforces.com/contest/631/problem/BВ a сразу понятно, что l и r надо брать 1 и n. Остаётся в обоих массивах сделать OR всех элементов, и сложить два получившихся числа. 5 минут.В b нужно тупо смоделировать процесс. 10 минут.Остаётся время поковырять C.
>>681789>сканируя соседние вершины и ища такие, которые будут принадлежать каждой вершине в группе.Есть идея получше. Допустим ты начинаешь с полносвязного графа размера 1 - одной вершины.Ты берёшь полный список всех вершин, и убираешь из него все несвязанные с этой вершиной вершины.Ты получил список всех вершин, которые можно добавить к первой для получения полносвязного графа из двух вершин.Выбираешь очередную вершину, удаляешь из списка кандидатов все вершины, которые не связаны с новодобавленной. Снова в остатке получаешь список вершин, которые можно добавить к имеющимся 2 для получения треугольника.Это работает для любого числа вершин, что позволяет наращивать массив рекурсивно. И это эффективнее чем каждый раз пробегаться по всем вершинам, проверяя, связаны ли они со всеми уже включёнными в рассматриваемый подграф.Конечно надо как-то избегать ситуации когда ты будешь рассматривать одну и ту же комбинацию по несколько раз. К примеру ты начал с пары вершин 1-2 и нашёл, что её можно вырастить до 1-2-3-4. Когда ты начнёшь с пары 3-4 тебе не надо будет рассматривать возможность добавить к ним 1 и 2, потому что этот вариант ты уже рассматривал.Чтобы понять как это сделать полезно написать неоптимизированную программу, которая будет выводить список _всех_ клик в графе, а не только максимальных. Ну то есть если у тебя полносвязный граф из 5 вершин, то надо вывести 5 клик из 1 вершины, 10 из 2-х, 10 из 3, 5 из 4 и 1 из 5.Когда соединишь всё вместе получишь Брона-Кербоша.
_тест_тест__тест__
>>681996>И это эффективнее чем каждый раз пробегаться по всем вершинам, проверяя, связаны ли они со всеми уже включёнными в рассматриваемый подграф.Но я не собирался ни по чему пробегаться. Я собираюсь делать все на множествах. Там и циклов по сути никаких не надо, только объединения/пересечения.
>>682008Ясно.
>>682014Да не кипишуй ты, попробую.Всему свое время. Я пока ебусь с std-шными контейнерами. Раньше юзал Qt-шные, не думал что в голых крестах они такое говно, и что даже чтобы банально узнать, есть ли элемент в контейнере - надо ебаться с итераторами.
https://ideone.com/odyLzbПомогите найти, хуле этой гниде не так.Из 9 тестов на 1м какая-то "ошибка выполнения".Тестил на их примере, и на графе в 20 вершин-пикрелейтед(http://pastebin.com/AYyh68gU)
>>682294У тебя "ошибка выполнения", а не неправильный ответ.Возможно мер-хикка, а его друзья - аутисты.
>>681970ты крут!
>>682561Блять, а ведь и правда - прога сегфолтится на том единственном случае, когда k=0 и 0 пар, то есть реально одни хикки в друзьях.А хуле в таком случае должна выводить прога?
>>682565Собсно, у меня 3 варианта:1) нихуя2) 03) 01
>>682565Значит команда мера - один мегатащер.
>>682566>3) 0>1Блять, 1 1
>>682570this
>>682572Фак еа!После инпута надо было добавить/if (K == 0){std::cout << 1 << std::endl;std::cout << 1 << std::endl;return 0;}/
Это жадник. ОП хуй. Мимо проходил
>>682849Это вообще не задача рюкзака.Ее уже давно решили ИТТ.
>>681846Как смог дойти до такого уровня, как готовился?
>>682862Занимался. Решал. Ездил в соответствующие лагеря (гугли лкш). Ходил во всякие кружки при ИТМО ДС-2 - бояринИ везде решал как сучка. Практика - это главное
>>683086что можешь сказать о людях у которых рейтинг >2000? из моей мухосранской школы как минимум двое имеют звание мастера
>>683115Это либо ебаные гении, которые просто выигрывают всеросы по математике и заодно кодят по приколу. Либо хорошие учителя + море практики
>>683129а ты сколько времени потратил на это? если к примеру у меня по математике отлично легко, за сколько можно надрочиться?
>>683141С разной интенсивностью я занимаюсь уже третий год. Но я хуйней страдаю. Знаю много ребят, которые за календарный год добивались призеров на всеросе. Просто надо реально по этой теме угареть, и реально много работать + изначальный предрасположенности
>>683146Двачую этого, сам я говно, но знаю парочку кто добился, но там адовая дрочильня почти каждый день была. Честно говоря, лучше уж что-то более прагматичное дрочить каждый день, но не мне судить успешных людей, кек.
>>683265Какая разница, если доставляет? Меня уже не раз захватывал такой поток, что я по 8 часов нарешивал эти задачки, другой вопрос, что потом меня переклинивает и я за один присест в пределах суток прочитываю какую-нибудь книгу, а потом неделю бегаю по утрам, забиваю, начинаю кодить на жабе, забиваю, учусь писать декартовы деревья, читаю китайские публикации по биологии и так далее
>>683146тебе какие-нибудь книги помогли?
>>683457Очевидный Кормен очевиден. Шень неплох. В принципе годная книга - Реальная математика Грехэма, Кнута и Поташника
Посоны, есть задачка.На поле размером NxM клеток в точке (x0, y0) стоит робот, который умеет делать шаг на 1 клетку влево/вправо/вверх/вниз (по диагонали не умеет). Посчитать количество вариантов перемещения робота в точку (x1, y1) ровно за k шагов.Прелесть в том, что шагать робот может по одним и тем же клеткам несколько раз. И мой алгоритм тупо перебором не периваривает большие поля и ходы. А когда попросил данные для теста, то получил вот этоn = 100m = 100x0 = 50y0 = 50x1 = 60y1 = 60k = 200ответ = 3026331761191340503770893374595925277055394295450130902271922168548205308642694668236259320332359033488388961148337920время выполенния 5 сек. Судя по всему тут можно применить какие то формулы комбинаторики, но я них не силен.
>>683469Это банальной трехмерное дп
>>683470Хотя с такими числами... Не знаю. Но ты подумаю в сторону дп
>>683471Дабл Пенетрейшн?
>>683471Ну как я понимаю что я и решал динамическим программированием. Рекурсивно перебираю все воздожные варианты. И мой алгоритм работает, но с маленькими числами, а как его оптимизировать я не знаю, может есть в динамическом программировании какой то раздел. Просто в олимпиадном программировании я не силен.
>>683474Динамика - это рекурсия развернутая в рекурсивную формулу. Или попросту рекурсия с запоминанием. Подумай, как ты можешь для вычисления очередного ответа не заново всю рекурсию запускать, а лишь обращаться, например, к соседним клетка, и как-то использовать уже предпосчитанную информацию
>>683475Спасибо анончик, буду думать в этом направлении.
Вам тут по скольку лет? Вообще бывают олимпиадники в районе 30 лет?
>>683493Олимпиадники в районе 30 лет - это те, которые уже все выиграли, что могли, и теперь только могут учить остальных
>>683469>ответ = 3026331761191340503770893374595925277055394295450130902271922168548205308642694668236259320332359033488388961148337920Это шцтка юмора что ли? Что это за число ебаный в рот?
>>683506три дохуллиона двадцать шесть дохуллионов триста тридцать один дохуллион семьсот шестьдесят один дохуллион сто девяносто один дохуллион триста сорок дохуллионов пятьсот три дохуллиона семьсот семьдесят дохуллионов восемьсот девяносто три дохуллиона триста семьдесят четыре дохуллиона пятьсот девяносто пять дохуллионов девятьсот двадцать пять дохуллионов двести семьдесят семь дохуллионов пятьдесят пять дохуллионов триста девяносто четыре дохуллиона двести девяносто пять дохуллионов четыреста пятьдесят дохуллионов сто тридцать дохуллионов девятьсот два дохуллиона двести семьдесят один дохуллион девятьсот двадцать два дохуллиона сто шестьдесят восемь дохуллионов пятьсот сорок восемь дохуллионов двести пять дохуллионов триста восемь дохуллионов шестьсот сорок два дохуллиона шестьсот девяносто четыре дохуллиона шестьсот шестьдесят восемь дохуллионов двести тридцать шесть дохуллионов двести пятьдесят девять дохуллионов триста двадцать дохуллионов триста тридцать два дохуллиона триста пятьдесят девять дохуллионов тридцать три квинтиллиона четыреста восемьдесят восемь квадриллионов триста восемьдесят восемь триллионов девятьсот шестьдесят один миллиард сто сорок восемь миллионов триста тридцать семь тысяч девятьсот двадцать
>>681228А кодфорсес - это самая легитимная платформа?Вообще, посоветуйте, на какой платформе рейтинг подымать? А то я на каждой решаю по чуть-чуть и забиваю. Хочется зависнуть на какой-то одной.
>>683689тимус прорешивай. Решишь там 500 задач - красный на кфе обеспечен
>>683690Спс. Я где-то тоже слышал, что тимус - это самый хардкор.
>>683694Не хардкор, а реальные задачи. Вот на кфе задачи A и B div2 вообще смысловой нагрузки не несут
Школота, кто-нибудь на московскую городскую олимпиаду идёт? Сколько там времени даётся, сколько баллов надо набрать на призёра?
>>683474>динамическим программированием>Рекурсивно перебираю все воздожные вариантынет, это не дп>>683471>Хотя с такими числами...какими числами? ограничений на n/m/k нет; а с длинными числами нужна только операция сложенияhttps://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5решение дать, или подсказку?
>>683883>ограничений на n/m/k нетограничений на n/m/k в пасте не дано, потому я предоположил очевидноебыстро-фикс
>>683469Строй деревья, деревья сами себя не построят. Я бы просто обходил вглубь и останавливал ветку, если бы превышал длину пути.
>>683469Три слова: размещение, сочетание, перестановка. Пиздуй на википедию, выясни что эти слова означают и выучи три формулы.
>>683466Взялся читать Конкретную математику стоп, ты назвал её Реальная математика? ну ты лах, решил что буду решать все домашние и контрольные задачи. В результате пока не выполз из первой главы.Как-то хардкорно.
>>683883Давай решение или подсказку.>>683988Я же писал что в комбинаторике не силён. Подскажи формулу.
>>684110Дать решение? Простое что охуеть
>>683981Длинну пути я проверяю.
>>684117А деревья строишь?
>>684113Давай, если это решение не типа соснуть хуйца.
>>684110>>684113Не бери его решение, бери моё, оно быстрее!
>>684119Нет, я сразу путь считаю.
>>684121https://ideone.com/Y6yY6wНе знаю как 5 секунд, твой пример с дохуячислом у меня находится за 1,9 сек.
>>684123>сразу путь считаюЭто как?
>>684126Охуеть блять! А можешь пояснить что конкретно ты сделал? Это какая то байтоебская магия? Как это вообще возможно?
>>684141у тебя массив размера n x m x k — кол-во вариантов добраться до каждой точки используя пути соотв. длинытупо заполняешь егодинамика
>>684145Подскажи, где я проебался.У меня число чуток не то, что у ОПа - только первые 27 чисел сходятся из дохулиона.
>>684145>>у тебя массив размера n x m x k Почему именно такая длинна массива?
>>684159Потому что рекурсивная функция, которая принимает x, y, k.Нужна таблица, которая позволит сделать так, чтобы функция вычислялась только один раз.x и y меняются в пределях от 0..n и 0..n, а шаг - от 0 до к.Итак, количестко итераций снижается с дохулиона со 192 разрядами до 2х миллионов, что тоже дохуя, но уже приемлемо.
>>684167Я давно собирался вбросить решение, но через memoize! работало долго, уже k=100 считало секунд 10, а 200 считало бы час или полтора.Сперва пилил свою таблицу и свою мемоизацию (и заебся отлаживать), а потом нашел в документации, что memoize! можно размер таблицы прямо указать. И заебашил алиас на него>alias memstep = memoize!(step, 100 100 200);
>>684167А в твоем коде, ты просто заполняешь этот массив 1 и 0? И потом как то приобразовывается к целому числу?А еще, вот что делает этот кусок кода: return up + down + left + right;Он рекурсивно вызывает эти функции чтоли? Первый раз просто D разбираю.
>>684176>И потом как то приобразовывается к целому числу?Суммируется же.
>>684176>А еще, вот что делает этот кусок кода: return up + down + left + right;Да. Ну епт, вся прога строк 30 занимает - хуле там непонятно?Писал бы на крестах - строк 200 бы заняло минимум, а тут же и длинная арифметика есть в дефолте, и мемоизация.
>>684177>Суммируется же.Но даже если весь массив запонить 1. То сумма получится всего лишь 2000000 а не духуилиард.
>>684182С чего вдруг? Ты походу не вдупляешь, количество вариантов по клеткам в зависимости от k растет просто в ебанутой прогрессии.
>>684180Ну вот я пока и не пойму до конца, как этот алгоритм работает на D.
>>684184Выше же мне сказали что >>684145>у тебя массив размера n x m x k — кол-во вариантов добраться до каждой точки используя пути соотв. длинытупо заполняешь его
>>684188Да, но в клетках будут охуенно большие числа.
>>684188идея динамики:что бы прийти в клетку (x; y) с длинной пути z, нужно быть в одной из соседних клеток с длинной пути z-1
>>684191Вроде начинаю понимать, то есть в клетках будет вот эта сумма? return up + down + left + right;А что означет слово auto? В доках не нашел его что то.
>>684195auto значит "товарищ компилятор, мне лениво писать тип выражения - так что будь добр, угадай его сам"
>>684195>то есть в клетках будет вот эта сумма? return up + down + left + right;Да, верно. Каждый вызов ветвится на 4 по сторонам и суммирует результаты (но сперва смотрит, не обсчитывал ли он уже такой вызов).Когда k=0 - то если мы в искомой клетке - путь верный(1), иначе путь неверный (и нехуй дальше уменьшать k)
>>684196Анончик, ты охуенен. А как обычные ЯП обходятся без memoize? Оставь свой контакт какой нибудь, если я таки решу эту задачку, и меня возьмут на работу, то подарю любую игру в стиме/ дам на пиво/етц.
>>684200Или ты, я тут запутался, вас тут двое похоже.
>>684205>А как обычные ЯП обходятся без memoize?В лиспе memoize вроде есть или что то подобное.В обычных ЯП ты - сам себе memoize, и будешь делать это руками. Ну а тут оно просто есть по дефолту. Я просто обожаю дишечку - это как "правильные кресты 2.0">и меня возьмут на работуЭто что, для собеседования чтоле?>ставь свой контакт какой нибудьДа не вопрос. pinkierton@gmail.com
>>684210Блять, с разметкой обосрался.
>>684210Да, ты прав, в кложе есть меморайз попробую на нем сделать. А насчет работы, да я норм собеседование прошел, и в конце спросил, а мы что, строчки разворачивать не будем и попросил что нибудь на алгоритмы. Ну я думал будет что то типа найти в строке кол-во трех подряд идущих символов 'abc'. А мне дали эту залупу.
>>684217Залупа в принципе простая, я просто поначалу охуел от числа на 192 разряда.
Сука, как же хуёво жить в Крыму. Час назад написал последнюю строчку проги и в ту же секунду вырубили свет. Сейчас заново набираю по памяти.
>>684210uint k = 100;а вот этот к нигде не используется?
>>684246Ну, замени на uint k = 200 и подсунь в конец функции.Мне лень было оформлять это говно, так что все параметры я захардкодил.На сам алгоритм они не влияют, это организационные мелочи.
>>684248Да не, норм. Вроде переписал почти на то, что мне надо.
>>684252В лоб не переписывай, я где то проебался или опечатался.С твоим примером сходятся только первые 27 цифр (если он сам конечно без опечатки)
>>684248А если вот это переписывать вручну, то тут нужен будет трехмерный массив? Или как лучше по индексу к нему обращаться?memoize!(step, 100 100 200);
>>684261>А если вот это переписывать вручну, то тут нужен будет трехмерный массив?Я, до того как нашел, что memoize можно подсунуть размер хеш-таблицы - охуел от "быстродействия" и пытался напилить свою реализацию.Я делал одномерный, arr[mnk] c индексацией по формуле.
>>683689советую участвовать на кодфорсес и топкодер, пригодиться по работе может, а тимус это просто задачник с проверкой, знаю ребят которые прорешали 600-950 на тимусе и имеют на кодфорсес ранг Эксперт, знаю парня который входит в топ 10 на тимусе.
>>684244> ту же секунду вырубили свет. Сейчас заново набираю по памяти. для таких случаев надо иметь ноут
>>684270Для таких случаев надо иметь ИБП, или хотя бы спинной рефлекс делать сейв каждые 2 минуты. Ну впрочем дохуя ИДЕ делают это автоматически
>3026331761191340503770893374595925277055394295450130902271922168548205308642694668236259320332359033488388961148337920Здравствуйте, господин работодатель! Как я вижу вы догадались загуглить число, которое этому - >>683469 оболтусу для тестов.Эта простая мера позволила вам выяснить, что данный кандидат склонен к обману, а также с большой вероятностью - наркоман и извращенец (в этом легко убедиться если заглянуть в другие разделы этого форума).Могу только поапплодировать вашей преусмотрительности!
>>684325
>>683469В задачнике Меньшикова была такая задачка, посмотри. Там в оглавлении написано, где динамика, там и она должна быть.
>>684339Хуле смотреть, ее же уже заебенили.20 строчек на всю прогу от силы >>684126
>>684343Тупо трёхмерная динамика?А что за язык? Питон какой-то с встроенной длинной арифметикой?
>>684348Дишечка же.
>>684343Можно сделать производительнее, если рассматривать движения по x и по y отдельно. Я нафигачил свой proof of concept, но есть расхождение с ответом после 8 знака, и переполняет стек на ideone. Надо бы переписать на явное динамическое программирование.https://ideone.com/XZPGR5
>>684355Чуть ли не впервые слышу, честно говоря.Кто такая, чем знаменита?
>>683469Кстати тут непонятно, используется ли в координатах нумерация с 0 или 1.Пинки пай, ты оба варианта пробовал?
>>684359Поскольку никакой гугл, микрософт или еще какая хуйня ее не пиарит - она не знаменита.Вообще, язык, который должен был сделать с++ "с нуля" и избавить его от недостатков. Язык охуенен и я от него тащусь и ссу кипятком, собсно язык моей мечты. Но вакансий по нему нет.
>>684362>Кстати тут непонятно, используется ли в координатах нумерация с 0 или 1.Вот кстати, где то тут я и проебался, пока особо не искал.Мой ответ сходится только на первые 27 цифр. Или надо чего-то поправить и найти, или исходное число само с опечаткой.
>>684363Жаль, что так получилось.А каких именно недостатков?
>>684363У меня знакомый анимешник на нем кф-раунды тащит
>>684368Любых. Возьми любое говно из крестов, которое бесит - и тут ты его не найдешь.Например, тут нормальные шаблоны, я их просто беру и пишу (а в крестах ниасилил). Тут нормальные строки, а не 9000 велосипедов. Тут нормальная блять стандартная библиотека (что заметно, для этого примера я просто заюзал мемоизацию и длинную арифметику, а не велосипедил их). Особо охуенные тут слайсы, аналогов в других языках не видел.По сути, основная идея такова - язык быстрый и нативный, есть сборщик мусора, но возможность пердолиться с указателями никто не отбирал.Есть указатели, есть маллок и фри, в стандартной библиотеке есть и весь сишный апи. И вообще она спокойно юзает либы от крестов и си.Долго объяснять короче, язык моей мечты, рили.
>>674231 (OP)Зашел я значит вот сюда http://acm.timus.ru/ranklist.aspx и мой пердак улетел в стратосферу.
>>684381Я нихуя не знаю из вышеперечисленного, ибо школьник.А так ли это важно, что есть в стандартной библиотеке? Нельзя что-ли не стандартную библиотеку с длинкой подключить?
>>684388Можно. Все можно.Но когда нормальная стандартная библиотека - ты просто решаешь задачу и занимаешься ей, а не еблей с языком. Вон, сколько у крестов строк? сишные ака "хуйня из указателей" - раз, std::string - два, QString - три, вроде в OpenCV тоже что то было...Заебывает, честно.
>>684387Чому?
>>684387я из этого списка знаю парня
>>684357>Можно сделать производительнееНу, не знаю как запустить грувипрогу на своем компе.Но на моем пример с оповскими данными у меня считается меньше секунды при ограничении в 5 секунд.>но есть расхождение с ответом после 8 знакаУ меня первые 27 сходятся. ХЗ, почему не все - вроде должно быть все правильно.>и переполняет стек на ideoneЯ как то логарифм от факториала пытался на жабе посчитать и охуел - жаба то, в отличии от дишечки, не оптимизирует хвостовую рекурсию, и на 15000 вроде у меня тоже стек распатронило на ровном месте.
>>684478Если на пальцах - есть минимальное число ходов, требуемое чтобы из (x0, y0) прибыть в (x1, y1), и есть некоторый излишек.Рассматриваем все варианты распределения этого излишка между ходами по горизонтали и вертикали. Для каждого считаем количество вариантов. Результаты суммируем.Как считаем:Допустим ходов по горизонтали X, а по ветикали Y. X + Y = k.Рассматриваем одномерную задачу для x: сколько есть способов добраться из x0 в x1, не выходя за пределы [0..M-1].Рассматриваем одномерную задачу для y: сколько есть способов добраться из y0 в y1, не выходя за пределы [0..N-1].Посчитали? Отлично. Остаётся посчитать, сколько есть вариантов соединения одного с другим для получение уникальных путей в 2d сетке.Впихнуть в последовательность из k ходов X горизонтальных ходов без учёта порядка можно C(X, k) способами.Результат = горизонтальное x вертикальное x С(X, k).
>>684499Твой метод я вроде понял (только не понимаю, почему это должно работать).Хуле, щас попробую реализовать. Затестю и результат, и скорость.
>>684652Это что за язык?
>>684652А что “зачем”? Я этих ваших грувей не знаю, их цомпелятора у меня нет.И какая разница, если код - абсолютно такой же?
>>684660Очевидно, первый пик - Ди, второй - Groovy.
>>684660
>>684660Код-то один, а вот результат-то разный
>>684663И результат такой же, я просто с условиями химичил после.Там >=0 и <m должно быть. Форкни и проверь.
И да - как запустить эту грувипрогу в терминале, имея бубунту?Хочу сравнить скорость.
>>684664
>>684664Форкнул - https://ideone.com/2YW0d1Получил результат3026331761191340503770893373029273844677591368122716618704642247067326254159330908652193057324457123166746681628950720Всё ещё не сходится с3026331761191340503770893372888058869422738484032331390788387569021838371831280294822254761283098828539404148603710720
>>684668Расслабься.У источника данных вообще 3026331761191340503770893374595925277055394295450130902271922168548205308642694668236259320332359033488388961148337920.И у тебя, и у меня с ним сходятся только первые 27 цифр.Такое ощущение, что везде реализация BigInt - сродни флоатам и накапливает какую-то погрешность.
>>684669У меня мир рушится, а ты говоришь расслабся?!>>684665Для начала сделайsudo apt-get install groovy2
>>684670>У меня мир рушится, а ты говоришь расслабся?!Как мы заметили, на абсолютно одинаковом алгоритме могут быть отличия в цифрах. И твой, и мой сходится с тестовым на первые 27 цифр (причем мой сходится ближе, азаза).Вывод1: как минимум 1 из наших ответов неверен.Вывод2: оповское тестовое значение также может быть неверным.Поскольку алгоритм явно одинаков, сколько там получилось - не столь важно (один хуй с таким числом - столько атомов во вселенной не наберется)
>>684670>sudo apt-get install groovy2Ну допустим сделал - а дальше то что?
>>684673groovy test.groovy
>>684674Ну ты пастебин то скинь.хуле я со скриншота набирать буду?
>>684676Так я думал ты хочешь замерить перформанс первой моей версии - >>684357Ну ок. Кинул тебе на пастебин, проверяй http://pastebin.com/UsRpiM2b
>>684677Первую версию я хотел утрецом переписать на дишку, и сравнивать уже сравнимые вещи.Один хуй я этих грувей не знаю.
>>684677org.codehaus.groovy.control.MultipleCompilationErrorsException: startup failed:/home/wolph/workspace/robot/test.groovy: 1: unable to resolve class groovy.transform.Memoized @ line 1, column 1. import groovy.transform.Memoized ^1 error
>>684679По ходу у тебя вызывается первая версияgroovy -vпоказывает 1.8.6? Тогда делайsudo apt-get remove groovy
>>684680 После этого должен остаться пакет groovy2 и команда groovy test.groovy должна работать.
>>684681Работает.Но дишная версия ощутимо быстрее.
>>684683Ты замерял время старта JVM.Юзайprintln System.currentTimeMillis()...println System.currentTimeMillis()Но вообще оно и должно быть медленнее на одинаковых алгоритмах. Типизация то типическая.
>>684685 То есть динамизация типическая. То есть... Ну ты понял.
>>684687Ну да, понел.Померял - 3421 мсек.
Надо будет с утреца заняться хуйней и попробовать переписать это на чистом лишпе. Там, если вики не пиздит, и мемоизация встроена, и числа - длинные по дефолту.Интересно, какой там результат будет, лишпу все таки несколько десятилетий и ему я доверяю.
http://pastebin.com/E096Qgru
>>684713Моя первая прога на Хаскелле. Прям чувствую, как передо мной распахнулся мир пандорических захватов, монадических трансформеров в категории эндофункторов, кластеров метапарадигм, зигохистоморфных препроморфизмов наконец.
>>684713>solve :: Int -> Int -> Int -> Int -> Int -> Int -> Int -> IntegerСука до слез
>>684672>Вывод2: оповское тестовое значение также может быть неверным.Возможен и такой вариант, так как у меня точно такое же значение как и у вас получается3026331761191340503770893372888058869422738484032331390788387569021838371831280294822254761283098828539404148603710720
А можно ли за год надрочиться чтобы решать div2 A и div2 B?
>>684890
>>684772Блять. Попытался переписать на язык смайликов не зная его, и обосрался.Может подскажете чого не так?http://pastebin.com/6xGZSze4
>>684890Смотря что у тебя с математикой. Если в вузе получал пятёрки, то можно.Сначала надо прорешать стандартные задачки по дискретной математике.Сделать обязательные мелочи типа перевода между произвольными системами счисления и генерации чисел-палиндромов. Не помешает самому написать длинную арифметику.Вникнуть в трюки с побитовыми операциями, тут подойдёт http://www.hackersdelight.org/Сделать поиск анаграмм методом "с размахиванием руками".Потом пишешь решето Эратосфена и факторизацию чисел, задачки на линейное программирование (начни с задачи о том, сколькими способами можно разменять энную сумму заданными купюрами).Обход графа в глубину и в ширину, поиск кратчайшего пути, минимизация потока. Всё это для графов, представленных разными структурами данных.Пишешь решалку судоку и непобедимый алгоритм для крестиков-ноликов миимаксом.Проникаешься основными формулами комбинаторики, пишешь свою небольшую либу для получения всех сочетаний, перестановок и размещений для заданного множества.Особое внимание уделяешь рекуррентным формулам для возведения в степень n, вычисления чисел Фибоначчи и Каталана, коэффициентов бинома Ньютона. Задачка Иосифа-Флавия сюда же.Теория чисел нужна на уровне алгоритма Эвклида, генерации пифагоровых троек, формул для "многоугольных" чисел, сумм полиномов для аргументов от 1 до N, нахождения периода десятичной дроби, полученной в результате деления двух чисел и наоборот.Когда освоишь это надо просто нарешивать задачи.
>>684985Какой диалект и как запустить?
>>685060Сохранил твой пост, добра тебемимо-пробегал
>>685060матан было 4, но я филонил, линейка, геометрия, тервер, матстат - отлично, в школе был по математике лучше тех ребят что ездили на финалы acm
>>685060Спасибо тебе. Вот ты так расписал все подробно, сколько лет тебе? Какие достижения в программировании?
>>68514826 лет. Никаких достижений тащемта нет. В шараге где я учился никто подготовкой олимпиадников не занимался. Жаль конечно.Это хобби у меня такое - решать головоломки и олимпиадные задачки по программированию.Решённые задачки я складываю в большой чёрный пакет облачную папочку. За год больше сотни набирается.Когда писал пасту я открыл эту папочку и пробежался по решениям. В пасту включил знания, требуемые для решения типовых задач.Учитывай что это начальный-средний уровень. В этой пасте даже китайской теоремы об остатках нет.
>>685063Common LispЯ на бубунте запускал REPL и копипастил по строчкам, gcl
>>685237Пробовал в Гугл Код Джэм?
http://hecs.info/Что скажете, атлеты?
>>685638Щито это?
>>685640Не знаю. Что-то вроде руководства к действию, наверное. Я вообще у вас спросил
>>685641Ну хер знает, я ничего не читаю, а решаю велосипедно "как в голову взбредет".
>>685642И как решается? Сколько на кфе?
>>685642Кстати, всякие жуткие структуры данных тебе тоже в голову сами приходят?
>>685643>Сколько на кфе?Не знаю, что это и где. Я несколько дней назад вкатился
>>685644Это какие такие?
>>685651Навскидку декартовы деревья, многомерные деревья декартовые, деревья отрезков с модификациями, суффиксные деревья, много их
>>685655А никак. Я всей этой ебани не знаю.Хуле, вкидывай задачу, где оно применяется.
>>685662http://neerc.ifmo.ru/school/archive/2014-2015/ru-olymp-regional-2015-day1.pdfТретья, с прошлогоднего региона
>>685670Ты ничего не путаешь? 3-я задача решается в лоб.
>>685679С полными ограничениями она решается декарткой или корневой декомпозицией и никак иначе
>>685682Хуле, вот и попробую.
>>685683Иди сначала почитай про сложность по Колмогорову
>>685685Нахуя? Вот упрусь в какую непреодолимую хуйню в процессе решения - тогда и пойду гуглить и читать.Где можно найти пример входных и выходных данных? Я имею в виду - именно ебического размера, а не тот крошечный?
>>685682В чём подвох? В том, что в список делаются вставки, и надо использовать линкед лист, а по нему доступ стоит O(n)?
>>685687http://codeforces.com/gym/100586Здесь можешь ее попытаться сдатьИли выкачать архив тестов отсюда:http://neerc.ifmo.ru/school/archive/2014-2015.html#region>>685690Да, Декартово дерево в среднем дает нам асимптотику логарифмическую + выигрыш по памяти
>>685691Ну хуй знает, я бы наверно навелосипедил ещё один двусвязный список, в котором хранил бы ссылки на каждый скажем 300-й элемент основного. И апдейтил бы его хвост после каждого эвента.Или можно сделать по-другому. Держать значения в массиве, отдельно мапу для добавляемых значений и таблицу поправок вида"начиная с 12345-го индекса индексы занижены на 1"Когда таблица будет слишком разрастаться, создавать новый массив со всеми поправками и добавлениями.Если писать на сишке вполне можно и уложиться в секунду.
>>685713Во-во. Вот, я думаю, в конечном итоге этот "велосипед" и будет похож на это самое говнодерево.
>>685713Не отрицаю, что такое шаманство может зайти. Но декартку проще и очевиднее было написать
>>685713Подумал немного над этим велосипедом... Можно сделать лучше. Не привязываться жёстко к каждому k-му элементу, а просто хранить лист структур (указатель на начало диапазона, количество элементов в диапазоне).Если диапазон слишком разрастается - дробить его на 2, стал слишком маленьким - соединять с соседом (и сразу дробить на 2, если получился переросток).Ничто не мешает сделать эту индексную систему многоуровневой. Жопой чую, что можно добиться логарифмического времени доступа в худшем случае. Надо будет внимательно посмотреть на худшие случаи с переполнениями и недонаполнениями, задевающими сразу все уровни.Получается эдакое дерево, упавшее на бок и попиленное лесорубами.
>>685716>декарткуниасилил причем тут декартово деревов моем понимании, для каждого узла будет {кол-во элементов в левом поддереве, сумма квадратов длин листьев (= сумме этого элемента левого и правого поддеревьев), высота (для балансировки)}соотв. O(k ∗ log(n))
>>685752Всё конечно же изобретено до меня - https://en.wikipedia.org/wiki/Skip_list#Indexable_skiplistК сожалению не могу найти ничего про его большое О на удаление/добавление.
>>684985http://pastebin.com/ZmKktwuaubuntu@ubuntu-VirtualBox:~$ time clisp test.cl3026331761191340503770893372888058869422738484032331390788387569021838371831280294822254761283098828539404148603710720 real 1m30.980suser 0m18.352ssys 0m2.264s
Пацаны, кто вккап пишет сейчас?
>>686233смотрю квалификацию, чувак из моей школы уже решил все задачи
>>686297У меня тоже некоторые знакомые все порешали. Я туплю над третьей, одно левое решение уже заслал
>>686303у тебя какой рейтинг?
>>686391Сейчас под 1400, добивался почти 1600
>>686233Короче первое место займут ребята из УрГУ или Китая
>>686396давно тренируешься? какое образование?
>>686398Вккап - это только для русских. Первое место займет Коротткевич с Бардашевичем (subscriber и tourist)
>>68640210 класс, про олимпиадное программирование знаю с 8. Большую часть времени страдал хуетой
>Я подтверждаю, что мой возраст не менее 14 и не более 23 полных лет в настоящий момент.
>>686418Тебе 12?
>>686420Да.
>>686418ты старичок как и я наверно
>>686403Я туриста как то не заметил, так то да, турист первый будет
Что-то затупил. Надо было Абу_team создавать и решать всем двачем
>>686425На самом деле не вдупляю, как можно быть Геной. Он же все нахуй решает
>>686431Я когда увидел рейтинги топов на кодефорсес долго истерически смеялся.Они заявляют, что их система рейтинга подобна ЭЛО.В шашках, шахматах, и тому подобном говне топовые игроки имеют ЭЛО рейтинг 2500-2700. А тут 3850. Пиздец.
>>686441>говнеТащемта не везде http://www.goratings.org/От способа расчета зависит
>>686509Не понял, бля, а где русские?
Сколько у кого задач и рейтинга на тимусе?
>>686431ну так парень с 5 лет кодит, я про код до 27 лет и не слышал даже
>>686766у меня 2 задачи решено, парень из моей школы на первой страничке светится, потом еще парень из школы в топ50
>>686794Что за парень-то в топе?
Посаны, подскажите.Бинарный поиск работает по отсортированным массивам. А можно написать вменяемый бинарный поиск через рекурсию который работает и с развернутыми массивами?Допустим, есть [1,2,3..n] как arr и возможен также [100,99,98..n] как аргумент, надо чтобы нашло индекс в обоих случая.Конечно проверить в тупую массив и написать две ветки через if я додумался, но может есть какое-нибудь более элегантное решение, чтобы не городить лишнюю кучу кода? нюфак в этих ваших алгоритмах и задачках
>>684985Уважаю братишка. Вот мое решение на кложе https://ideone.com/LVX5ng
>>687644Бинпоиск работает на монотонных последовательностях
Расскажите свои истории успеха, как пришли к олимпиадам, как трудились чтобы достичь высот?
>>688634Лет 8-9 назад училка по информатике потянула на городскую коколимпиадку по погромированию. Не трудился.Эээ, все.
>>688669И что дальше было? Сейчас что с тобой?
>>688701Ничего. Потом я пошел в вузик. Но вузиковскую олимпиадку по кокограммированию я засрал, ибо там скорее всего был сговор - по правилам на отбор должен был отводиться час, а нам дали полчаса и по листку бумаги с заданием, которое (как я уже вспомнил на 3м курсе, когда у нас пошла комбинаторика и матстатистика) - вообще не имело ничего общего с программированием, а по сути это была формула из комбинаторики. Ну, разве что реализовать "функцию факториала" для нее, лол.После вузика 2 года поработал, заебало, уволился, сычую.
>>688705тебе 24? какие планы сейчас, гугл код джэм будешь пытаться? я вообще в школе не знал о программировании, хотя на олимпиадах по матеше уделывал парня который сейчас уже и гугле и фейсбуках поработал
>>689046>тебе 24?Да. Скоро 25.>какие планы сейчасНикаких. Попроебываюсь, поучу алгоритмы (работал погромистом, но по образованию я инженегр и самоучка - так что теоретические основы у меня хромают). Права получу, пузо сброшу, ремонт сделаю, отдохну нормально.А потом поищу работу получше.
Как такое решать?
>>689673Где ограничения и как проверять?
>>689685http://codeforces.com/contest/644/problem/A
>>689673>>689691Сука, нельзя, бля
>>689673Достаточно минуту порисовать на листочкеБывший_цвета_морской_волны - кун
>>689673шахматная раскраска
>>689870Ну, пиздец. Сказано же не обсуждать нигде. Ты мне еще вторую тогда оттуда реши, бля
>>689873да похуй мне бля, щаз решу
>>689911обычная линеечка, хуйле
>>689914Лично я уже минут 30 потею. Тяжело думать что-то
>>689873да всем похуй, все равно те кто обсуждает нихуя не смогут
вообще эти задачи за 10 минут все решаются опытным олимпиадником 14ти лет
>>689914Лол, умудрился тл схватить. Вот же ж я тупой
>>689953Теперь ошибка на претесте 4. Я ебал
Если я начал изучать программирование в феврале, и до сих пор не могу решить див2а и див2б, то это значит что я совсем тупой?
>>689925рацетамы пропей
>>689974Это значит, что ты мало занимаешься
>>689977нужно больше, по 8 часов в день? стоит ли это делать каждый день или как в кружках 2 раза в неделю?
>>689983Еще раз, что ты можешь решить, а что нет?На каком языке пишешь?
>>689988прохожу курс с++ на яндексе, в курсе какие-то задачи могу решить, какието нет, на кодфорсерс не могу решить ниче пока
Посоны, где можно разбор задач с ИОИП посмотреть? А то что-то ничего не могу нагуглить.
>>690949http://informatics.mccme.ru/course/view.php?id=117
>>691003Там только у одной задачи разбор.
>>691016Посмотри, может на кфе топики есть
>>691022Там ничего нет или я плохо ищу.
>>691075Печаль. Официальных разборов, насколько я знаю, нет
Не олимпиадная задача, но вы тут любите алгоритмы подрочить, так что спрошу.Есть набор точек вида (широта;долгота). Нужно придумать как находить точку в этом наборе, ближайшую к заданной (не из набора), быстрее, чем за линейное время.Например, есть координаты всех макдональдсов, и нужно найти ближайший к юзеру, даже если юзер посреди Антарктиды.Для плоскости есть quadtree, а вот как сделать что-то подобное для сферы - ума не приложу.
>>691176А чем плоскость от сферы то отличается?
>>691177Тем, что тривиально делится на куски одинаковой площади и формы.
>>691179Ну представь, что твой шарик - это прямоугольник. Развертку глобуса не видел?Ну, будут куски не одинакового размера - и поебать, все равно в антарктиде макдональсов не шибко много.
>>691181Не катит. Макдональдсы только для примера.Если бы такое решение подходило - взял бы геохеш и не парился. Но, во-первых, в полярных широтах размер кусков сильно отличается от экватора, во-вторых, кратчайшее расстояние вообще может идти через полюс и развертка отсасывает.
>>691198Чем блять не катит?Нарезаем шарик на куски, каждую точку пихаем в соответствующий кусок. Итого - чтобы искать ближайшую мы перебираем расстояния только точек в текущем куске, а не на всем шарике. Куски можно делать многоуровневыми - большой кусок включает в себя куски поменьше и так далее - получится сорт оф дерево.Не сомневаюсь, карты ИРЛ как-то похоже и работают.
Посмотри на карту. Что ближе всего к Хельсинки: Улан-Батор, Анадырь или Нью Йорк? По развертке хуй скажешь, что Анадырь.Карты работают в самом деле так, но только потому, что подобные задачи на практике всегда ограничены относительно небольшой территорией, в рамках которой кривизной Земли можно пренебречь.
>>691214>что подобные задачи на практике всегда ограничены относительно небольшой территорией, в рамках которой кривизной Земли можно пренебречь.Ну вот - а в твоем случае разве не так? Что у тебя за задача такая?
>>691219Нет, в моем нельзя, решение должно работать для всей Земли. Задача с авиацией связана.Сейчас работает полным перебором, но банально интересно найти оптимальное решение для общего случая.
>>691230По какому количеству объектов идет поиск?
>>691176>Для плоскости есть quadtree, а вот как сделать что-то подобное для сферы - ума не приложу.Да точно такое же рекурсивное разбиение пространства. Наиболее безгеморройный способ - взять octtree и отобразить широту и долготу в [x;y;z] на сфере, так как минимальное расстояние по поверхности сферы будет соответствовать минимальному же расстоянию по хорде.
>>691176http://kerbalspace.tumblr.com/post/9056986834/on-quadtrees-and-why-they-are-awesomeНу или нарезай икосаэдр https://en.wikipedia.org/wiki/Geodesic_grid
>>691176Ну, я слышал, что для поиска кратчайших путей алгоритм есть. Дыйкстра, как-то так
>>691214Ну и получишь ты Улан-Батор, Анадырь и Нью Йорк. Потом пройдёшься по ним, посчитаешь расстояние и выберешь наименьшее.
>>691358Как понять сколько ближайших точек надо набрать прежде чем выбирать из них наименьшее?
>>691244> минимальное расстояние по поверхности сферы будет соответствовать минимальному же расстоянию по хордеНе подумал об этом. Ты прав, это выглядит как самое простое решение. Спасибо.
Подскажите, как решать. Не могу понять как записать условие, как соотносятся i и j каждого элемента
>>691913m[j] == abs(i - j)
>>691916поясни, пожалуйста, что такое m[j] и что такое abs, а то пока такого не объясняли еще на курсе
>>691929>такое m[j]это сожранное вакабой m[і][j]>absмодуль числаhttps://ru.wikipedia.org/wiki/%D0%90%D0%B1%D1%81%D0%BE%D0%BB%D1%8E%D1%82%D0%BD%D0%B0%D1%8F_%D0%B2%D0%B5%D0%BB%D0%B8%D1%87%D0%B8%D0%BD%D0%B0
>>691956Спасибо, ты просто мегамозг! Жаль что у меня нет таких друзей программистов
>>691960Здесь все твои друзья
>>696330Наверное нужно начинать просмотр с первого элемента, если он не равен искомому то потом смотреть второй, потом четвертый, потом восьмой - пока не получим элемент больший искомого, и дальше бинарный поиск на последнем отрезке.
Вопрос олимпиадникам: бывает ли у вас, что вы дропаете задачи, так и не решив, и переключаетесь на другое?
>>696415Ну да. Все так делают время от времени.
Расскажите про Кодефорсес. Когда там контесты? Там всегда правила, что сначала задача больше баллов стоит, чем потом? Насколько сложные задачи? Какой рейтинг там -- ето крута?
>>696738Контесты на главной странице вывешиваются объявы, бывает что несколько за неделю. Про баллы не очень понятно, я сам не умею решать, но видел как в разные контесты у человека вычиталось за 2 решенные из пяти, а в другой контест например за 2 решенные прибавлялось. Еще вычитают если ты одну задачу несколько раз отсылаешь неверное решение. Крутой рейтинг начинается думаю с Эксперта. Ниже Специалиста наверно зашквар.
Я ньюфаг, записался в ВУЗе на курсы, щас тренируют на acmp, говорят, что потом нужно на Тимус с Кодфорсами переходить. И у меня возник вопрос: какова сложность задач на олимпиадах (на том же acm) по сравнению с acmp? Если я решаю на acmp задачи сложности 30-40% это же все хуйня по сравнению с олимпиадами?
Ребята, вот эта задачка совсем начальный уровень считается да?
>>701379Да, легче уже ничего нет.
>>701379Ультралегкая
>>701379Нихуя. Мне за эту задачу на собеседовании Senior Ruby Developer дали.
>>701454>>701456>>701610решение написали быстро
>>701111бамп вопросу
>>701829
>>701829ИЗИЗИhttps://ideone.com/OT04ZM
>>701111Ну так возьми да посмотри задачки предыдущих олимпиад.
>>701871Ух ты, какой лвл? За какой срок научился так решать?
>>701897>>685237Изначально решение выглядело проще, но длиннее. Я решил его вручную пообфусцировать в целях траллинга.
>>701915Участвуешь в асm-тусовке?
>>702190Нет.
Бумп
>>701879Смотрел. Для меня сложно. хочется поставить какую-то конкретную планку сложности задач, которую я должен уметь выполнять.
>>702780Расскажи как вас тренируют, и какие достижения у тех, кто это делает? Какой город?
Есть такая структура данных, которая мне быстрее, чем за линию уменьшит значения части элементов массива на 1?
>>704503
>>704503Последовательной части?
>>704503Формально нет, а так любое дерево с операциями над подотрезками: дерево отрезков, декартово дерево и тд. Уменьшают за логарифм, используются когда тебе надо сначала провести много операций и потом вывести ответ. Один элемент берётся за логарифм.Также есть более простая штука, sqrt-декомпозиция, как бы дерево всего с 2 уровнями, соответственно по sqrt(n) потомков в вершине. Принцип тот же самый, что и выше, только изменение отрезка работает за корень, элемент берётся за единицу -> можно часто брать отдельные элементы.
>>701379Нам такое в школе в 9 классе давали не траль, я тогда очень долго пыхтел
>>704665Я тогда написал через конечный автомат, не зная что такое конечный автомат, лол.
>>704689Ах да, по условию за О(n * m)
>>704690А по памяти сколько? Можно же тупо массив заполнить, а потом выводить.
Вот, например, задача на КФ. Вчера начал решать, сделал через рекурсию, но то и дело ловил WA и потом TLE. Через часов 5 сдался, спиздил решение у красного. Но чтобы только понять его решение, потратил час. Сейчас проснулся и пытаюсь по памяти воспроизвести его алгоритм (пока WA). Вот скажите, как можно сразу учитывать все corner-кейсы и ебашить идеальное решение?
>>705021Хм, а какие там крайние случаи? Мне видится, что задача решается за линию скользящим окном.
>>705043Мое первое решение и было окно. Мало того, что надо учесть все выпуклости, так еще и по времени оно не проходит, как оказалось.
>>705052И за линию окном никак. Отсечешь правую часть, а она может входить в решение, и наоборот. То есть надо делать два слайса: [left, right-1] и [left+1, right]. Рекурсия даже с сохранением значений не прошла.
>>705060Непонятно, там же по идее надо жадно брать возрастающие элементы, как только встретится невозрастающий, запоминаешь его. Дальше, когда встретится следующий невозрастающий, то смотришь, что уже получилось и обрезаешь по первому невозрастающему, ну там около него. Разве не так? Там несколько случаев, правда, получается, какой из элементов увеличивать/уменьшать, но вроде вполне реализуемо.
>>705060Находишь в массиве все возрастающие отрезки, включая участки длины 1.Заносишь их границы в список вида [[1,3], [4,4], [5,10], [11,12], [12,12], ...]Проходишься по списку отрезков, проверяя, можно ли склеить текущий отрезок с последующим изменением последнего элемента текущего отрезка, или первого элемента следующего.Если следующий отрезок имеет длину 1, то надо также проверить, можно ли его изменить так, чтобы склеить текущий отрезок со следующими двумя.После каждого удачного склеивания проапдейтишьь максимальную длину.
>>674231 (OP)>i-ый участникКак это читается?
>>705091итый
>>705084>Если следующий отрезок имеет длину 1, то надо также проверить, можно ли его изменить так, чтобы склеить текущий отрезок со следующими двумя.Это не надо, затупил чёт.
>>705084Дьявол в деталях.Имеем массив [1, 3, 4, 3, 4].Два возрастающих отрезка - [1,3,4], [3,4]. По твоей логике, изменив [1,3,4] на [1,3,2], его можно будет склеить с [3,4] и получить [1,3,2,3,4] длиной 5.
>>705081Запомнил i1, i3, i6. Увидел i7, посчитал длину i1-i6 и отбросил i1, ок. Но i1-i6 - невалидный отрезок.
>>705021В общем, вот ссылка, чтобы не теоретизировать, попробуйте заслать свое решение. http://codeforces.com/contest/446/problem/A
>>705099Ну понятно, что если мы хотим поменять элемент на позиции fixIdx, то надо проверять, что array[fixIdx+1] - array[fixIdx-1] >= 2boolean isMergeable(range1, range2) { assert range1.end + 1 == range2.start if(range1.start == range1.end || range2.start == range2.end) return true //пробуем поменять конец первого отрезка if (array[range1.end + 1] - array[range1.end - 1] >= 2) return true //пробуем поменять начало второго отрезка if (array[range2.start + 1] - array[range2.start - 1] >= 2) return true return false}
>>705116Вроде нормально. Попробуй заслать полное решение.И потом скажи, смог бы ты без подсказок сразу написать идеальное решение, прошедшее бы с первого раза.Задача, судя по рейтингу А, легкая. Но вот как замечать такие штуки, это ппц. После часов отладки они уже бросаются в глаза, но не сразу же. По идее она должна решаться за 5 минут.
>>705134Мне лень.
>>705134Решение красного было примерно таким: завел 2 вектора, в одном хранил числа, в другом - индексы предыдущих фейлов. Потом для каждого i смотрел предыдущий и предпредыдущий фейлы. И в зависимости от проверки вроде той, что выше, выбирал нужный отрезок от i до первого или второго фейла и обновлял максимум.
>>705146По идее можно было бы вообще без второго вектора, тупо 2 переменных.
>>705146На скриншоте олимпиадники as is. Попизди еще, что олимпиадники - элита программистов.
>>705146Блять. Что тут написано то? Это на конкурс обфускции должно пойти. Одноразовый код
>>705108В смысле, понятно, что так делать не надо. Тебе надо хранить текущий уровень, а не просто смотреть на предыдущий элемент, тогда тебя стопорнёт ещё на 5 элементе.
>>704690>>704665Вам в 9 классе давали О-нотацию?
И как же я завидую успешным олимпиадным задротам
>>705390Да, была, не на продвинутом уровне, конечно. Просто примерное представление о зависимости времени работы от входных параметров. Вот когда после 10 класса нам рассказывали доказательство времени работы суффиксного автомата, это было трудно, да. пилите перекат уже!
ПОКАТИЛИСЬhttps://2ch.hk/pr/res/706304.html
