Оп - хуй. Задача изи.
Объясни, или уходи.
Bump
Bump
Есть пример входных данных?
Смахивает на задачу на упаковку рюкзака, но сходу не могу понять как решить "жадным алгоритмом".
Лезет в голову всякая чушь, уровня разбивать их на пары чтобы пока один надувает другой отдыхал и наоборот, для пары считать время, сортировать по минимальному времени их и отправлять надувать таких вот.
Google: multiple knapsack problem
Пояснять не буду потому что ты:
1. Создал тред.
2. Не привёл пример входных данных.
Жадный алгоритм - это слишком слабо.
Для хороших резлуьтатов тебе нужен Dynamic Programming или Branch And Bound.
А чего ты так мудришь-то с жадным алгоритмом? Просто выбирай шар который влезает с минимальной затратой времени. Время отдыха учитвай как затрату на последний шар.
Задача же олимпиадная, похуй на качество - главное быстрее сделать же.
Это да. Но ты хочешь слишком хороший результат получить от жадного алгоритма. Я понимаю, что его можно выбрать в качестве первой итерации. Но когда улучшаешь результат лучше выбрать хороший алгоритм, чем пытаться полировать эвристику.
Как же хочется порешать олимпиадочки...
Но нет, блять, пиши жабаговно, сука, у тебя ипотека ещё на 10 лет.
Один хуй, примера данных нет.
Может там можно въебать полный перебор и не париться.
Кстати да. Ни данных, ни ограничений по времени/памяти.
О чём мы тут вообще разговариваем?
Ты промазал, ковбой:
Задача
Ватсон поставил Рыбке простую задачу – найти сумму чисел меньших N, которые должны делиться либо на A, либо на B, и вывести её остаток от деления на 1000000007 (109 + 7). Помогите Рыбке справиться с этой задачей.
Входные данныеі
В одной строке задано три целых числа N, A и B.
1 ≤ N, A, B < 1018.
Выходные данные
Вывести остаток от деления искомой суммы на 1000000007.
Сорян, эта легитимная http://www.e-olymp.com/ru/problems/7227
Мне 15
(1000 99) вариантов, перебором не получится.
Требуется точное решение - эвристики и локальный поиск сосут.
Остаётся Dynamic Programming и Branch and Bound. Ну или Mixed Integer Programming, если делать по-серьёзке, но это не для олимпиады.
Через Dynamic Programming у меня нихуя не получается доказать какое-то свойство решения m шаров через m-1. Там всё хитро именно из-за пауз.
Через Branch and Bound можно так:
- в качестве нижней границы используй жадную эвристику или какую-нибудь другую эвристику если найдёшь лучше.
- в качестве верхней границы убери эти ёбанные паузы и решай стандартный multiple knapsack problem (это-то, я надеюсь, ты умеешь).
*ёбаные
Естественно, когда будешь считать верхнюю границу, учитывай время, которое уже потрачено на паузы.
Кароч, не слушай меня, через Branch and Bound хуйня полная получается.
Можно через Dynamic Programming через такое соотношения:
Решения для k+1 школьников и l шаров - это когда мы хуйнём x шаров новому школьнику + оптимальное решение для k школьнико и l-x шаров.
Дальше, я думаю, таблицу для Dynamic Programming ты построишь сам.
Спасибо попробую
Блять, почему на этом сайте ни одного языка программирования нет?
Если уже добавили Java, то могли бы и Clojure добавить, я бы им рассказал как нормально бенчмаркать через Grenchman.
И даже Ocaml нет, aleksey ссыт им в ёбыч.
Если уже добавили Java, то могли бы и Clojure добавить, я бы им рассказал как нормально бенчмаркать через Grenchman.
И даже Ocaml нет, aleksey ссыт им в ёбыч.
Помоему тут двоичной кучей (минимизирующей) проще всего. В кучу заносятся школьники, ключами служат момент времени в который они завершат надувать очередной шар. Тоесть изначально все ключи в куче равны ai соотвествующего школьника. Потом сверху кучи извлекается школьник, счетчик шаров увеличивается на один, если нужное количество шаров достигается - ответ это ключ вытянутого школьника. Если шаров не достаточно то школьник возвращается в кучу с ключом увеличеным на ai. Из-за того что школьники должны делать перерывы нужно следить за количеством надутых шаров каждым школьником - тоесть в куче нельзя хранить просто чиcла, а должна хранится структура соответсвующая школьнику с помощью который можно ослеживать сколько шаров надул школьник, и если он достиг предела, то школьник возвращается в кучу с ключом увеличены не на ai, а уже на ai + ci (перерыв плюс время необходимое на надутие очередного шара). Сложность этой хуйни полчается равна количеству шаров умноженому на логарифм школьников.
Это можно улучшить если придумать способ определить достаточно большой момент времени T, которого однако гарантировано не достаточно для того чтобы надуть все шары. Тогда изменяется начальная процедура заполнения кучи. Для каждого школьника высчитывается сколько шаров он надует за время T (это просто), счетчик шаров увеличивается это количество, и в кучу школьник кладется с ключем равным количеству времени которое осталось ему до надувания следующего шара (оно может не быть равно ai - в зависимости от времени T, может быть даже больше, если момент времени Т попал на отдых школьника). А дальше обычное вытаскивание школьников пока не наберется нужное количество шаров. Сложность получается равна "оставшемуся количеству шаров" умноженому на логарифм школьников. Проблема в способе выбора достаточно большого Т - чем оно больше тем быстрее сработает алгоритм, но при этом нельзя превысить ответ. Я думаю нужно нужно отталкиваться от среднего времени затрачиваемого школьником (с учетем отдыха) - и брать немного меньше от полученого.
Это можно улучшить если придумать способ определить достаточно большой момент времени T, которого однако гарантировано не достаточно для того чтобы надуть все шары. Тогда изменяется начальная процедура заполнения кучи. Для каждого школьника высчитывается сколько шаров он надует за время T (это просто), счетчик шаров увеличивается это количество, и в кучу школьник кладется с ключем равным количеству времени которое осталось ему до надувания следующего шара (оно может не быть равно ai - в зависимости от времени T, может быть даже больше, если момент времени Т попал на отдых школьника). А дальше обычное вытаскивание школьников пока не наберется нужное количество шаров. Сложность получается равна "оставшемуся количеству шаров" умноженому на логарифм школьников. Проблема в способе выбора достаточно большого Т - чем оно больше тем быстрее сработает алгоритм, но при этом нельзя превысить ответ. Я думаю нужно нужно отталкиваться от среднего времени затрачиваемого школьником (с учетем отдыха) - и брать немного меньше от полученого.
Ты по сути описываешь жадную эвристику. Она не гарантиурует оптимального результата.
Почему не гарантирует? У школьников есть более оптимальный способ поведения чем начать всем сразу надувать шары, делая перерывы когда выбиваются из сил?
Может быть.
Пример: 3 шара, 3 школьника. Первые 2 надувают за 1 минуту, третий надувает за 100 минут. Оптимально третьего послать нахуй.
Ну так и будет. Изначально школьники закинутся в кучу с ключами 1, 1, 100. После того как будет вытащен и закинут первый школьник куча будет 1, 2, 100, после следующего 2, 2, 100, на следующем мы наберем нужное количество шаров и ответ - ключ последнего вытянутого школьника, тоесть 2. Подход с кучей моделирует систему школьников. Давать не оптимальный ответ он может только если моделируемое поведение школьников (все сразу начинают надувать шары, делая перерывы когда выбиваются из сил) не оптимально. Естественно я не утверждаю что это идеальный способ решения, я слаб в динамическом программировании, вполне возможно что с помощью ДП можно решить более эффективно.
Есть 95% процентов робочий код, нужно обьяснить как он работает.
http://ideone.com/oGjprh
http://ideone.com/oGjprh
Вопрос не в эффективности, а в корректности.
Бремя доказательства в данном случае лежит на тебе.
Читать твои телеги мне немного влом, извини. Как только ты сформулировал чёткое и короткое предложение по типу
> У школьников есть более оптимальный способ поведения чем начать всем сразу надувать шары
я тебе сразу привёл контрпирмер.
Сможешь так же чётко и коротко сформулировать доказательство корректности - я проверю.
Вообще, какие ограничения по времени и по размеру входных жанных? Оные вообще есть?
хз, какой-то жадный алгоритм. На ДП не похоже.
Ох лол. Иди нахуй.
Какие мы важные.
Пишешь длинные телеги, в которых смешиваешь в кучу идею с реализацией и даже не думаешь что-то говорить о корректности.
Потом ждёшь что кто-то это будет читать, утирать тебе сопли и учить тебя нормально формулировть свои мысли, а потом ещё будет искать контрпример для тебя.
Ну ты понял.
пусть есть один школьник
наилучшая стратегия для него начинать дуть сразу после отдыха
пусть есть 2 школьника
есть два варианта
0 надувают одновременно
1 второй начинает дуть с задержкой
это либо даст задержку, либо не даст, но время не улучшит никак, поэтому на хуй не нужно
в первом слкучае следующее соотношение будет справедливо для двух и большего числа школьников в виду аддитивности
0 посчитаем поток, с которым надувают шарики 1/ai
1 сложим потоки надува sum(1/ai)
2 надуем с совокупным потоком m/(sum(1/ai))
3 учтём время на отдых sum(floor(m/(bi)ci))
время надува будет
m/(sum(ai))+sum(floor(m/(bi)ci))
>Источник Житомирская ХХVIII обласная олимпиада по информатике
Чому не по русскому языку?
Кстати это еще что.
Таких организаторов олимпиады в анус без смазки ебать надо, там минимальное время не 8, а 7 минут.
Как выглядит решение для 7 минут?
Задача кстати элементарная, если шариков больше надувающих. По сути только итерироваться по времени и считать шарики. Сейчас сфоткаю и выложу графический способ решения, по которому все станет понятно (в том числе и обосрамс с 8, а не 7)
да ну не может там быть 7 минут
в семь минут уложится всего 3 шара от третьего и 2 от второго (по 6 минут), значит первому остаётся 5 шаров. 5 шаров у него займут 11 минут.
Ты b и c перепутал: первый должен делать 3хминутные паузы после каждых 2х шаров, а не наоборот.
> за ai минут, причем каждый раз после надувания bi шариков отдыхает и переводит дух ci
Таблица по горизонтали, а не по вертикали что ли идет?
Доказательство оптимальности не забудь.
Да, по горизонтали. Один ряд - описание одного школьника.
Щас тогда переделаю.
Таки 8.
Но я уже определился с выбором - назовем этот метод "интегрирующим". Для каждого школьника строим числовой ряд - сколько шариков он надувает за текущее время, и суммируем ряды, а дальше ищем искомое время в результирующем ряду.
Но я уже определился с выбором - назовем этот метод "интегрирующим". Для каждого школьника строим числовой ряд - сколько шариков он надувает за текущее время, и суммируем ряды, а дальше ищем искомое время в результирующем ряду.
В принципе, на скорую руку могу запилить реализацию на дишке.
Доказательство оптимальности не забудь.
Это еще зачем, лол?
Каким образом?
Эталонной реализации и набора данных то нет.
Может ты и задачу рюкзака будешь решать жадной эвристикой и утверждать, что решение оптимально?
Бля, придётся в той петушатне зарегаться.
А не похуй, оптимально оно, или нет?
Это тебе и доказывать, найди такие наборы данных, которые докажут, что оно неоптимально.
Это олимпиадная задача, проверять будут автоматизированно. Даже если оно неоптимально, но таких наборов данных не будет - никого не ебет.
Как-то так
Ясно.
нахуй из математики - это вон туда
Ты даун что ли? Мы тут не в математике, теоретическая хуйня не ебет никого. Должно сойтись по тестам за отведенное время - как то так.
Для той хуйни только на жабе писать надо?
Правильно,теперь на паскаль перепишу
Нет, можно даже Хачкиль.
Суки ебаные, дишечки нет.
Набор данных, на котором проверяют - выдрать можно?
Хуй знает, не пробовал. Stdout твоей программы не показывают, как по другому выдирать - я не знаю.
Ну может ты в чём-то прав.
Численные эксперименты в математике имеют место, и зачастую опережают доказательства.
А то. Ты же пользуешься классической механикой, и тебя не ебет, что она неправильная.
Так как в своей жизни с такими скоростями или прочими условиями, на которых это будет ощутимо - один хуй не столкнешься.
Кодируй номерами тестов
номер теста - 1 бит
прошёл - единица
не прошёл - нолик
В первом прогоне выкидывает первый бит тестовых данных
во втором - второй
и т д
>номер теста - 1 бит
вернее номер теста - это номер теста
в исходнике захардкоденное число, инкрементируемое
программа смотрит соответствующий бит входных данных, если бит один, то решает тест, если 0 - то фейлит
вернее номер теста - это номер теста
в исходнике захардкоденное число, инкрементируемое
программа смотрит соответствующий бит входных данных, если бит один, то решает тест, если 0 - то фейлит
По-моему это сложнее, чем решить саму задачу.
Но он же её уже решил, теперь он хочет выдрать условия тестов чтобы выложить в инет.
Больший bandwidth можно получить, если использовать память.
Также это не потребует решения теста.
Маллоком выделяем памяти столько, сколько нужно.
Предварительно прогоняем программу, не выделяющую кодирующей памяти вообще, чтобы иметь базовое значение
Предварительно прогоняем программу, не выделяющую кодирующей памяти вообще, чтобы иметь базовое значение
А вот время хер заюзаешь, оно обычно заблокированно. но если разблокированно, то действуем аналогично.
Для большей эффективности можно добавить zlib
Для большей эффективности можно добавить zlib
если они станут рандомизировать размер кучи, то его опять же можно легко узнать маллоком и внести поправку
но вообще это всё не имеет смысла, так как большая часть тестов на олимпиадах - случайная
Если она будет случайная - одно и то же решение на разных наборах может быть правильным и неправильным.
как будто что-то плохое. Важно ведь общее число пройденных тестов.
Зачем они вообще показывают номера тестов, если данные от них не выдают, не понятно.
Интересно, к ним можно загрузить тест с форк-бомбой, лол?
И вообще, может тесты детерминированно случайные. То есть у каждого игрока есть случайный seed, на основе которого генерится тестовый набор, фиксированный для каждого игрока.
Кстати, seed можно не генерить для каждой задачи, а выводить с помощью хеш-функции
обычно такие вызовы запрещены. Как и вызовы работы с фс кроме stdin/stdout, и прочие системные вызовы
Нахрена что то хранить?
Со статическими тестами проще всего, так нафига лишние выебоны.
при выводе с помощью хеш-функции не нужно ничего кроме данных аккаунта и данных задачи, которые хранятся и так
Проверять решения разными наборами - нечестно, вот и все.
>Со статическими тестами проще всего, так нафига лишние выебоны.
Чтобы нельзя было наплевать на ограничения времени и памяти. Можно неэффективным алгоритмом предпросчитать у себя на cpu/видеокарте/fpga.
Каким образом? Допустим набор статический - для всех одинаковый, но погромист извне все равно его не знает.
Я помню мне препод мануал выдал по проведению олимпиад, там было чёрным по белому написано что используются 4 группы тестов: выданные на руки с задачей, граничные случаи, рандомизированные и специально спроектированные жури с целью завалить некоторые решения.
>и специально спроектированные жури с целью завалить некоторые решения.
Это чтоб свои знакомые выиграли, когда оешениям других участников можно подосрать?
хз
Я помню, как лет 8 назад после школки возлагал надежды на коколимпиадку вузиковскую. В методичке были примеры заданий и написано что отводится час. По факту - решение требовало не алгоритма, а формулки из матстатистики которую давали на 3м курсе, писать заставили на листке и дали полчаса.
Учитывая, что призом был ноут - специально суки под знакомых заточили, пидоры.
Нет, это чтобы жиды выигравали, а русские нет.
ну он дал рецепт обхода - рандомизировать входные данные
ладно, я вот геометрию понял только тогда, когда в вузе курс линейной алгебры прошёл, а до этого мне это казалось какой-то хуйнёй
Все эти олимпиады решаются знанием нескольких вузовских курсов
Я серьезно - уже на 3м курсе понял, как вспомнил.
Требовалась там какая та формула из комбинаторики, сцуко - и все, никакого алгоритма.
А я в 11 классе такую знать никак не мог.
Если конкретно, то курсом "Дискретная оптимизация".
Но в рашкинских вузах такого не бывает, насколько я знаю.
Кстати, интересный вопрос - а там оценивается время выполнения проги?
В крестах то некоторые вычисления можно в compile-time упрятать.
В крестах то некоторые вычисления можно в compile-time упрятать.
сега приклеилась
В компайл-тайме ты не знаешь входных данных.
Чтобы частные случаи и эвристику поломать. Бывает, что неправильный алгоритм правильно работает на некотором подмножестве данных.
Делал на частных случаях и эвристике, прокатывало.
Везучий засранец.
Зато тупанул на другой хуйне, вышел уже из кабинета - тут в голову пришло решение, а обратно зайти зассал.
А вот и мое "интегральное" решение. Простое как три копейки.
В душе не ебу, "оптимальное" ли оно, но все тесты проходит.
http://ideone.com/5uGC5x
В душе не ебу, "оптимальное" ли оно, но все тесты проходит.
http://ideone.com/5uGC5x
чем они там блядь с# компилируют, на dotnetfiddle работает, а у них с этим judge c# меня нахуй шлёт с "Ошибка выполнения"
Алсо загрузилось только со второго раза - эта олимпиадная ебань сагрилась на кириллицу в комментариях.
проверьте https://ideone.com/rB02rY
Отправил за тебя твое решение.
Говно короче.
очень простой тест-кейс дополнительный
просто замени 10 3 на 10 4
и следующей строкой добавь "10 1 1" например
твой вариант уже валится
Твоё определённо лучше, чем ДП.
Но оно специфично для задачи. И ещё нужно хотя-бы самого себя убедить в его корректности (что ты сделал с помощью рисунка, это очень хороший метод).
А у меня, так сказать, профессиональная деформация личности, после изучения методов дискретной оптимизации я всё делаю стандартными методами. В данном случае интуиция меня подвела, т.к. я думал что задача связана с задачей рюкзака, в которой эвристики не прокатывают.
>следующей строкой
>следующей строкой
>следующей строкой
>следующей строкой
>следующей строкой
Алгоритм X - каждый сосницкий начинает надувать шары как только может и продолжает до тех пор, пока не устанет.
Допустим есть алгоритм Y, позволяющий за то же время надуть больше шаров, чем при использовании алгоритма X.
Общее количество надутых шаров складывается из шаров надутых каждым сосницким. Значит в алгоритме Y некоторые сосницкие надувают больше шаров, чем в алгоритме X. А это невозможно. Уж это-то объяснять не надо?
в оптимальном некоторые сосницкие шары не трогают вообще. Потому что может быть что у одного из них ампутировали 1.5 лёгкого и один шар он надувает теперь за 1000 минут.
>каждый сосницкий начинает надувать шары
будет работать только если твой алгоритм умеет отнимать обслюнявленные шары у медленно-дующих инвалидов
Но ведь нет ограничения по количеству шариков.
Сказано - нужно надуть n шариков. А сколько там резины валяется - не сказано.
Ты сам себе ограничения придумываешь.
Верно. Но даже если бы лишних шаров не было формула никак не поменялась бы.
От нас не требуется составлять расписание надувания шаров, так что мы можем предположить, что вокруг сосницких бегает препод и оптимальным образом распределяет шары. При таком раскладе ситуация ровно такая же что и с лишними шарами.
В любом случае, у нас самый простой вариант - дуют все участники, количество сдутых шаров безлимитно.
Так что те, кто хуево дует, как минимум не сделают хуже и никак не влияют на время.
> кроме себя
Не, на себя ты тоже норм наляпал. Учитывая что выше был анон с соточкой то можно считать что ты себя с головы до ног обоссал.
Два анона с соточкой было же.
Ок, разобассываю.
Назовём надувание bi шариков + отдых одним циклом, время выполнения которого ti=ai*bi+ci
Тогда поделив bi/ti=perfi мы найдём среднюю производительность perfi каждого школьника по времени. Найдём отношение каждого perfi к максимальному max_perf из них и округлив вперёд до целых, мы найдём их соотношения rel_perfi = round(max_perf/perfi) . После чего кидаем каждому школьнику, начиная с самых производительных, количество шакриков, равное rel_perfi
Кинул свои шарики тебе за щёку.
не вовремя, он уже вдул 10, и он отдыхает 5 минут.
С этой уже определились.
Какую следующей солвить будем?
Какую следующей солвить будем?
Выбирай. Только посложнее что-нибудь.
Алгоритм уже не так красиво выглядит, как у -куна
У него тупо цикл, а у меня бинарный поиск, понятно что кода побольше.
Ну так зато у него сложность O(nT), а у меня O(nlog(T)), где n - число школьников, а T - требуемое время.
Это как дергать гланды автогеном через анальное отверстие. В рассматриваемой задаче нахуй не нужно, на скорость не влияет, а на простоту понимания - еще как.
Идёт девушка, видит - парень косит траву в противогазе:
- Ты что, с ума сошёл - зачем противогаз надел?
- Я комсомолец - не могу без трудностей...
- Кончай хуйней страдать, пошли лучше потрахаемся.
- Хорошо, но только стоя и в гамаке...
Ну что же:
http://www.e-olymp.com/ru/problems/32
Мы предлагаем Вам похожую игру, в которой участвуют белая пешка и черный конь. Ходы делаются в соответствии с общепринятыми шахматными правилами. Белые ходят первыми. Белые побеждают, если они смогли провести свою пешку в ферзи и следующим своим ходом черный конь не может уничтожить ферзя. Партия заканчивается вничью, если очередь хода за белыми, но пешка не может продвинуться вперед. Если конь сумел побить пешку или ферзя, то выигрывают черные. Требуется выяснить исход партии при наилучшей игре с обеих сторон.
Вопрос таков - что есть "наилучшая игра с обоих сторон", и как она определяется?
В голову приходит разве что завершение игры через максимально долгое время. Правда, если проигравший так долго мог защищаться - выходит игра победившего была неоптимальной?
http://www.e-olymp.com/ru/problems/32
Мы предлагаем Вам похожую игру, в которой участвуют белая пешка и черный конь. Ходы делаются в соответствии с общепринятыми шахматными правилами. Белые ходят первыми. Белые побеждают, если они смогли провести свою пешку в ферзи и следующим своим ходом черный конь не может уничтожить ферзя. Партия заканчивается вничью, если очередь хода за белыми, но пешка не может продвинуться вперед. Если конь сумел побить пешку или ферзя, то выигрывают черные. Требуется выяснить исход партии при наилучшей игре с обеих сторон.
Вопрос таков - что есть "наилучшая игра с обоих сторон", и как она определяется?
В голову приходит разве что завершение игры через максимально долгое время. Правда, если проигравший так долго мог защищаться - выходит игра победившего была неоптимальной?
Хотя, походу наоборот - у коня дохуя способов походить, а у пешки - только вперед. Значит, оптимальный - думаю это когда конь натягивает пешку за минимально короткое время (поскольку пешка не может ходить неоптимально, у нее один путь)
> натягивает пешку за минимально короткое время
Именно минимальность времени в данном случае не важно, так как нужно сообщить результат, а не количество ходов. Тоесть для коня "наилучшей игрой" будет такая последовательность ходов при которой он берет пешку, если у него такая возможность есть. С ходами пешки не совсем ясно. Свой первый ход пешка может сделать как на одну, так и на две клетки. Следовательно для своей "наилучшей игры" пешка должна просчитать результат при первом ходе на одну клетку, и при первом ходе на две клетки. И выбрать тот вариант при котором она выигрывает. Если такого нет, то разницы что выбирать нет. Выбор есть только если пешка начинает со своей начальной по правилам позиции (второй ряд).
Я настаиваю на минимальности. Именно игра, которая закончилась минимально быстро - была оптимальной, кмк, так как конь может ее затянуть и просрать в итоге.
Непонятно другое - на самом сайтеце есть два варианта развития событий для g3-a1, если пешка ходит на два хода - то ничья, а если один - то съедается конем. Казалось бы, раз пешка может сыграть вничью - то это и есть вариант когда оба играют оптимально. Но с какого то хуя там в результате программы стоит -1 - если выигрывают черные. Как это понимать?
Хотя, ашибочка. Анимашка с примером для пешки на g2, а там где пример входа и выхода - g3, все верно. А для g2 видимо оптимальна именно ничья.
Что делать, если пешка изначально на 8-й линии?
Очевидно, пешка побеждает.
Хотя, точнее - побеждает, если не находится под ударом коня на следующем ходу.
Сука, какое же говно эта ваша джава.
Думаю, как организовать список результатов - нету в этой блядине ни Pair, ни Tuple.
Думаю, как организовать список результатов - нету в этой блядине ни Pair, ни Tuple.
А где ее тип то задается? Я ожидал что то вроде Pair<int, double>.
Мне вообще то список такой поеботы нужен. Впрочем, я уже плюнул и на кресты перешел.
CYKA BLYAT, ну и как это дебажить?
Тут такой интересный вопрос - а может ли пешка перепрыгнуть коня, если она стоит на начальной позиции?
Нет конечно.
Ты не понел - если конь стоит на следующей, а пешка имеет право в первый раз походить на 2 клетки?
> имеет право в первый раз походить на 2 клетки
Только если обе клетки пустые. Пешка не может перепрыгивать фигуры.
Ну и заебок, это упрощает дело - меньше лишней поеботины обрабатывать.
Посоны, вроде сделал - кроме одного.
Как там вход считать? На крестах?
Ну как эту ебань g3 и a1 получить?
Как там вход считать? На крестах?
Ну как эту ебань g3 и a1 получить?
https://ideone.com/Miu6QC
Подскажите, где я проебался?
Подскажите, где я проебался?
Читай в строку. Потом проще всего будет сделать str[0] - 'a' и str[1] - '0' - получишь индексы. Это не сильно надежно, но для олимпиадки пойдет.
Да я так уже и сделал.
Только блять, ищу что не так.
Родился хохлом.
В загон, быдло.
Но я нихуя не ukraine, лол.
Хотя и родился в Харькове. Но тогда был еще совок.
> так уже и сделал
У тебя там какая-то неочевидная хуита. Я бы работал не с координатами фигур, а с растоянием между ними (отдельно растояние по вертикали и по горизонтали) высчитаное из их начальных позиций. Дальше, пешка на каждом своем ходу (кроме первого) увеличивает растояние по вертикали на один. А конь может увеличить/уменьшить растояние по вертикали или горизонтали на 2 и одновременно увеличить или уменьшить растояние по другой координате на 1. Если растояние стало 0 по обоим координатам то конь победил, если один по вертикали перед ходом белых то ничья. Ну и нужно сначала высчитать ограничение по ходам, связаное с тем что пешка дойдет до верха.
там по умолчанию украха ставится
Не важно.
Я тоже застрял на 97% верных ответов. Хочешь сгенерю ответы своей прогой для всех пар координат?
Я нихуя не понял.
>У тебя там какая-то неочевидная хуита.
У меня все очевидно - просчитываются абсолютно все варианты (их 6 штук примерно получается), потом они сортируются (сперва по номеру хода, потом по позиции), а потом берется первый из списка.
Я думаю, что у меня проеб с сортировкой, т.е. с критерием "оптимальной игры обоих сторон"
Дохуя пар координат получается.
64*63 всего же
Блжад, если бы можно было из этой украинской ебани выдрать наборы данных, вызывающие неправильное поведение...
Я надеюсь, там вход валидировать не нужно? Там, регистр к маленькому приводить?
Входные данные скорее всего верные.
Наборы данных выдрать не проблема, но не хочу этим заниматься т.к. читерство.
Определенно, дело скорее всего в критерии "оптимальности".
Подшаманил сравнение на
return (a.second != b.second) ? a.first < b.first : a.first < b.first;
Но чего то еще не хватает...
Ебать, я даже условия не понимаю. Как вы это решаете, школьники?
Идея понятна, но я не врубаюсь почему это работает
Я же выше с рисунками даже блять логику показал, не?
Просто мне сначала показалось что это слишком наивное решение, которое завалится на каких ни будь изоощерённых тестах
Ну, не завалилось же?
Пришлось делать двумя разными способами чтобы отловить ошибки. Но я сделал это! https://ideone.com/V5zFoc
Что, соснули, да? А? А?
Ха-ха-ха, ещё как соснули! ( ͡° ͜ʖ ͡°)
Пользуясь случаем передаю привет маме.
Этот кусок говна с тестами - неправильный.
Конкретный пример - b6 c7. 30й тест ожидает что победят белые, хотя - хуй там плавал.
b6b7 c7a6
b7b8 a6b8 - только пешка прорывается в ферзи, как следующим же ходом ее срезает конь
>Белые побеждают, если они смогли провести свою пешку в ферзи и следующим своим ходом черный конь не может уничтожить ферзя.
Конкретный пример - b6 c7. 30й тест ожидает что победят белые, хотя - хуй там плавал.
b6b7 c7a6
b7b8 a6b8 - только пешка прорывается в ферзи, как следующим же ходом ее срезает конь
>Белые побеждают, если они смогли провести свою пешку в ферзи и следующим своим ходом черный конь не может уничтожить ферзя.
Кстати, раз пошла такая пьянка - я выдрал тесты, входные данные и результат. Они таки статические:
g3-a1 = -1
a7-a6 = 1
a7-a5 = 1
a7-a1 = 1
a7-b5 = 1
a7-c6 = 1
a7-b8 = 1
a7-c8 = 1
a7-d6 = 1
b7-a8 = 1
b7-c8 = 1
b7-b6 = 1
b7-a5 = 1
b7-c5 = 1
b7-c6 = -1
b7-a6 = -1
b7-d7 = -1
b7-g2 = 1
b7-d3 = 1
b7-d4 = 1
b6-a6 = 0.5
b6-c6 = 0.5
b6-d7 = 0.5
b6-b7 = 0.5
b6-c5 = -1
b6-d6 = -1
b6-d8 = -1
b6-a5 = -1
b6-b8 = -1
b6-c7 = 1
b6-a7 = 1
b6-a8 = 1
b6-c8 = 1
b5-a4 = -1
b5-c4 = -1
b5-d5 = -1
b5-d7 = -1
b5-c8 = -1
b5-a8 = -1
b5-b7 = -1
b5-e4 = -1
b5-f5 = -1
b5-e6 = -1
b5-h7 = -1
b5-g8 = -1
b5-g4 = -1
b5-h5 = -1
b5-d3 = -1
b5-b3 = -1
b5-c2 = -1
b5-a2 = -1
b5-g2 = 1
b5-h3 = 1
b5-d4 = 0.5
b5-d6 = 0.5
b5-b4 = 0.5
b5-a5 = 0.5
b5-e5 = 0.5
b5-e7 = 0.5
b5-d8 = 0.5
a5-b6 = 1
a5-c8 = 0.5
a5-c6 = 0.5
a5-b5 = 0.5
a5-a7 = -1
a5-a8 = 0.5
a5-a6 = 0.5
a5-h1 = 1
a5-g1 = 1
a5-f1 = 1
a5-f2 = 1
a5-g2 = 1
a5-h2 = 1
a5-h3 = 1
a5-g3 = 1
a5-f3 = 1
a5-f4 = -1
a5-e4 = 1
a5-d4 = -1
a5-d5 = 0.5
d7-d8 = 0.5
d7-b7 = -1
d7-c6 = -1
d7-e6 = -1
d7-f7 = -1
d7-e7 = 1
d6-d7 = 0.5
d6-b7 = 0.5
d6-c6 = 0.5
d6-e6 = 0.5
d6-f7 = 0.5
d6-g7 = -1
d6-h8 = -1
d6-f4 = -1
d6-f5 = 1
c6-a7 = 0.5
c6-e7 = 0.5
c6-d6 = 0.5
c6-c8 = -1
c6-g6 = -1
g2-a1 = 0.5
h2-a1 = 1
h3-a1 = 1
a2-a3 = 0.5
b2-b3 = 0.5
c2-c3 = 0.5
d2-d3 = 0.5
e2-e3 = 0.5
f2-f3 = 0.5
g2-g3 = 0.5
h2-h3 = 0.5
a2-b3 = 1
b2-c3 = 1
c2-d3 = 1
d2-e3 = 1
e2-f3 = 1
f2-g3 = 1
g2-h3 = 1
h2-g3 = 1
a2-a4 = -1
b2-b4 = -1
c2-c4 = -1
d2-d4 = -1
e2-e4 = -1
f2-a2 = 0.5
g2-a8 = 0.5
g3-h4 = 1
a2-b5 = 0.5
b2-a5 = 0.5
c2-d5 = 0.5
d2-e5 = 0.5
e2-d5 = 0.5
f2-e5 = 0.5
g2-f5 = 0.5
h2-h5 = 0.5
a3-a7 = -1
b3-a4 = 1
c3-d8 = -1
d3-e6 = -1
e3-c6 = 0.5
f3-b6 = 0.5
g3-c6 = 0.5
h3-g4 = 1
h3-h7 = -1
> b6 c7
Игра же идет по правилам шахмат, пешка бьет коня. ШАХ И МАТ ОЛИМПИАДНИКИ
А, блять.
В условии такой хуйни (что пешка может бить) - оговорено не было.
Ну ок.
Фух, отладил. Заебался баги выцеплять.
https://ideone.com/YKN6Dy
https://ideone.com/YKN6Dy
Какой у вас рейтинг на кодфорсес?
Лично я впервые услышал это слово месяц назад на дваче. Смотрел задачи прошедших контестов - за 2 часа могу решить 2, если повезёт - 3.
http://www.e-olymp.com/ru/problems/41
Сап, друзья есть одна проблема, просьба рассказать алгоритм.
Сап, друзья есть одна проблема, просьба рассказать алгоритм.
Спасибо
Забавное наблюдение - если нарисовать матрицу смежности, то искомые группы образуют "ступеньки" на картинке, и графическое решение - поиск наикрупнейшего куска "ступенек".
Подумаю, можно ли это использовать в алгоритме решения.
Подумаю, можно ли это использовать в алгоритме решения.
Если ты заштрихуешь главную диагональ, то тебе бросится в глаза кое-что другое - полностью заштрихованный квадрит в левом верхнем углу.
Это более правильное наблюдение. Максимальная клика всегда выглядит как такой квадрат. Проблема в том, что строки и столбцы могут идти в любом порядке, и строки и столбцы квадрата могут быть разрежены полупустыми строками и столбцами.
Просто найти такой квадрат
Когда квадрат выглядит вот так
найти его сложнее. В реальности же там ещё и посторонний мусор будет
Так что пиши Брона-Кербоша и не выёбуйся.
Бляяя. Ща оформлю.
Просто найти такой квадрат
xxx
xxx
xxx
Когда квадрат выглядит вот так
xx x
xx x
xx x
найти его сложнее. В реальности же там ещё и посторонний мусор будет
xx x
xx
xx x
x
xxxx
Ну я собсно ща и проверяю, как оно будет выглядеть - рисую граф повыебистее, а номера позже порандомнее расставлю.
>Так что пиши Брона-Кербоша и не выёбуйся.
Я про эту хуйню всего лишь 15 минут назад на википедии вычитал. Выглядит слишком замороченно и дрючевно.
У меня пока мысль попроще - начинаем со списка пар, как с минимальных групп размером 2.
Каждую группу пытаемся "укрупнить", сканируя соседние вершины и ища такие, которые будут принадлежаьб каждой вершине в группе.
И так до тех пор, пока не будет получаться увеличить список таких кусков. А дальше - дроп и выбор первого из крупных кусков как результата.
Как достиг такого навыка? сколько лет тренируешься?
Я доходил до 1593, потом все слил. Уже месяца два не пишу, ибо в школе напряги
В универе я осознал, что мне нравится писать проги для курсача по дискретной математике. Это было лет 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.
>сканируя соседние вершины и ища такие, которые будут принадлежать каждой вершине в группе.
Есть идея получше. Допустим ты начинаешь с полносвязного графа размера 1 - одной вершины.
Ты берёшь полный список всех вершин, и убираешь из него все несвязанные с этой вершиной вершины.
Ты получил список всех вершин, которые можно добавить к первой для получения полносвязного графа из двух вершин.
Выбираешь очередную вершину, удаляешь из списка кандидатов все вершины, которые не связаны с новодобавленной. Снова в остатке получаешь список вершин, которые можно добавить к имеющимся 2 для получения треугольника.
Это работает для любого числа вершин, что позволяет наращивать массив рекурсивно. И это эффективнее чем каждый раз пробегаться по всем вершинам, проверяя, связаны ли они со всеми уже включёнными в рассматриваемый подграф.
Конечно надо как-то избегать ситуации когда ты будешь рассматривать одну и ту же комбинацию по несколько раз. К примеру ты начал с пары вершин 1-2 и нашёл, что её можно вырастить до 1-2-3-4. Когда ты начнёшь с пары 3-4 тебе не надо будет рассматривать возможность добавить к ним 1 и 2, потому что этот вариант ты уже рассматривал.
Чтобы понять как это сделать полезно написать неоптимизированную программу, которая будет выводить список _всех_ клик в графе, а не только максимальных. Ну то есть если у тебя полносвязный граф из 5 вершин, то надо вывести 5 клик из 1 вершины, 10 из 2-х, 10 из 3, 5 из 4 и 1 из 5.
Когда соединишь всё вместе получишь Брона-Кербоша.
_тест_
тест
__тест__
тест
__тест__
>И это эффективнее чем каждый раз пробегаться по всем вершинам, проверяя, связаны ли они со всеми уже включёнными в рассматриваемый подграф.
Но я не собирался ни по чему пробегаться. Я собираюсь делать все на множествах. Там и циклов по сути никаких не надо, только объединения/пересечения.
Ясно.
Да не кипишуй ты, попробую.
Всему свое время. Я пока ебусь с std-шными контейнерами. Раньше юзал Qt-шные, не думал что в голых крестах они такое говно, и что даже чтобы банально узнать, есть ли элемент в контейнере - надо ебаться с итераторами.
https://ideone.com/odyLzb
Помогите найти, хуле этой гниде не так.
Из 9 тестов на 1м какая-то "ошибка выполнения".
Тестил на их примере, и на графе в 20 вершин-пикрелейтед
(http://pastebin.com/AYyh68gU)
Помогите найти, хуле этой гниде не так.
Из 9 тестов на 1м какая-то "ошибка выполнения".
Тестил на их примере, и на графе в 20 вершин-пикрелейтед
(http://pastebin.com/AYyh68gU)
У тебя "ошибка выполнения", а не неправильный ответ.
Возможно мер-хикка, а его друзья - аутисты.
ты крут!
Блять, а ведь и правда - прога сегфолтится на том единственном случае, когда k=0 и 0 пар, то есть реально одни хикки в друзьях.
А хуле в таком случае должна выводить прога?
Собсно, у меня 3 варианта:
1) нихуя
2) 0
3) 0
1
Значит команда мера - один мегатащер.
>3) 0
>1
Блять, 1 1
this
Фак еа!
После инпута надо было добавить
/if (K == 0){
std::cout << 1 << std::endl;
std::cout << 1 << std::endl;
return 0;
}/
Это жадник. ОП хуй. Мимо проходил
Это вообще не задача рюкзака.
Ее уже давно решили ИТТ.
Как смог дойти до такого уровня, как готовился?
Занимался. Решал. Ездил в соответствующие лагеря (гугли лкш). Ходил во всякие кружки при ИТМО ДС-2 - боярин
И везде решал как сучка. Практика - это главное
что можешь сказать о людях у которых рейтинг >2000? из моей мухосранской школы как минимум двое имеют звание мастера
Это либо ебаные гении, которые просто выигрывают всеросы по математике и заодно кодят по приколу. Либо хорошие учителя + море практики
а ты сколько времени потратил на это? если к примеру у меня по математике отлично легко, за сколько можно надрочиться?
С разной интенсивностью я занимаюсь уже третий год. Но я хуйней страдаю. Знаю много ребят, которые за календарный год добивались призеров на всеросе. Просто надо реально по этой теме угареть, и реально много работать + изначальный предрасположенности
Двачую этого, сам я говно, но знаю парочку кто добился, но там адовая дрочильня почти каждый день была. Честно говоря, лучше уж что-то более прагматичное дрочить каждый день, но не мне судить успешных людей, кек.
Какая разница, если доставляет? Меня уже не раз захватывал такой поток, что я по 8 часов нарешивал эти задачки, другой вопрос, что потом меня переклинивает и я за один присест в пределах суток прочитываю какую-нибудь книгу, а потом неделю бегаю по утрам, забиваю, начинаю кодить на жабе, забиваю, учусь писать декартовы деревья, читаю китайские публикации по биологии и так далее
тебе какие-нибудь книги помогли?
Очевидный Кормен очевиден. Шень неплох. В принципе годная книга - Реальная математика Грехэма, Кнута и Поташника
Посоны, есть задачка.
На поле размером NxM клеток в точке (x0, y0) стоит робот, который умеет делать шаг на 1 клетку влево/вправо/вверх/вниз (по диагонали не умеет). Посчитать количество вариантов перемещения робота в точку (x1, y1) ровно за k шагов.
Прелесть в том, что шагать робот может по одним и тем же клеткам несколько раз. И мой алгоритм тупо перебором не периваривает большие поля и ходы. А когда попросил данные для теста, то получил вот это
n = 100
m = 100
x0 = 50
y0 = 50
x1 = 60
y1 = 60
k = 200
ответ = 3026331761191340503770893374595925277055394295450130902271922168548205308642694668236259320332359033488388961148337920
время выполенния 5 сек.
Судя по всему тут можно применить какие то формулы комбинаторики, но я них не силен.
На поле размером NxM клеток в точке (x0, y0) стоит робот, который умеет делать шаг на 1 клетку влево/вправо/вверх/вниз (по диагонали не умеет). Посчитать количество вариантов перемещения робота в точку (x1, y1) ровно за k шагов.
Прелесть в том, что шагать робот может по одним и тем же клеткам несколько раз. И мой алгоритм тупо перебором не периваривает большие поля и ходы. А когда попросил данные для теста, то получил вот это
n = 100
m = 100
x0 = 50
y0 = 50
x1 = 60
y1 = 60
k = 200
ответ = 3026331761191340503770893374595925277055394295450130902271922168548205308642694668236259320332359033488388961148337920
время выполенния 5 сек.
Судя по всему тут можно применить какие то формулы комбинаторики, но я них не силен.
Это банальной трехмерное дп
Хотя с такими числами... Не знаю. Но ты подумаю в сторону дп
Дабл Пенетрейшн?
Ну как я понимаю что я и решал динамическим программированием. Рекурсивно перебираю все воздожные варианты. И мой алгоритм работает, но с маленькими числами, а как его оптимизировать я не знаю, может есть в динамическом программировании какой то раздел. Просто в олимпиадном программировании я не силен.
Динамика - это рекурсия развернутая в рекурсивную формулу. Или попросту рекурсия с запоминанием. Подумай, как ты можешь для вычисления очередного ответа не заново всю рекурсию запускать, а лишь обращаться, например, к соседним клетка, и как-то использовать уже предпосчитанную информацию
Спасибо анончик, буду думать в этом направлении.
Вам тут по скольку лет? Вообще бывают олимпиадники в районе 30 лет?
Олимпиадники в районе 30 лет - это те, которые уже все выиграли, что могли, и теперь только могут учить остальных
>ответ = 3026331761191340503770893374595925277055394295450130902271922168548205308642694668236259320332359033488388961148337920
Это шцтка юмора что ли? Что это за число ебаный в рот?
три дохуллиона двадцать шесть дохуллионов триста тридцать один дохуллион семьсот шестьдесят один дохуллион сто девяносто один дохуллион триста сорок дохуллионов пятьсот три дохуллиона семьсот семьдесят дохуллионов восемьсот девяносто три дохуллиона триста семьдесят четыре дохуллиона пятьсот девяносто пять дохуллионов девятьсот двадцать пять дохуллионов двести семьдесят семь дохуллионов пятьдесят пять дохуллионов триста девяносто четыре дохуллиона двести девяносто пять дохуллионов четыреста пятьдесят дохуллионов сто тридцать дохуллионов девятьсот два дохуллиона двести семьдесят один дохуллион девятьсот двадцать два дохуллиона сто шестьдесят восемь дохуллионов пятьсот сорок восемь дохуллионов двести пять дохуллионов триста восемь дохуллионов шестьсот сорок два дохуллиона шестьсот девяносто четыре дохуллиона шестьсот шестьдесят восемь дохуллионов двести тридцать шесть дохуллионов двести пятьдесят девять дохуллионов триста двадцать дохуллионов триста тридцать два дохуллиона триста пятьдесят девять дохуллионов тридцать три квинтиллиона четыреста восемьдесят восемь квадриллионов триста восемьдесят восемь триллионов девятьсот шестьдесят один миллиард сто сорок восемь миллионов триста тридцать семь тысяч девятьсот двадцать
А кодфорсес - это самая легитимная платформа?
Вообще, посоветуйте, на какой платформе рейтинг подымать? А то я на каждой решаю по чуть-чуть и забиваю. Хочется зависнуть на какой-то одной.
тимус прорешивай. Решишь там 500 задач - красный на кфе обеспечен
Спс. Я где-то тоже слышал, что тимус - это самый хардкор.
Не хардкор, а реальные задачи. Вот на кфе задачи A и B div2 вообще смысловой нагрузки не несут
Школота, кто-нибудь на московскую городскую олимпиаду идёт? Сколько там времени даётся, сколько баллов надо набрать на призёра?
>динамическим программированием
>Рекурсивно перебираю все воздожные варианты
нет, это не дп
>Хотя с такими числами...
какими числами? ограничений на 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
решение дать, или подсказку?
>ограничений на n/m/k нет
ограничений на n/m/k в пасте не дано, потому я предоположил очевидное
быстро-фикс
Строй деревья, деревья сами себя не построят. Я бы просто обходил вглубь и останавливал ветку, если бы превышал длину пути.
Три слова: размещение, сочетание, перестановка. Пиздуй на википедию, выясни что эти слова означают и выучи три формулы.
Взялся читать Конкретную математику стоп, ты назвал её Реальная математика? ну ты лах, решил что буду решать все домашние и контрольные задачи. В результате пока не выполз из первой главы.
Как-то хардкорно.
Давай решение или подсказку.
Я же писал что в комбинаторике не силён. Подскажи формулу.
Дать решение? Простое что охуеть
Длинну пути я проверяю.
А деревья строишь?
Давай, если это решение не типа соснуть хуйца.
Не бери его решение, бери моё, оно быстрее!
Нет, я сразу путь считаю.
https://ideone.com/Y6yY6w
Не знаю как 5 секунд, твой пример с дохуячислом у меня находится за 1,9 сек.
>сразу путь считаю
Это как?
Охуеть блять! А можешь пояснить что конкретно ты сделал? Это какая то байтоебская магия? Как это вообще возможно?
у тебя массив размера n x m x k — кол-во вариантов добраться до каждой точки используя пути соотв. длины
тупо заполняешь его
динамика
Подскажи, где я проебался.
У меня число чуток не то, что у ОПа - только первые 27 чисел сходятся из дохулиона.
>>у тебя массив размера n x m x k
Почему именно такая длинна массива?
Потому что рекурсивная функция, которая принимает x, y, k.
Нужна таблица, которая позволит сделать так, чтобы функция вычислялась только один раз.
x и y меняются в пределях от 0..n и 0..n, а шаг - от 0 до к.
Итак, количестко итераций снижается с дохулиона со 192 разрядами до 2х миллионов, что тоже дохуя, но уже приемлемо.
Я давно собирался вбросить решение, но через memoize! работало долго, уже k=100 считало секунд 10, а 200 считало бы час или полтора.
Сперва пилил свою таблицу и свою мемоизацию (и заебся отлаживать), а потом нашел в документации, что memoize! можно размер таблицы прямо указать. И заебашил алиас на него
>alias memstep = memoize!(step, 100 100 200);
А в твоем коде, ты просто заполняешь этот массив 1 и 0? И потом как то приобразовывается к целому числу?
А еще, вот что делает этот кусок кода: return up + down + left + right;
Он рекурсивно вызывает эти функции чтоли? Первый раз просто D разбираю.
>И потом как то приобразовывается к целому числу?
Суммируется же.
>А еще, вот что делает этот кусок кода: return up + down + left + right;
Да. Ну епт, вся прога строк 30 занимает - хуле там непонятно?
Писал бы на крестах - строк 200 бы заняло минимум, а тут же и длинная арифметика есть в дефолте, и мемоизация.
>Суммируется же.
Но даже если весь массив запонить 1. То сумма получится всего лишь 2000000 а не духуилиард.
С чего вдруг? Ты походу не вдупляешь, количество вариантов по клеткам в зависимости от k растет просто в ебанутой прогрессии.
Ну вот я пока и не пойму до конца, как этот алгоритм работает на D.
Выше же мне сказали что
>у тебя массив размера n x m x k — кол-во вариантов добраться до каждой точки используя пути соотв. длины
тупо заполняешь его
Да, но в клетках будут охуенно большие числа.
идея динамики:
что бы прийти в клетку (x; y) с длинной пути z, нужно быть в одной из соседних клеток с длинной пути z-1
Вроде начинаю понимать, то есть в клетках будет вот эта сумма? return up + down + left + right;
А что означет слово auto? В доках не нашел его что то.
auto значит "товарищ компилятор, мне лениво писать тип выражения - так что будь добр, угадай его сам"
>то есть в клетках будет вот эта сумма? return up + down + left + right;
Да, верно. Каждый вызов ветвится на 4 по сторонам и суммирует результаты (но сперва смотрит, не обсчитывал ли он уже такой вызов).
Когда k=0 - то если мы в искомой клетке - путь верный(1), иначе путь неверный (и нехуй дальше уменьшать k)
Анончик, ты охуенен. А как обычные ЯП обходятся без memoize? Оставь свой контакт какой нибудь, если я таки решу эту задачку, и меня возьмут на работу, то подарю любую игру в стиме/ дам на пиво/етц.
Или ты, я тут запутался, вас тут двое похоже.
>А как обычные ЯП обходятся без memoize?
В лиспе memoize вроде есть или что то подобное.
В обычных ЯП ты - сам себе memoize, и будешь делать это руками. Ну а тут оно просто есть по дефолту. Я просто обожаю дишечку - это как "правильные кресты 2.0"
>и меня возьмут на работу
Это что, для собеседования чтоле?
>ставь свой контакт какой нибудь
Да не вопрос. [email protected]
Блять, с разметкой обосрался.
Да, ты прав, в кложе есть меморайз попробую на нем сделать. А насчет работы, да я норм собеседование прошел, и в конце спросил, а мы что, строчки разворачивать не будем и попросил что нибудь на алгоритмы. Ну я думал будет что то типа найти в строке кол-во трех подряд идущих символов 'abc'. А мне дали эту залупу.
Залупа в принципе простая, я просто поначалу охуел от числа на 192 разряда.
Сука, как же хуёво жить в Крыму. Час назад написал последнюю строчку проги и в ту же секунду вырубили свет. Сейчас заново набираю по памяти.
uint k = 100;
а вот этот к нигде не используется?
Ну, замени на uint k = 200 и подсунь в конец функции.
Мне лень было оформлять это говно, так что все параметры я захардкодил.
На сам алгоритм они не влияют, это организационные мелочи.
Да не, норм. Вроде переписал почти на то, что мне надо.
В лоб не переписывай, я где то проебался или опечатался.
С твоим примером сходятся только первые 27 цифр (если он сам конечно без опечатки)
А если вот это переписывать вручну, то тут нужен будет трехмерный массив? Или как лучше по индексу к нему обращаться?
memoize!(step, 100 100 200);
>А если вот это переписывать вручну, то тут нужен будет трехмерный массив?
Я, до того как нашел, что memoize можно подсунуть размер хеш-таблицы - охуел от "быстродействия" и пытался напилить свою реализацию.
Я делал одномерный, arr[mnk] c индексацией по формуле.
советую участвовать на кодфорсес и топкодер, пригодиться по работе может, а тимус это просто задачник с проверкой, знаю ребят которые прорешали 600-950 на тимусе и имеют на кодфорсес ранг Эксперт, знаю парня который входит в топ 10 на тимусе.
> ту же секунду вырубили свет. Сейчас заново набираю по памяти.
для таких случаев надо иметь ноут
Для таких случаев надо иметь ИБП, или хотя бы спинной рефлекс делать сейв каждые 2 минуты. Ну впрочем дохуя ИДЕ делают это автоматически
>3026331761191340503770893374595925277055394295450130902271922168548205308642694668236259320332359033488388961148337920
Здравствуйте, господин работодатель! Как я вижу вы догадались загуглить число, которое этому - оболтусу для тестов.
Эта простая мера позволила вам выяснить, что данный кандидат склонен к обману, а также с большой вероятностью - наркоман и извращенец (в этом легко убедиться если заглянуть в другие разделы этого форума).
Могу только поапплодировать вашей преусмотрительности!
Здравствуйте, господин работодатель! Как я вижу вы догадались загуглить число, которое этому - оболтусу для тестов.
Эта простая мера позволила вам выяснить, что данный кандидат склонен к обману, а также с большой вероятностью - наркоман и извращенец (в этом легко убедиться если заглянуть в другие разделы этого форума).
Могу только поапплодировать вашей преусмотрительности!
В задачнике Меньшикова была такая задачка, посмотри. Там в оглавлении написано, где динамика, там и она должна быть.
Хуле смотреть, ее же уже заебенили.
20 строчек на всю прогу от силы
Тупо трёхмерная динамика?
А что за язык? Питон какой-то с встроенной длинной арифметикой?
Дишечка же.
Можно сделать производительнее, если рассматривать движения по x и по y отдельно. Я нафигачил свой proof of concept, но есть расхождение с ответом после 8 знака, и переполняет стек на ideone. Надо бы переписать на явное динамическое программирование.
https://ideone.com/XZPGR5
Чуть ли не впервые слышу, честно говоря.
Кто такая, чем знаменита?
Кстати тут непонятно, используется ли в координатах нумерация с 0 или 1.
Пинки пай, ты оба варианта пробовал?
Поскольку никакой гугл, микрософт или еще какая хуйня ее не пиарит - она не знаменита.
Вообще, язык, который должен был сделать с++ "с нуля" и избавить его от недостатков. Язык охуенен и я от него тащусь и ссу кипятком, собсно язык моей мечты. Но вакансий по нему нет.
>Кстати тут непонятно, используется ли в координатах нумерация с 0 или 1.
Вот кстати, где то тут я и проебался, пока особо не искал.
Мой ответ сходится только на первые 27 цифр. Или надо чего-то поправить и найти, или исходное число само с опечаткой.
Жаль, что так получилось.
А каких именно недостатков?
У меня знакомый анимешник на нем кф-раунды тащит
Любых. Возьми любое говно из крестов, которое бесит - и тут ты его не найдешь.
Например, тут нормальные шаблоны, я их просто беру и пишу (а в крестах ниасилил). Тут нормальные строки, а не 9000 велосипедов. Тут нормальная блять стандартная библиотека (что заметно, для этого примера я просто заюзал мемоизацию и длинную арифметику, а не велосипедил их). Особо охуенные тут слайсы, аналогов в других языках не видел.
По сути, основная идея такова - язык быстрый и нативный, есть сборщик мусора, но возможность пердолиться с указателями никто не отбирал.
Есть указатели, есть маллок и фри, в стандартной библиотеке есть и весь сишный апи. И вообще она спокойно юзает либы от крестов и си.
Долго объяснять короче, язык моей мечты, рили.
Зашел я значит вот сюда http://acm.timus.ru/ranklist.aspx и мой пердак улетел в стратосферу.
Я нихуя не знаю из вышеперечисленного, ибо школьник.
А так ли это важно, что есть в стандартной библиотеке? Нельзя что-ли не стандартную библиотеку с длинкой подключить?
Можно. Все можно.
Но когда нормальная стандартная библиотека - ты просто решаешь задачу и занимаешься ей, а не еблей с языком. Вон, сколько у крестов строк? сишные ака "хуйня из указателей" - раз, std::string - два, QString - три, вроде в OpenCV тоже что то было...
Заебывает, честно.
Чому?
я из этого списка знаю парня
>Можно сделать производительнее
Ну, не знаю как запустить грувипрогу на своем компе.
Но на моем пример с оповскими данными у меня считается меньше секунды при ограничении в 5 секунд.
>но есть расхождение с ответом после 8 знака
У меня первые 27 сходятся. ХЗ, почему не все - вроде должно быть все правильно.
>и переполняет стек на ideone
Я как то логарифм от факториала пытался на жабе посчитать и охуел - жаба то, в отличии от дишечки, не оптимизирует хвостовую рекурсию, и на 15000 вроде у меня тоже стек распатронило на ровном месте.
Если на пальцах - есть минимальное число ходов, требуемое чтобы из (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).
Твой метод я вроде понял (только не понимаю, почему это должно работать).
Хуле, щас попробую реализовать. Затестю и результат, и скорость.
Это что за язык?
А что “зачем”? Я этих ваших грувей не знаю, их цомпелятора у меня нет.
И какая разница, если код - абсолютно такой же?
Очевидно, первый пик - Ди, второй - Groovy.
Код-то один, а вот результат-то разный
И результат такой же, я просто с условиями химичил после.
Там >=0 и <m должно быть. Форкни и проверь.
И да - как запустить эту грувипрогу в терминале, имея бубунту?
Хочу сравнить скорость.
Хочу сравнить скорость.
Форкнул - https://ideone.com/2YW0d1
Получил результат
3026331761191340503770893373029273844677591368122716618704642247067326254159330908652193057324457123166746681628950720
Всё ещё не сходится с
3026331761191340503770893372888058869422738484032331390788387569021838371831280294822254761283098828539404148603710720
Расслабься.
У источника данных вообще 3026331761191340503770893374595925277055394295450130902271922168548205308642694668236259320332359033488388961148337920.
И у тебя, и у меня с ним сходятся только первые 27 цифр.
Такое ощущение, что везде реализация BigInt - сродни флоатам и накапливает какую-то погрешность.
У меня мир рушится, а ты говоришь расслабся?!
Для начала сделай
sudo apt-get install groovy2
>У меня мир рушится, а ты говоришь расслабся?!
Как мы заметили, на абсолютно одинаковом алгоритме могут быть отличия в цифрах. И твой, и мой сходится с тестовым на первые 27 цифр (причем мой сходится ближе, азаза).
Вывод1: как минимум 1 из наших ответов неверен.
Вывод2: оповское тестовое значение также может быть неверным.
Поскольку алгоритм явно одинаков, сколько там получилось - не столь важно (один хуй с таким числом - столько атомов во вселенной не наберется)
>sudo apt-get install groovy2
Ну допустим сделал - а дальше то что?
groovy test.groovy
Ну ты пастебин то скинь.
хуле я со скриншота набирать буду?
Так я думал ты хочешь замерить перформанс первой моей версии -
Ну ок. Кинул тебе на пастебин, проверяй http://pastebin.com/UsRpiM2b
Первую версию я хотел утрецом переписать на дишку, и сравнивать уже сравнимые вещи.
Один хуй я этих грувей не знаю.
org.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
По ходу у тебя вызывается первая версия
groovy -v
показывает 1.8.6? Тогда делай
sudo apt-get remove groovy
После этого должен остаться пакет groovy2 и команда groovy test.groovy должна работать.
Работает.
Но дишная версия ощутимо быстрее.
Ты замерял время старта JVM.
Юзай
println System.currentTimeMillis()
...
println System.currentTimeMillis()
Но вообще оно и должно быть медленнее на одинаковых алгоритмах. Типизация то типическая.
То есть динамизация типическая. То есть... Ну ты понял.
Ну да, понел.
Померял - 3421 мсек.
Надо будет с утреца заняться хуйней и попробовать переписать это на чистом лишпе. Там, если вики не пиздит, и мемоизация встроена, и числа - длинные по дефолту.
Интересно, какой там результат будет, лишпу все таки несколько десятилетий и ему я доверяю.
Интересно, какой там результат будет, лишпу все таки несколько десятилетий и ему я доверяю.
Моя первая прога на Хаскелле. Прям чувствую, как передо мной распахнулся мир пандорических захватов, монадических трансформеров в категории эндофункторов, кластеров метапарадигм, зигохистоморфных препроморфизмов наконец.
>solve :: Int -> Int -> Int -> Int -> Int -> Int -> Int -> Integer
Сука до слез
>Вывод2: оповское тестовое значение также может быть неверным.
Возможен и такой вариант, так как у меня точно такое же значение как и у вас получается
3026331761191340503770893372888058869422738484032331390788387569021838371831280294822254761283098828539404148603710720
А можно ли за год надрочиться чтобы решать div2 A и div2 B?
Блять. Попытался переписать на язык смайликов не зная его, и обосрался.
Может подскажете чого не так?
http://pastebin.com/6xGZSze4
Смотря что у тебя с математикой. Если в вузе получал пятёрки, то можно.
Сначала надо прорешать стандартные задачки по дискретной математике.
Сделать обязательные мелочи типа перевода между произвольными системами счисления и генерации чисел-палиндромов. Не помешает самому написать длинную арифметику.
Вникнуть в трюки с побитовыми операциями, тут подойдёт http://www.hackersdelight.org/
Сделать поиск анаграмм методом "с размахиванием руками".
Потом пишешь решето Эратосфена и факторизацию чисел, задачки на линейное программирование (начни с задачи о том, сколькими способами можно разменять энную сумму заданными купюрами).
Обход графа в глубину и в ширину, поиск кратчайшего пути, минимизация потока. Всё это для графов, представленных разными структурами данных.
Пишешь решалку судоку и непобедимый алгоритм для крестиков-ноликов миимаксом.
Проникаешься основными формулами комбинаторики, пишешь свою небольшую либу для получения всех сочетаний, перестановок и размещений для заданного множества.
Особое внимание уделяешь рекуррентным формулам для возведения в степень n, вычисления чисел Фибоначчи и Каталана, коэффициентов бинома Ньютона. Задачка Иосифа-Флавия сюда же.
Теория чисел нужна на уровне алгоритма Эвклида, генерации пифагоровых троек, формул для "многоугольных" чисел, сумм полиномов для аргументов от 1 до N, нахождения периода десятичной дроби, полученной в результате деления двух чисел и наоборот.
Когда освоишь это надо просто нарешивать задачи.
Какой диалект и как запустить?
Сохранил твой пост, добра тебе
мимо-пробегал
матан было 4, но я филонил, линейка, геометрия, тервер, матстат - отлично, в школе был по математике лучше тех ребят что ездили на финалы acm
Спасибо тебе. Вот ты так расписал все подробно, сколько лет тебе? Какие достижения в программировании?
26 лет. Никаких достижений тащемта нет. В шараге где я учился никто подготовкой олимпиадников не занимался. Жаль конечно.
Это хобби у меня такое - решать головоломки и олимпиадные задачки по программированию.
Решённые задачки я складываю в большой чёрный пакет облачную папочку. За год больше сотни набирается.
Когда писал пасту я открыл эту папочку и пробежался по решениям. В пасту включил знания, требуемые для решения типовых задач.
Учитывай что это начальный-средний уровень. В этой пасте даже китайской теоремы об остатках нет.
Common Lisp
Я на бубунте запускал REPL и копипастил по строчкам, gcl
Пробовал в Гугл Код Джэм?
http://hecs.info/
Что скажете, атлеты?
Что скажете, атлеты?
Щито это?
Не знаю. Что-то вроде руководства к действию, наверное. Я вообще у вас спросил
Ну хер знает, я ничего не читаю, а решаю велосипедно "как в голову взбредет".
И как решается? Сколько на кфе?
Кстати, всякие жуткие структуры данных тебе тоже в голову сами приходят?
>Сколько на кфе?
Не знаю, что это и где. Я несколько дней назад вкатился
Это какие такие?
Навскидку декартовы деревья, многомерные деревья декартовые, деревья отрезков с модификациями, суффиксные деревья, много их
А никак. Я всей этой ебани не знаю.
Хуле, вкидывай задачу, где оно применяется.
http://neerc.ifmo.ru/school/archive/2014-2015/ru-olymp-regional-2015-day1.pdf
Третья, с прошлогоднего региона
Ты ничего не путаешь? 3-я задача решается в лоб.
С полными ограничениями она решается декарткой или корневой декомпозицией и никак иначе
Хуле, вот и попробую.
Иди сначала почитай про сложность по Колмогорову
Нахуя? Вот упрусь в какую непреодолимую хуйню в процессе решения - тогда и пойду гуглить и читать.
Где можно найти пример входных и выходных данных? Я имею в виду - именно ебического размера, а не тот крошечный?
В чём подвох? В том, что в список делаются вставки, и надо использовать линкед лист, а по нему доступ стоит O(n)?
http://codeforces.com/gym/100586
Здесь можешь ее попытаться сдать
Или выкачать архив тестов отсюда:
http://neerc.ifmo.ru/school/archive/2014-2015.html#region
Да, Декартово дерево в среднем дает нам асимптотику логарифмическую + выигрыш по памяти
Ну хуй знает, я бы наверно навелосипедил ещё один двусвязный список, в котором хранил бы ссылки на каждый скажем 300-й элемент основного. И апдейтил бы его хвост после каждого эвента.
Или можно сделать по-другому. Держать значения в массиве, отдельно мапу для добавляемых значений и таблицу поправок вида
"начиная с 12345-го индекса индексы занижены на 1"
Когда таблица будет слишком разрастаться, создавать новый массив со всеми поправками и добавлениями.
Если писать на сишке вполне можно и уложиться в секунду.
Во-во. Вот, я думаю, в конечном итоге этот "велосипед" и будет похож на это самое говнодерево.
Не отрицаю, что такое шаманство может зайти. Но декартку проще и очевиднее было написать
Подумал немного над этим велосипедом... Можно сделать лучше. Не привязываться жёстко к каждому k-му элементу, а просто хранить лист структур (указатель на начало диапазона, количество элементов в диапазоне).
Если диапазон слишком разрастается - дробить его на 2, стал слишком маленьким - соединять с соседом (и сразу дробить на 2, если получился переросток).
Ничто не мешает сделать эту индексную систему многоуровневой. Жопой чую, что можно добиться логарифмического времени доступа в худшем случае. Надо будет внимательно посмотреть на худшие случаи с переполнениями и недонаполнениями, задевающими сразу все уровни.
Получается эдакое дерево, упавшее на бок и попиленное лесорубами.
>декартку
ниасилил причем тут декартово дерево
в моем понимании, для каждого узла будет {кол-во элементов в левом поддереве, сумма квадратов длин листьев (= сумме этого элемента левого и правого поддеревьев), высота (для балансировки)}
соотв. O(k ∗ log(n))
Всё конечно же изобретено до меня - https://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist
К сожалению не могу найти ничего про его большое О на удаление/добавление.
http://pastebin.com/ZmKktwua
ubuntu@ubuntu-VirtualBox:~$ time clisp test.cl
3026331761191340503770893372888058869422738484032331390788387569021838371831280294822254761283098828539404148603710720
real 1m30.980s
user 0m18.352s
sys 0m2.264s
Пацаны, кто вккап пишет сейчас?
смотрю квалификацию, чувак из моей школы уже решил все задачи
У меня тоже некоторые знакомые все порешали. Я туплю над третьей, одно левое решение уже заслал
у тебя какой рейтинг?
Сейчас под 1400, добивался почти 1600
Короче первое место займут ребята из УрГУ или Китая
давно тренируешься? какое образование?
Вккап - это только для русских. Первое место займет Коротткевич с Бардашевичем (subscriber и tourist)
10 класс, про олимпиадное программирование знаю с 8. Большую часть времени страдал хуетой
>Я подтверждаю, что мой возраст не менее 14 и не более 23 полных лет в настоящий момент.
Тебе 12?
Да.
ты старичок как и я наверно
Я туриста как то не заметил, так то да, турист первый будет
Что-то затупил. Надо было Абу_team создавать и решать всем двачем
На самом деле не вдупляю, как можно быть Геной. Он же все нахуй решает
Я когда увидел рейтинги топов на кодефорсес долго истерически смеялся.
Они заявляют, что их система рейтинга подобна ЭЛО.
В шашках, шахматах, и тому подобном говне топовые игроки имеют ЭЛО рейтинг 2500-2700. А тут 3850. Пиздец.
Не понял, бля, а где русские?
Сколько у кого задач и рейтинга на тимусе?
ну так парень с 5 лет кодит, я про код до 27 лет и не слышал даже
у меня 2 задачи решено, парень из моей школы на первой страничке светится, потом еще парень из школы в топ50
Что за парень-то в топе?
Посаны, подскажите.
Бинарный поиск работает по отсортированным массивам. А можно написать вменяемый бинарный поиск через рекурсию который работает и с развернутыми массивами?
Допустим, есть [1,2,3..n] как arr и возможен также [100,99,98..n] как аргумент, надо чтобы нашло индекс в обоих случая.
Конечно проверить в тупую массив и написать две ветки через if я додумался, но может есть какое-нибудь более элегантное решение, чтобы не городить лишнюю кучу кода?
нюфак в этих ваших алгоритмах и задачках
Бинарный поиск работает по отсортированным массивам. А можно написать вменяемый бинарный поиск через рекурсию который работает и с развернутыми массивами?
Допустим, есть [1,2,3..n] как arr и возможен также [100,99,98..n] как аргумент, надо чтобы нашло индекс в обоих случая.
Конечно проверить в тупую массив и написать две ветки через if я додумался, но может есть какое-нибудь более элегантное решение, чтобы не городить лишнюю кучу кода?
нюфак в этих ваших алгоритмах и задачках
Уважаю братишка. Вот мое решение на кложе https://ideone.com/LVX5ng
Бинпоиск работает на монотонных последовательностях
Расскажите свои истории успеха, как пришли к олимпиадам, как трудились чтобы достичь высот?
Лет 8-9 назад училка по информатике потянула на городскую коколимпиадку по погромированию. Не трудился.
Эээ, все.
И что дальше было? Сейчас что с тобой?
Ничего. Потом я пошел в вузик. Но вузиковскую олимпиадку по кокограммированию я засрал, ибо там скорее всего был сговор - по правилам на отбор должен был отводиться час, а нам дали полчаса и по листку бумаги с заданием, которое (как я уже вспомнил на 3м курсе, когда у нас пошла комбинаторика и матстатистика) - вообще не имело ничего общего с программированием, а по сути это была формула из комбинаторики. Ну, разве что реализовать "функцию факториала" для нее, лол.
После вузика 2 года поработал, заебало, уволился, сычую.
тебе 24? какие планы сейчас, гугл код джэм будешь пытаться? я вообще в школе не знал о программировании, хотя на олимпиадах по матеше уделывал парня который сейчас уже и гугле и фейсбуках поработал
>тебе 24?
Да. Скоро 25.
>какие планы сейчас
Никаких. Попроебываюсь, поучу алгоритмы (работал погромистом, но по образованию я инженегр и самоучка - так что теоретические основы у меня хромают). Права получу, пузо сброшу, ремонт сделаю, отдохну нормально.
А потом поищу работу получше.
Как такое решать?
Где ограничения и как проверять?
Сука, нельзя, бля
Достаточно минуту порисовать на листочке
Бывший_цвета_морской_волны - кун
шахматная раскраска
Ну, пиздец. Сказано же не обсуждать нигде. Ты мне еще вторую тогда оттуда реши, бля
да похуй мне бля, щаз решу
обычная линеечка, хуйле
Лично я уже минут 30 потею. Тяжело думать что-то
да всем похуй, все равно те кто обсуждает нихуя не смогут
вообще эти задачи за 10 минут все решаются опытным олимпиадником 14ти лет
Лол, умудрился тл схватить. Вот же ж я тупой
Теперь ошибка на претесте 4. Я ебал
Если я начал изучать программирование в феврале, и до сих пор не могу решить див2а и див2б, то это значит что я совсем тупой?
рацетамы пропей
Это значит, что ты мало занимаешься
нужно больше, по 8 часов в день? стоит ли это делать каждый день или как в кружках 2 раза в неделю?
Еще раз, что ты можешь решить, а что нет?
На каком языке пишешь?
прохожу курс с++ на яндексе, в курсе какие-то задачи могу решить, какието нет, на кодфорсерс не могу решить ниче пока
Посоны, где можно разбор задач с ИОИП посмотреть? А то что-то ничего не могу нагуглить.
Там только у одной задачи разбор.
Посмотри, может на кфе топики есть
Там ничего нет или я плохо ищу.
Печаль. Официальных разборов, насколько я знаю, нет
Не олимпиадная задача, но вы тут любите алгоритмы подрочить, так что спрошу.
Есть набор точек вида (широта;долгота). Нужно придумать как находить точку в этом наборе, ближайшую к заданной (не из набора), быстрее, чем за линейное время.
Например, есть координаты всех макдональдсов, и нужно найти ближайший к юзеру, даже если юзер посреди Антарктиды.
Для плоскости есть quadtree, а вот как сделать что-то подобное для сферы - ума не приложу.
Есть набор точек вида (широта;долгота). Нужно придумать как находить точку в этом наборе, ближайшую к заданной (не из набора), быстрее, чем за линейное время.
Например, есть координаты всех макдональдсов, и нужно найти ближайший к юзеру, даже если юзер посреди Антарктиды.
Для плоскости есть quadtree, а вот как сделать что-то подобное для сферы - ума не приложу.
А чем плоскость от сферы то отличается?
Тем, что тривиально делится на куски одинаковой площади и формы.
Ну представь, что твой шарик - это прямоугольник. Развертку глобуса не видел?
Ну, будут куски не одинакового размера - и поебать, все равно в антарктиде макдональсов не шибко много.
Не катит. Макдональдсы только для примера.
Если бы такое решение подходило - взял бы геохеш и не парился. Но, во-первых, в полярных широтах размер кусков сильно отличается от экватора, во-вторых, кратчайшее расстояние вообще может идти через полюс и развертка отсасывает.
Чем блять не катит?
Нарезаем шарик на куски, каждую точку пихаем в соответствующий кусок. Итого - чтобы искать ближайшую мы перебираем расстояния только точек в текущем куске, а не на всем шарике. Куски можно делать многоуровневыми - большой кусок включает в себя куски поменьше и так далее - получится сорт оф дерево.
Не сомневаюсь, карты ИРЛ как-то похоже и работают.
Посмотри на карту. Что ближе всего к Хельсинки: Улан-Батор, Анадырь или Нью Йорк? По развертке хуй скажешь, что Анадырь.
Карты работают в самом деле так, но только потому, что подобные задачи на практике всегда ограничены относительно небольшой территорией, в рамках которой кривизной Земли можно пренебречь.
Карты работают в самом деле так, но только потому, что подобные задачи на практике всегда ограничены относительно небольшой территорией, в рамках которой кривизной Земли можно пренебречь.
>что подобные задачи на практике всегда ограничены относительно небольшой территорией, в рамках которой кривизной Земли можно пренебречь.
Ну вот - а в твоем случае разве не так? Что у тебя за задача такая?
Нет, в моем нельзя, решение должно работать для всей Земли. Задача с авиацией связана.
Сейчас работает полным перебором, но банально интересно найти оптимальное решение для общего случая.
По какому количеству объектов идет поиск?
>Для плоскости есть quadtree, а вот как сделать что-то подобное для сферы - ума не приложу.
Да точно такое же рекурсивное разбиение пространства. Наиболее безгеморройный способ - взять octtree и отобразить широту и долготу в [x;y;z] на сфере, так как минимальное расстояние по поверхности сферы будет соответствовать минимальному же расстоянию по хорде.
Ну, я слышал, что для поиска кратчайших путей алгоритм есть. Дыйкстра, как-то так
Ну и получишь ты Улан-Батор, Анадырь и Нью Йорк. Потом пройдёшься по ним, посчитаешь расстояние и выберешь наименьшее.
Как понять сколько ближайших точек надо набрать прежде чем выбирать из них наименьшее?
> минимальное расстояние по поверхности сферы будет соответствовать минимальному же расстоянию по хорде
Не подумал об этом. Ты прав, это выглядит как самое простое решение. Спасибо.
Подскажите, как решать. Не могу понять как записать условие, как соотносятся i и j каждого элемента
m[j] == abs(i - j)
поясни, пожалуйста, что такое m[j] и что такое abs, а то пока такого не объясняли еще на курсе
>такое 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
Спасибо, ты просто мегамозг! Жаль что у меня нет таких друзей программистов
Здесь все твои друзья
Наверное нужно начинать просмотр с первого элемента, если он не равен искомому то потом смотреть второй, потом четвертый, потом восьмой - пока не получим элемент больший искомого, и дальше бинарный поиск на последнем отрезке.
Вопрос олимпиадникам: бывает ли у вас, что вы дропаете задачи, так и не решив, и переключаетесь на другое?
Ну да. Все так делают время от времени.
Расскажите про Кодефорсес. Когда там контесты? Там всегда правила, что сначала задача больше баллов стоит, чем потом? Насколько сложные задачи? Какой рейтинг там -- ето крута?
Контесты на главной странице вывешиваются объявы, бывает что несколько за неделю. Про баллы не очень понятно, я сам не умею решать, но видел как в разные контесты у человека вычиталось за 2 решенные из пяти, а в другой контест например за 2 решенные прибавлялось. Еще вычитают если ты одну задачу несколько раз отсылаешь неверное решение. Крутой рейтинг начинается думаю с Эксперта. Ниже Специалиста наверно зашквар.
Я ньюфаг, записался в ВУЗе на курсы, щас тренируют на acmp, говорят, что потом нужно на Тимус с Кодфорсами переходить. И у меня возник вопрос: какова сложность задач на олимпиадах (на том же acm) по сравнению с acmp? Если я решаю на acmp задачи сложности 30-40% это же все хуйня по сравнению с олимпиадами?
Ребята, вот эта задачка совсем начальный уровень считается да?
Да, легче уже ничего нет.
Ультралегкая
Нихуя. Мне за эту задачу на собеседовании Senior Ruby Developer дали.
решение написали быстро
бамп вопросу
Ну так возьми да посмотри задачки предыдущих олимпиад.
Ух ты, какой лвл? За какой срок научился так решать?
Изначально решение выглядело проще, но длиннее. Я решил его вручную пообфусцировать в целях траллинга.
Участвуешь в асm-тусовке?
Нет.
Бумп
Смотрел. Для меня сложно. хочется поставить какую-то конкретную планку сложности задач, которую я должен уметь выполнять.
Расскажи как вас тренируют, и какие достижения у тех, кто это делает? Какой город?
Есть такая структура данных, которая мне быстрее, чем за линию уменьшит значения части элементов массива на 1?
Последовательной части?
Формально нет, а так любое дерево с операциями над подотрезками: дерево отрезков, декартово дерево и тд. Уменьшают за логарифм, используются когда тебе надо сначала провести много операций и потом вывести ответ. Один элемент берётся за логарифм.
Также есть более простая штука, sqrt-декомпозиция, как бы дерево всего с 2 уровнями, соответственно по sqrt(n) потомков в вершине. Принцип тот же самый, что и выше, только изменение отрезка работает за корень, элемент берётся за единицу -> можно часто брать отдельные элементы.
Нам такое в школе в 9 классе давали не траль, я тогда очень долго пыхтел
Я тогда написал через конечный автомат, не зная что такое конечный автомат, лол.
Ах да, по условию за О(n * m)
А по памяти сколько? Можно же тупо массив заполнить, а потом выводить.
Вот, например, задача на КФ. Вчера начал решать, сделал через рекурсию, но то и дело ловил WA и потом TLE. Через часов 5 сдался, спиздил решение у красного. Но чтобы только понять его решение, потратил час. Сейчас проснулся и пытаюсь по памяти воспроизвести его алгоритм (пока WA).
Вот скажите, как можно сразу учитывать все corner-кейсы и ебашить идеальное решение?
Вот скажите, как можно сразу учитывать все corner-кейсы и ебашить идеальное решение?
Хм, а какие там крайние случаи? Мне видится, что задача решается за линию скользящим окном.
Мое первое решение и было окно. Мало того, что надо учесть все выпуклости, так еще и по времени оно не проходит, как оказалось.
И за линию окном никак. Отсечешь правую часть, а она может входить в решение, и наоборот. То есть надо делать два слайса: [left, right-1] и [left+1, right]. Рекурсия даже с сохранением значений не прошла.
Непонятно, там же по идее надо жадно брать возрастающие элементы, как только встретится невозрастающий, запоминаешь его. Дальше, когда встретится следующий невозрастающий, то смотришь, что уже получилось и обрезаешь по первому невозрастающему, ну там около него. Разве не так? Там несколько случаев, правда, получается, какой из элементов увеличивать/уменьшать, но вроде вполне реализуемо.
Находишь в массиве все возрастающие отрезки, включая участки длины 1.
Заносишь их границы в список вида [[1,3], [4,4], [5,10], [11,12], [12,12], ...]
Проходишься по списку отрезков, проверяя, можно ли склеить текущий отрезок с последующим изменением последнего элемента текущего отрезка, или первого элемента следующего.
Если следующий отрезок имеет длину 1, то надо также проверить, можно ли его изменить так, чтобы склеить текущий отрезок со следующими двумя.
После каждого удачного склеивания проапдейтишьь максимальную длину.
>i-ый участник
Как это читается?
итый
>Если следующий отрезок имеет длину 1, то надо также проверить, можно ли его изменить так, чтобы склеить текущий отрезок со следующими двумя.
Это не надо, затупил чёт.
Дьявол в деталях.
Имеем массив [1, 3, 4, 3, 4].
Два возрастающих отрезка - [1,3,4], [3,4]. По твоей логике, изменив [1,3,4] на [1,3,2], его можно будет склеить с [3,4] и получить [1,3,2,3,4] длиной 5.
Запомнил i1, i3, i6. Увидел i7, посчитал длину i1-i6 и отбросил i1, ок. Но i1-i6 - невалидный отрезок.
В общем, вот ссылка, чтобы не теоретизировать, попробуйте заслать свое решение. http://codeforces.com/contest/446/problem/A
Ну понятно, что если мы хотим поменять элемент на позиции fixIdx, то надо проверять, что array[fixIdx+1] - array[fixIdx-1] >= 2
boolean 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
}
Вроде нормально. Попробуй заслать полное решение.
И потом скажи, смог бы ты без подсказок сразу написать идеальное решение, прошедшее бы с первого раза.
Задача, судя по рейтингу А, легкая. Но вот как замечать такие штуки, это ппц. После часов отладки они уже бросаются в глаза, но не сразу же. По идее она должна решаться за 5 минут.
Мне лень.
Решение красного было примерно таким: завел 2 вектора, в одном хранил числа, в другом - индексы предыдущих фейлов. Потом для каждого i смотрел предыдущий и предпредыдущий фейлы. И в зависимости от проверки вроде той, что выше, выбирал нужный отрезок от i до первого или второго фейла и обновлял максимум.
По идее можно было бы вообще без второго вектора, тупо 2 переменных.
На скриншоте олимпиадники as is. Попизди еще, что олимпиадники - элита программистов.
Блять. Что тут написано то? Это на конкурс обфускции должно пойти. Одноразовый код
В смысле, понятно, что так делать не надо. Тебе надо хранить текущий уровень, а не просто смотреть на предыдущий элемент, тогда тебя стопорнёт ещё на 5 элементе.
Вам в 9 классе давали О-нотацию?
И как же я завидую успешным олимпиадным задротам
Да, была, не на продвинутом уровне, конечно. Просто примерное представление о зависимости времени работы от входных параметров. Вот когда после 10 класса нам рассказывали доказательство времени работы суффиксного автомата, это было трудно, да.
пилите перекат уже!
ПОКАТИЛИСЬ
https://2ch.hk/pr/res/706304.html
https://2ch.hk/pr/res/706304.html
Школьный бал
Во время проведения школьного бала планируется запустить m одинаковых воздушных шариков. Наполнить их воздухом согласились n старшеклассников с различной силой духа и выносливостью. Известно, что i-ый участник процесса наполняет один шарик воздухом за ai минут, причем каждый раз после надувания bi шариков отдыхает и переводит дух ci минут (i = 1..n). Нужно узнать за какое минимальное время (в минутах) будут надуты все шарики при оптимальной работе всех участников.